When to prefer LinkedBlockingQueue over ArrayBlockingQueue?

Question

When to prefer LinkedBlockingQueue over ArrayBlockingQueue?

Which data structure to use among LinkedBlockingQueue and ArrayBlockingQueue when:

1. You want an efficient read and write
2. should have lesser memory footprints

Although there is a similar question but it does not highlight the fact that which should be preferred?

Links:

• Java: ArrayBlockingQueue vs. LinkedBlockingQueue
• What is the Difference between ArrayBlockingQueue and LinkedBlockingQueue

Answer 1

Boris the Spider has already outlined the most visible difference between ArrayBlockingQueue and LinkedBlockingQueue - the former is always bounded, while the latter can be unbounded.

So in case you need an unbounded blocking queue, LinkedBlockingQueue or a LinkedTransferQueue used as a BlockingQueue are your best bets from the java.util.concurrent toolbox.

But let's say you need a bounded blocking queue. In the end, you should choose an implementation based on extensive experimenting with a simulation of your real-world workload. Nevertheless, here are some notes that can help you with your choice or with interpreting the results from the experiment:

• ArrayBlockingQueue can be created with a configurable (on/off) scheduling fairness policy. This is great if you need fairness or want to avoid producer/consumer starvation, but it will cost you in throughput.
• ArrayBlockingQueue pre-allocates its backing array, so it doesn't allocate nodes during its usage, but it immediately takes what can be a considerable chunk of memory, which can be a problem if your memory is fragmented.
• ArrayBlockingQueue should have less variability in performance, because it has less moving parts overall, it uses a simpler and less-sophisticated single-lock algorithm, it does not create nodes during usage, and its cache behavior should be fairly consistent.
• LinkedBlockingQueue should have better throughput, because it uses separate locks for the head and the tail.
• LinkedBlockingQueue does not pre-allocate nodes, which means that its memory footprint will roughly match its size, but it also means that it will incur some work for allocation and freeing of nodes.
• LinkedBlockingQueue will probably have worse cache behavior, which may affect its own performance, but also the performance of other components due to false sharing.

Depending on your use-case and how much do you care about performance, you may also want to look outside of java.util.concurrent and consider Disruptor (an exceptionally fast, but somewhat specialized bounded non-blocking ring buffer) or JCTools (a variety of bounded or unbounded queues with different guarantees depending on the number of producers and consumers).

Answer 2

From the JavaDoc for ArrayBlockingQueue

A bounded blocking queue backed by an array.

_{Emphasis mine}

From the JavaDoc for LinkedBlockingQueue:

An optionally-bounded blocking queue based on linked nodes.

_{Emphasis mine}

So if you need a bounded queue you can use either, if you need an unbounded queue you must use LinkedBlockingQueue.

For a bounded queue, then you would need to benchmark to work out which is better.