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.

Solution 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...

Solution 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.

Solution 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 add/poll 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 poll() 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)

Comments

[Adamski]

Thanks Jon - I hadn't noticed that. So where / why would you use ConcurrentLinkedQueue?

[Jon Skeet]

When you need to access the queue from a lot of threads, but you don't need to "wait" on it.

[Pacerier]

Per your last paragraph, why do you say that waiting on a queue is a terrible way of designing concurrent systems? If we have a threadgroup with 10 threads eating tasks from a taskqueue, what's wrong with blocking when the taskqueue has less than 10 tasks?

[Adam Gent]

@AlexandruNedelcu You can't make a sweeping statement like "freakishly terrible" where very often the very actor frameworks you say to use use threadpools which themselves you BlockingQueue's. If you need a highly reactive system and you know how to deal with backpressure (something that blocking queues mitigate) than nonblocking is clearly superior. But.. often times blocking IO and blocking queues can out perform nonblocking particularly if you have long running tasks that are IO bound and cannot be divide n' conquered.

[Brinal]

one doubt here. As you mentiond consumer waits when the queue is empty..how long does it wait. Who will notify it to not to wait?

[Alexandru Nedelcu]

@AdamGent - The actor frameworks do have implementation of mailboxes based on blocking queues, but that's a bug in my opinion, because blocking doesn't work over asynchronous boundaries and thus only works in demos. For me this has been a source of frustration, as for example Akka's notion of dealing with overflow is to block, instead of to drop messages, until version 2.4 that is, which isn't out yet. That said I do not believe that there are use-cases for which blocking queues can be superior. You're also conflating two things that shouldn't be conflated. I haven't spoken about blocking I/O.

[Adam Gent]

@AlexandruNedelcu Are you serious that you can't think of a use case? Sometimes you do not want to drop messages ... ever. Not all companies are Netflix and Twitter where uptime aka availability is more important than consistency (ie drop a few messages who cares)... hint think banking. And blocking queues are very related to blocking IO since both block and one usually causes a need for the other. I have yet to see an Akka implementation not use Blocking Queues (aka threadpool) for blocking database access.. aka blocking IO.

[Alexandru Nedelcu]

@AdamGent - as I said previously, blocking threads is a terrible mechanism for back-pressure and if dropping messages should be avoided at all costs, blocking threads is a terrible way to do it, because it's an in-process trick that doesn't work for the world around you. On blocking I/O I still don't get the link, I'm sure you have a point, I just don't see it. Surely you can't possibly bring up thread-pools as a use-case for blocking queues, but please excuse me while I go and implement my own ForkJoinPool, as it's one of those days.

[Adam Gent]

@AlexandruNedelcu while I generally agree with you on backpressure I have yet to see a "lock free" system from top to bottom. Somewhere in a technology stack whether its Node.js, Erlang, Golang, its using a some sort of wait strategy whether that is a blockingqueue (locks) or CAS spinning its blocking and some cases a traditional lock strategy is faster. Its very hard to not have locks because of consistency and this is especially important with blocking io and schedulers which are ~ Producer/Consumer. ForkJoinPool works with short running tasks and it still has CAS spinning locks.

[Adam Gent]

@AlexandruNedelcu I guess if you can show me how you can use a ConcurrentLinkedQueue (which is not bounded btw hence my weak backpressure argument) for Producer/Consumer pattern which is a pattern needed for schedulers and threadpooling I think I will give in and admit that BlockingQueue's should never be used (and you can't cheat and delegate to something else doing the scheduling ie akka since that in turn will do the blocking/waiting as it is a producer/consumer).

[LateralFractal]

A ConcurrentLinkedQueue is also useful if your thread is checking multiple queues. For instance, in a multi-tenant server. Assuming for isolation reasons you don't use a single blocking queue and a tenant discriminator instead.

[orodbhen]

@brindal The only way for it to wait, that I know of, is in a loop. Which is a significant problem that hasn't been given much attention in the answers here. Just running a loop waiting for data uses a lot of processor time. You'll know it when your fans start revving. The only remedy is to put a sleep in the loop. So it's a problem in a system with inconsistent data flow. Perhaps I misunderstand AlexandruNedelcu's answer, but an operating system itself is a concurrent system, that would be hugely inefficient if it were full of non-blocking event loops.

[amarnath harish]

okay, but if unbounded blockingqueue is used would it be better than CAS based concurrent ConcurrentLinkedQueue

[amarnath harish]

your case only hold true if we use bounded queue, in unbounded queue take() and put() merely consumes extra resource( interms of synchronization ) than ConcurrentLinkedQueue . although it is the case to use bounded queues for Producer-consumer scenarios

[Nishit]

@Adamski IMO, ConcurrentLinkedQueue is just a linkedlist to be used in a multi threaded environment. The best analogy for this would be ConcurrentHashMap and HashMap.

[Nishit]

"but it has the awesome property that the producer does not contend with the consumer. In a single producer / single consumer scenario (SPSC)," IMO, even in a LinkedBlockingQueue, separate locks are taken by producer group threads and consumer group threads.

[Nishit]

@orodbhen Putting a sleep would also not eliminate wastage. The OS has to do a lot of work to get a thread out of sleep and schedule and run it. If messages are not yet available, that work done by your OS goes waste. I would recommend it is better to use BlockingQueue, as it was specifically designed for producer-consumer problem.

[http8086]

actually, I'm very interested in the "consume/produce rate" part, so which one is better if rate goes high?

[Wuaner]

there is no take() in ConcurrentLinkedQueue, put() neither.