LinkedBlockingQueue vs ConcurrentLinkedQueue

Question

My question relates to this question asked earlier. In situations where I am using a queue for communication between producer and consumer threads would people generally recommend using LinkedBlockingQueue or ConcurrentLinkedQueue?

What are the advantages / disadvantages of using one over the other?

The main difference I can see from an API perspective is that a LinkedBlockingQueue can be optionally bounded.

Answer 1

For a producer/consumer thread, I'm not sure that ConcurrentLinkedQueue is even a reasonable option - it doesn't implement BlockingQueue, which is the fundamental interface for producer/consumer queues IMO. You'd have to call poll(), wait a bit if you hadn't found anything, and then poll again etc... leading to delays when a new item comes in, and inefficiencies when it's empty (due to waking up unnecessarily from sleeps).

From the docs for BlockingQueue:

BlockingQueue implementations are designed to be used primarily for producer-consumer queues

I know it doesn't strictly say that only blocking queues should be used for producer-consumer queues, but even so...

Answer 2

This question deserves a better answer.

Java's ConcurrentLinkedQueue is based on the famous algorithm by Maged M. Michael and Michael L. Scott for non-blocking lock-free queues.

"Non-blocking" as a term here for a contended resource (our queue) means that regardless of what the platform's scheduler does, like interrupting a thread, or if the thread in question is simply too slow, other threads contending for the same resource will still be able to progress. If a lock is involved for example, the thread holding the lock could be interrupted and all threads waiting for that lock would be blocked. Intrinsic locks (the synchronized keyword) in Java can also come with a severe penalty for performance - like when biased locking is involved and you do have contention, or after the VM decides to "inflate" the lock after a spin grace period and block contending threads ... which is why in many contexts (scenarios of low/medium contention), doing compare-and-sets on atomic references can be much more efficient and this is exactly what many non-blocking data-structures are doing.

Java's ConcurrentLinkedQueue is not only non-blocking, but it has the awesome property that the producer does not contend with the consumer. In a single producer / single consumer scenario (SPSC), this really means that there will be no contention to speak of. In a multiple producer / single consumer scenario, the consumer will not contend with the producers. This queue does have contention when multiple producers try to offer(), but that's concurrency by definition. It's basically a general purpose and efficient non-blocking queue.

As for it not being a BlockingQueue, well, blocking a thread to wait on a queue is a freakishly terrible way of designing concurrent systems. Don't. If you can't figure out how to use a ConcurrentLinkedQueue in a consumer/producer scenario, then just switch to higher-level abstractions, like a good actor framework.

Answer 3

LinkedBlockingQueue blocks the consumer or the producer when the queue is empty or full and the respective consumer/producer thread is put to sleep. But this blocking feature comes with a cost: every put or take operation is lock contended between the producers or consumers (if many), so in scenarios with many producers/consumers the operation might be slower.

ConcurrentLinkedQueue is not using locks, but CAS, on its put/take operations potentially reducing contention with many producer and consumer threads. But being an "wait free" data structure, ConcurrentLinkedQueue will not block when empty, meaning that the consumer will need to deal with the take() returning null values by "busy waiting", for example, with the consumer thread eating up CPU.

So which one is "better" depends on the number of consumer threads, on the rate they consume/produce, etc. A benchmark is needed for each scenario.

One particular use case where the ConcurrentLinkedQueue is clearly better is when producers first produce something and finish their job by placing the work in the queue and only after the consumers starts to consume, knowing that they will be done when queue is empty. (here is no concurrency between producer-consumer but only between producer-producer and consumer-consumer)

Answer 4

Another solution (that does not scale well) is rendezvous channels : java.util.concurrent SynchronousQueue

Answer 5

If your queue is non expandable and contains only one producer/consumer thread. You can use lockless queue (You don't need to lock the data access).