Menu
When to prefer LinkedBlockingQueue over ArrayBlockingQueue?
Which data structure to use among LinkedBlockingQueue and ArrayBlockingQueue when:
Although there is a similar question but it does not highlight the fact that which should be preferred?
Links:
206
BlockingQueue is a java Queue that support operations that wait for the queue to become non-empty when retrieving and removing an element, and wait for space to become available in the queue when adding an element.
ArrayBlockingQueue is thread-safe. The Iterator provided in iterator() method traverses the elements in order from first (head) to last (tail). It supports an optional fairness policy for ordering waiting producer and consumer threads.
The LinkedBlockingQueue is an optionally-bounded blocking queue based on linked nodes. It means that the LinkedBlockingQueue can be bounded, if its capacity is given, else the LinkedBlockingQueue will be unbounded. The capacity can be given as a parameter to the constructor of LinkedBlockingQueue.
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).
131
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.
36
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
