Pure Danger Tech


Java 7 TransferQueue

28 Feb 2009

Java 7 will include several improvements in the collections and concurrency libraries under JSR 166y. One addition is a new interface called TransferQueue and a corresponding implementation called LinkedTransferQueue.

TransferQueue extends BlockingQueue which extends Queue interface added in Java 5 and adds some new methods. BlockingQueue expresses the concept of a queue that a producer can block when adding items to a queue until there is space avaliable or a consumer can block when removing an item from the queue until an item exists.

TransferQueue takes this one step further and blocks on put until the item is actually consumed by a consumer (not just added to the queue). This new constraint is expressed in the key new method called transfer(). The name is very descriptive – because the blocking occurs until a hand-off is complete from one thread to another, you are effectively transferring the item between threads (in a way that properly creates happens-before relationships in the Java Memory Model).

Several other methods are included as well: two forms of tryTransfer() that perform a transfer but are either non-blocking (transfer only if it can be done immediately) or with a timeout. And then there are a couple of helper methods hasWaitingConsumer() and getWaitingConsumerCount().

When I first read about TransferQueue, I was immediately reminded of the existing SynchronousQueue implementation, which provides a queue with size 0. That seemed inherently useless when I originally looked at it but I’ve since found it to be one of the most useful queue implementations in the collections framework, specifically for this use case of handing off an item from one thread to another.

TransferQueue is more generic and useful than SynchronousQueue however as it allows you to flexibly decide whether to use normal BlockingQueue semantics or a guaranteed hand-off. In the case where items are already in the queue, calling transfer will guarantee that all existing queue items will be processed before the transferred item. Doug Lea says that capability-wise, LinkedTransferQueue is actually a superset of ConcurrentLinkedQueue, SynchronousQueue (in “fair” mode), and unbounded LinkedBlockingQueues. And it’s made better by allowing you to mix and match those features as well as take advantage of higher-performance implementation techniques.

Joe Bowbeer helpfully provided a link to a paper by William Scherer, Doug Lea, and Michael Scott that lays out the LinkedTransferQueue algorithms and performance tests showing their improvements over the existing Java 5 alternatives. LinkedTransferQueue outperforms SynchronousQueue by a factor of 3x in unfair mode and 14x in fair mode. Because SynchronousQueue is used as the heart of task handoff in something like ThreadPoolExecutor, this can result in similar kinds of performance improvements there. Given the importance of executors in concurrent programming, you start to see the importance of adding this new implementation.

The Java 5 SynchronousQueue implementation uses dual queues (for waiting producers and waiting consumers) and protects both queues with a single lock. The LinkedTransferQueue implementation uses CAS operations to form a nonblocking implementation and that is at the heart of avoiding serialization bottlenecks. The paper lays out a lot more detail and data – if you’re interested in the details it’s worth a read.