Package org.jctools.queues
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:
- Bounded/Unbounded SPSC queues - Serving the Single Producer Single Consumer use case.
- 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.
- 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 usually not
supported and dependent methods from AbstractQueue
are also not supported such as:
Collection.remove(Object)
Collection.removeAll(java.util.Collection)
Collection.removeIf(java.util.function.Predicate)
Collection.contains(Object)
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:
- Hot counters (or write locations) are padded.
- Read-Only shared fields are padded.
- Array edges are NOT padded (though doing so is entirely legitimate).
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:
- 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 for performance reasons. On newer OpenJDKs where AFU is made more performant the difference is small. - We use Unsafe to gain volatile/lazySet access to array elements. We could use
AtomicReferenceArray
but choose not to for performance reasons(extra reference chase and redundant boundary checks).
Avoiding redundant loads of fields:
Because a volatile load will force any following field access to reload the field value an effort is made to cache
field values in local variables where possible and expose interfaces which allow the code to capitalize on such
caching. As a convention the local variable name will be the field name and will be final.
Method naming conventions:
The following convention is followed in method naming to highlight volatile/ordered/plain access to fields:
- lpFoo/spFoo: these will be plain load or stores to the field. No memory ordering is needed or expected.
- soFoo: this is an ordered stored to the field (like
AtomicInteger.lazySet(int)
). Implies an ordering of stores (StoreStore barrier before the store). - lv/svFoo: these are volatile load/store. A store implies a StoreLoad barrier, a load implies LoadLoad barrier before and LoadStore after.
- casFoo: compare and swap the field. StoreLoad if successful. See
AtomicInteger.compareAndSet(int, int)
- xchgFoo: atomically get and set the field. Effectively a StoreLoad. See
AtomicInteger.getAndSet(int)
- xaddFoo: atomically get and add to the field. Effectively a StoreLoad. See
AtomicInteger.getAndAdd(int)
-
ClassDescriptionA base data structure for concurrent linked queues.An MPSC array queue which starts at initialCapacity and grows to maxCapacity in linked chunks of the initial size.BQueue<E>BQueueL1Pad<E>BQueueL2Pad<E>BQueueL3Pad<E>Common functionality for array backed queues.FFBuffer<E>A note to maintainers on index assumptions: in a single threaded world it would seem intuitive to assume:This is used for method substitution in the LinkedArray classes code generation.Message passing queues are intended for concurrent method passing.A Multi-Producer-Multi-Consumer queue based on a
ConcurrentCircularArrayQueue
.An MPMC array queue which grows unbounded in linked chunks.
Differently fromMpmcArrayQueue
it is designed to provide a better scaling when more producers are concurrently offering.
Users should be aware thatMpmcUnboundedXaddArrayQueue.poll()
could spin while awaiting a new element to be available: to avoid this behaviourMpmcUnboundedXaddArrayQueue.relaxedPoll()
should be used instead, accounting for the semantic differences between the twos.A Multi-Producer-Single-Consumer queue based on aConcurrentCircularArrayQueue
.This is a partial implementation of theBlockingQueue
on the consumer side only on top of the mechanics described inBaseMpscLinkedArrayQueue
, but with the reservation bit used for blocking rather than resizing in this instance.An MPSC array queue which starts at initialCapacity and grows to maxCapacity in linked chunks of the initial size.Use a set number of parallel MPSC queues to diffuse the contention on tail.An MPSC array queue which starts at initialCapacity and grows to maxCapacity in linked chunks, doubling theirs size every time until the full blown backing array is used.This is a Java port of the MPSC algorithm as presented on 1024 Cores by D.Use an SPSC per producer.This class is still work in progress, please do not pick up for production use just yet.A Multi-Producer-Single-Consumer queue based on same algorithm used forMpmcArrayQueue
but with the appropriate weakening of constraints on offer.An MPSC array queue which starts at initialCapacity and grows indefinitely in linked chunks of the initial size.An MPSC array queue which grows unbounded in linked chunks.
Differently fromMpscUnboundedArrayQueue
it is designed to provide a better scaling when more producers are concurrently offering.
Users should be aware thatMpscUnboundedXaddArrayQueue.poll()
could spin while awaiting a new element to be available: to avoid this behaviourMpscUnboundedXaddArrayQueue.relaxedPoll()
should be used instead, accounting for the semantic differences between the twos.Common infrastructure for the XADD queues.MpUnboundedXaddChunk<R,E> Deprecated.This interface is provided for monitoring purposes only and is only available on queues where it is easy to provide it.A Single-Producer-Single-Consumer queue backed by a pre-allocated buffer.An SPSC array queue which starts at initialCapacity and grows to maxCapacity in linked chunks of the initial size.An SPSC array queue which starts at initialCapacity and grows to maxCapacity in linked chunks, doubling theirs size every time until the full blown backing array is used.This is a weakened version of the MPSC algorithm as presented on 1024 Cores by D.An SPSC array queue which starts at initialCapacity and grows indefinitely in linked chunks of the initial size.Tagging interface to help testing