Java 7 TransferQueue
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
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
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
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.
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.