What is the Difference between ArrayBlockingQueue and LinkedBlockingQueue

Question

1. What scenarios is it better to use an ArrayBlockingQueue and when is it better to use a LinkedBlockingQueue?
2. If LinkedBlockingQueue default capacity is equal to MAX Integer, is it really helpful to use it as BlockingQueue with default capacity?

Yee

For the #1 point, I guess it's quite the same reason as ArrayList vs LinkedList ;) – Contraption

A BlockingQueue doesn't only block on put(). It also blocks an take(), when the queue is empty. – Woundwort

@Contraption but in queue we don't have in between insertion or deletion. So there is no question of per4formance like in the case of ArrayList and LinkedList – Yee

@user2375176 I think if you can estimate size of your queue then ArrayBlockingQueue is better. But if the rate of adding gets high, then it will block and reduce object to pass through – Quitclaim

ArrayBlockingQueue bounded LinkedBlockingQueue is unbounded , If you know the size of reasonable queue/ max number then choose ArrayBlockingQueue over LinkedBlockingQueue. – Arkhangelsk

@user2375176: actually, yes, there is. A LinkedBlockingQueue is a Deque, which allows inserting elements at both ends of the queue. Doing that with an array would force the queue to shift right all the elements when inserting at the beginning. – Woundwort

@JBNizet Actually you can work with begin and end offsets in an array based implementation. When the begin offset is greater than end offset then the elements have to read wrap around the array border. So inserting an element in the front can be done with storing it at the end of the array and adjusting begin offset without the need of shifting. – Triumvir

@FabianBarney: yes indeed. I didn't think about that. – Woundwort

possible duplicate of Java: ArrayBlockingQueue vs. LinkedBlockingQueue – Bethsaida

Answer 1

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.

Triumvir

Answer 2

ArrayBlockingQueue :

ArrayBlockingQueue is a bounded, blocking queue that stores the elements internally in an array. That it is bounded means that it cannot store unlimited amounts of elements. There is an upper bound on the number of elements it can store at the same time. You set the upper bound at instantiation time, and after that it cannot be changed.

LinkedBlockingQueue

The LinkedBlockingQueue keeps the elements internally in a linked structure (linked nodes). This linked structure can optionally have an upper bound if desired. If no upper bound is specified, Integer.MAX_VALUE is used as the upper bound.

Similarity

The ArrayBlockingQueue/LinkedBlockingQueue stores the elements internally in FIFO (First In, First Out) order. The head of the queue is the element which has been in queue the longest time, and the tail of the queue is the element which has been in the queue the shortest time.

Differences

• LinkedBlockingQueue has a putLock and a takeLock for insertion and removal respectively but ArrayBlockingQueue uses only 1 lock.
• ArrayBlockingQueue uses single-lock double condition algorithm and LinkedBlockingQueue is variant of the "two lock queue" algorithm and it has 2 locks 2 conditions ( takeLock , putLock).

Two Lock Queue algorithm is being used by LinkedBlockingQueue Implementation.Thus LinkedBlockingQueue's take and put can work concurrently, but this is not the case with ArrayBlockingQueue. The reason for using a single lock in ArrayBlockingQueue is ,ArrayBlockingQueue has to avoid overwriting entries so that it needs to know where the start and the end is. A LinkedBlockQueue doesn't need to know this as it lets the GC worry about cleaning up Nodes in the queue.

Internist

Answer 3

ArrayBlockingQueue<E> and LinkedBlockingQueue<E> are common implementations of the BlockingQueue<E> interface.

ArrayBlockingQueue is backed by array and Queue impose orders as FIFO. head of the queue is the oldest element in terms of time and tail of the queue is youngest element. ArrayBlockingQueue is also fixed size bounded buffer on the other hand LinkedBlockingQueue is an optionally bounded queue built on top of Linked nodes.

The optional capacity bound constructor argument serves as a way to prevent excessive queue expansion because if capacity is unspecified, than it is equal to Integer.MAX_VALUE.

Read more From here.

Benchmark: http://www.javacodegeeks.com/2010/09/java-best-practices-queue-battle-and.html

Pudens

I doubt that LinkedBlockingQueue would have higher throughput. Any becnhmarks to back the claim? – Daugherty

@EskoLuontola: You can found a benchmark from here: javacodegeeks.com/2010/09/… – Pudens

So based on that benchmark LinkedBlockingQueue is faster in produced-consumer scenarios, but in the first two benchmarks ArrayBlockingQueue is slightly faster. Regardless, Disruptor wipes the floor with both of them: code.google.com/p/disruptor/wiki/PerformanceResults – Daugherty

Answer 4

Adding an element to ArrayBlockingQueue is supposed to be faster since it means only setting a reference to an element of the backing Object array, while adding an element to LinkedBlockingQueue means creating a Node and setting its item, prev and next fields. Besides, when we remove an element from LinkedBlockingQueue the removed Node becomes garbage which may influence app's performance.

As for memory consumption ArrayBlockingQueue always holds an Object array with full capacity even when empty. On the other hand one element in LinkedBlockingQueue is a Node with an Object with 3 Object fields.

Industrious

This is a good answer explaining the reason, but you mentioned ArrayBlockingQueue is supposed to be faster and I agree with you based on the reason you provided. But Javadocs say this "Linked queues typically have higher throughput than array-based queues but less predictable performance in most concurrent applications." see LinkedBlockingQueue.class – Counterblow

Latency and throughput are 2 different things. ArrayBlockingQueue has better latency since it is faster to set reference in array whereas LinkedBlockingQueue has better throughput since it uses 2 diff locks for put and take and only synchronizes on edge condition. – Recitativo