There exist multiple queue implementations in Java. Six alone implementations in the package java.util.concurrent. Why are there so many implementations? For a data structure that is implemented in the single-threaded case as a linked list?

Concurrent queues let two threads communicate asynchronously. And since this communication is often performance-critical we have multiple implementations optimized for a specific communication pattern. Let us look at those communication patterns in more detail and see which queue is optimized for which pattern.

Unbounded

The queue implementation for the first communication pattern, the unbounded multi -producer multi-consumer pattern, is similar to the single-threaded linked list implementation. It is implemented through the class java.util.concurrent.ConcurrentLinkedQueue The implementation is based on an algorithm from Michael and Scott from 1996 described in the paper Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms.

It uses a linked list data structure and compare and swap operations to update this data structure. I am not aware of any other implementation for an unbounded queue in Java.

Here is an example for its usage offering and polling a message from the queue:

Queue<String> queue = new ConcurrentLinkedQueue<String>();
queue.offer("hello world");
String message = queue.poll();
System.out.println(message);
	

The problem of the unbounded queue is that if the producer side is faster than the consumer the queue grows without limit. Or till the Java Heap is exhausted and we receive an OutOfMemory Exception. This leads us to the second type of concurrent queue, the bounded concurrent queue.

Bounded

The package java.util.concurrent contains two implementations for a bounded multi-consumer, multi-producer queue, the class java.util.concurrent.ArrayBlockingQueue and the class java.util.concurrent.LinkedBlockingQueue. The class LinkedBlockingQueue uses a linked list data-structure similar to the class ConcurrentLinkedQueue. But instead of using compare and swap operations it uses locks. The class ArrayBlockingQueue on the other side uses an array to store the messages. And locks to update the array

Here is an example for its usage offering and polling a message from the queue:

Queue<String> queue = new ArrayBlockingQueue<String>(10);
queue.offer("hello world");
String message = queue.poll();
System.out.println(message);
		

Both queues implement the same interface so you can easily switch between the implementation to see which of the queue performs better in your application.

Extra bit of performance

The open-source library JCTools also contains a bounded multi-consumer, multi-producer queue, the class org.jctools.queues.MpmcArrayQueue. This queue is based on an array similar to the class java.util.concurrent.ArrayBlockingQueue. But instead of using locks it uses compare and swap operations. The class MpmcArrayQueue implements the Queue interface so you can switch implementations to see if this implementation improves the performance in your application.

Single consumer and single producer queues.

When only one thread writes to the queue we can avoid the expensive lock or compare and swap operations for writing. The same is true for reading. This is used by JCTools. JCTools provides an implementation for each combination.

Here is an example for creating a multi-producer, single-consumer queue using the JCTools factory:

Queue<String> queue = QueueFactory.newQueue(
	 ConcurrentQueueSpec.createBoundedMpsc(10));

Again all those queue implementations implement the Queue interface. So you can switch implementations to see if those queues improve the performance in your application.

Avoiding memory creation

If we use a bounded queue backed by an array we can reuse the events after they were consumed. This idea is implemented by the LMAX Disruptor. Here you use an array pre-initialized with events. Instead of creating a new event you use one of the already created events. The LMAX Disruptor does not implement the Queue interface so switching implementations is harder. But if you need to avoid garbage collections it is worth a look.

Still more queues

So far we have seen three queue implementations from the package java.util.concurrent. Here are the three still missing implementations:

java.util.concurrent.LinkedTransferQueue

LinkedTransferQueue lets the producer optionally wait till a consumer has consumed its element. A TransferQueue may be useful for example in message passing applications in which producers sometimes (using method transfer(E)) await receipt of elements by consumers invoking take or poll, while at other times enqueue elements (via method put) without waiting for receipt.

java.util.concurrent.SynchronousQueue

A queue where every producer waits until its element was consumed by a corresponding consumer.

java.util.concurrent.DelayQueue

A queue whose element can only be consumed when the elements are expired.

Conclusion

So why are there so many concurrent queues implementations in Java? First Java is a pretty mature programming language. And second, there are many thread to thread communication patterns. And to achieve the maximum performance you need a data structure optimized for this special communication pattern.