79

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:

Lii
  • 11,553
  • 8
  • 64
  • 88
Vaibhav Gupta
  • 1,035
  • 1
  • 8
  • 16

2 Answers2

107

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

Dimitar Dimitrov
  • 16,032
  • 5
  • 53
  • 55
  • 1
    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. – Vaibhav Gupta Mar 15 '16 at 07:36
  • Since most of java GCs are compacting, problems with heap fragmentation don't really exist. – a.yekimov Mar 08 '21 at 13:31
  • @Dimitar Dimitrov what are the `JCTools` alternatives for `BlockingQueue`? – Jire Nov 21 '21 at 01:26
  • 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. – Dasmowenator May 10 '22 at 22:21
21

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.

Boris the Spider
  • 59,842
  • 6
  • 106
  • 166
  • 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. – Rahul Mar 13 '16 at 07:49
  • @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. – Boris the Spider Mar 13 '16 at 07:50
  • 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 ? – Vaibhav Gupta Mar 13 '16 at 08:14
  • @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. – Boris the Spider Mar 13 '16 at 10:37