When to prefer LinkedBlockingQueue over ArrayBlockingQueue?

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:

31288 次浏览
小开

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


提交答案