Skip navigation links

Package org.jctools.queues

This package aims to fill a gap in current JDK implementations in offering lock free (wait free where possible) queues for inter-thread message passing with finer grained guarantees and an emphasis on performance.
At the time of writing the only lock free queue available in the JDK is ConcurrentLinkedQueue which is an unbounded multi-producer, multi-consumer queue which is further encumbered by the need to implement the full range of Queue methods.

See: Description

Package org.jctools.queues Description

This package aims to fill a gap in current JDK implementations in offering lock free (wait free where possible) queues for inter-thread message passing with finer grained guarantees and an emphasis on performance.
At the time of writing the only lock free queue available in the JDK is ConcurrentLinkedQueue which is an unbounded multi-producer, multi-consumer queue which is further encumbered by the need to implement the full range of Queue methods. In this package we offer a range of implementations:
  1. Bounded/Unbounded SPSC queues - Serving the Single Producer Single Consumer use case.
  2. Bounded/Unbounded MPSC queues - The Multi Producer Single Consumer case also has a multi-lane implementation on offer which trades the FIFO ordering(re-ordering is not limited) for reduced contention and increased throughput under contention.
  3. Bounded SPMC/MPMC queues

Limited Queue methods support:
The queues implement a subset of the Queue interface which is documented under the MessagePassingQueue interface. In particular Collection.iterator() is not supported and dependent methods from AbstractQueue are also not supported such as:

  1. Collection.remove(Object)
  2. Collection.removeAll(java.util.Collection)
  3. Collection.removeIf(java.util.function.Predicate)
  4. Collection.contains(Object)
  5. Collection.containsAll(java.util.Collection)

Memory layout controls and False Sharing:
The classes in this package use what is considered at the moment the most reliable method of controlling class field layout, namely inheritance. The method is described in this post which also covers why other methods are currently suspect.
Note that we attempt to tackle both active (write/write) and passive(read/write) false sharing case:

  1. Hot counters (or write locations) are padded.
  2. Read-Only shared fields are padded.
  3. Array edges are padded.

Use of sun.misc.Unsafe:
A choice is made in this library to utilize sun.misc.Unsafe for performance reasons. In this package we have two use cases:

  1. The queue counters in the queues are all inlined (i.e. are primitive fields of the queue classes). To allow lazySet/CAS semantics to these fields we could use AtomicLongFieldUpdater but choose not to.
  2. We use Unsafe to gain volatile/lazySet access to array elements. We could use AtomicReferenceArray but the extra reference chase and redundant boundary checks are considered too high a price to pay at this time.
Author:
nitsanw
Skip navigation links

Copyright © 2013-2015. All Rights Reserved.