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

Missing

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

Digitiform

Nice answer! I agree with what you have mentioned also I would like to emphasis (again) the fact that ArrayBlockingQueue is backed by an array that size will never change after creation. Setting the capacity to Integer.MAX_VALUE would create a big array with high costs in space. ArrayBlockingQueue is always bounded. LinkedBlockingQueue creates nodes dynamically until the capacity is reached. This is by default Integer.MAX_VALUE. Using such a big capacity has no extra costs in space. LinkedBlockingQueue is optionally bounded. – Missing

Since most of java GCs are compacting, problems with heap fragmentation don't really exist. – Budgerigar

@Dimitar Dimitrov what are the JCTools alternatives for BlockingQueue? – Gula

Does ArrayBlockingQueue move all of the elements in the backing array up by one index every time you remove the head element from the queue? If so, it seems like a simple operation like popping the head element off the queue could be extremely expensive. – Noncommittal

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.

Stores

To be able to declare an unbounded queue is also one of the reasons as specified in my answer as linkedList is unbounded whereas arrays are not. – Allred

@rahulroc you actually never say that at all, and never provide any evidence for your assertions. Saying that an array backed collection is bounded is also simplistic and untrue - an ArrayList is array backed. – Stores

Thanks for your answer @BoristheSpider. Your are right this is one good reason for preference, but do we have differences in performance when : 1. You want an efficient read and write 2. there is no concern on whether queue be bounded or not 3. should have lesser memory footprints ? – Missing

@VaibhavGupta what do you mean by 2? How can you have no concern? If you create an ArrayBlockingQueue then you must specify the size of the underlying array. If you set it to Integer.MAX_VALUE your computer will likely crash, so you have to pick a realistic number. If there is no realistic number, then you require an unbounded queue. – Stores