Which concurrent Queue implementation should I use in Java

Question

From the JavaDocs    A ConcurrentLinkedQueue is an appropriate choice when many threads will share access to a common collection  This queue does not permit null elements  ArrayBlockingQueue is a classic  bounded buffer   in which a fixed-sized array holds elements inserted by producers and extracted by consumers  This class supports an optional fairness policy for ordering waiting producer and consumer threads LinkedBlockingQueue typically have higher throughput than array-based queues but less predictable performance in most concurrent applications    I have 2 scenarios  one requires the queue to support many producers  threads using it  with one consumer and the other is the other way around   I do not understand which implementation to use  Can somebody explain what the differences are   Also  what is the  optional fairness policy  in the ArrayBlockingQueue

User · Answer

ConcurrentLinkedQueue is lock-free  LinkedBlockingQueue is not  Every time you invoke LinkedBlockingQueue put   or LinkedBlockingQueue take    you need acquire the lock first  In other word  LinkedBlockingQueue has poor concurrency  If you care performance  try ConcurrentLinkedQueue   LockSupport

User · Answer

Your question title mentions Blocking Queues   However  ConcurrentLinkedQueue is not a blocking queue   The BlockingQueues are ArrayBlockingQueue  DelayQueue  LinkedBlockingDeque  LinkedBlockingQueue  PriorityBlockingQueue  and SynchronousQueue   Some of these are clearly not fit for your purpose  DelayQueue  PriorityBlockingQueue  and SynchronousQueue    LinkedBlockingQueue and LinkedBlockingDeque are identical  except that the latter is a double-ended Queue  it implements the Deque interface    Since ArrayBlockingQueue is only useful if you want to limit the number of elements  I d stick to LinkedBlockingQueue

User · Answer

ConcurrentLinkedQueue means no locks are taken  i e  no synchronized this  or Lock lock calls    It will use a CAS - Compare and Swap operation during modifications to see if the head tail node is still the same as when it started   If so  the operation succeeds   If the head tail node is different  it will spin around and try again   LinkedBlockingQueue will take a lock before any modification   So your offer calls would block until they get the lock   You can use the offer overload that takes a TimeUnit to say you are only willing to wait X amount of time before abandoning the add  usually good for message type queues where the message is stale after X number of milliseconds    Fairness means that the Lock implementation will keep the threads ordered   Meaning if Thread A enters and then Thread B enters  Thread A will get the lock first   With no fairness  it is undefined really what happens   It will most likely be the next thread that gets scheduled   As for which one to use  it depends   I tend to use ConcurrentLinkedQueue because the time it takes my producers to get work to put onto the queue is diverse   I don t have a lot of producers producing at the exact same moment   But the consumer side is more complicated because poll won t go into a nice sleep state   You have to handle that yourself

User · Answer

ArrayBlockingQueue has lower memory footprint  it can reuse element node  not like LinkedBlockingQueue that have to create a LinkedBlockingQueue Node object for each new insertion

User · Answer

Basically the difference between them are performance characteristics and blocking behavior   Taking the easiest first  ArrayBlockingQueue is a queue of a fixed size  So if you set the size at 10  and attempt to insert an 11th element  the insert statement will block until another thread removes an element  The fairness issue is what happens if multiple threads try to insert and remove at the same time  in other words during the period when the Queue was blocked   A fairness algorithm ensures that the first thread that asks is the first thread that gets  Otherwise  a given thread may wait longer than other threads  causing unpredictable behavior  sometimes one thread will just take several seconds because other threads that started later got processed first   The trade-off is that it takes overhead to manage the fairness  slowing down the throughput   The most important difference between LinkedBlockingQueue and ConcurrentLinkedQueue is that if you request an element from a LinkedBlockingQueue and the queue is empty  your thread will wait until there is something there  A ConcurrentLinkedQueue will return right away with the behavior of an empty queue   Which one depends on if you need the blocking  Where you have many producers and one consumer  it sounds like it  On the other hand  where you have many consumers and only one producer  you may not need the blocking behavior  and may be happy to just have the consumers check if the queue is empty and move on if it is

User · Answer

SynchronousQueue   Taken from another question     SynchronousQueue is more of a handoff  whereas the LinkedBlockingQueue just allows a single element  The difference being that the put   call to a SynchronousQueue will not return until there is a corresponding take   call  but with a LinkedBlockingQueue of size 1  the put   call  to an empty queue  will return immediately  It s essentially the BlockingQueue implementation for when you don t really want a queue  you don t want to maintain any pending data     LinkedBlockingQueue  LinkedList Implementation but Not Exactly JDK Implementation of LinkedList It uses static inner class Node to maintain Links between elements     Constructor for LinkedBlockingQueue  public LinkedBlockingQueue int capacity             if  capacity  lt    0  throw new IllegalArgumentException            this capacity   capacity          last   head   new Node lt  E  gt  null        Maintains a underlying linkedlist    Use when size is not known       Node class Used to Maintain Links  static class Node lt E gt        E item      Node lt E gt  next      Node E x    item   x        3   ArrayBlockingQueue   Array Implementation    Constructor for ArrayBlockingQueue  public ArrayBlockingQueue int capacity  boolean fair                 if  capacity  lt    0                  throw new IllegalArgumentException                this items   new Object capacity      Maintains a underlying array             lock   new ReentrantLock fair               notEmpty   lock newCondition                notFull    lock newCondition        IMHO Biggest Difference between ArrayBlockingQueue and LinkedBlockingQueue is clear from constructor one has underlying data structure Array and other linkedList   ArrayBlockingQueue uses single-lock double condition algorithm and LinkedBlockingQueue is variant of the  two lock queue  algorithm and it has 2 locks 2 conditions   takeLock   putLock

[java] Which concurrent Queue implementation should I use in Java?

Examples related to java

Examples related to multithreading

Examples related to concurrency

Examples related to queue