Netty 4.1.107.Final · io.netty.util.internal.shaded.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 java.util.concurrent.ConcurrentLinkedQueue which is an unbounded multi-producer, multi-consumer queue which is further encumbered by the need to implement the full range of java.util.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 java.util.Queue interface which is documented under the io.netty.util.internal.shaded.org.jctools.queues.MessagePassingQueue interface. In particular java.util.Queue#iterator() is usually not supported and dependent methods from java.util.AbstractQueue are also not supported such as:

A few queues do support a limited form of iteration. This support is documented in the Javadoc of the relevant queues.

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 java.util.concurrent.atomic.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 java.util.concurrent.atomic.AtomicReferenceArray but choose not to for performance reasons(extra reference chase and redundant boundary checks).

Both use cases should be made obsolete by VarHandles at some point.

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 java.util.concurrent.atomic.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 java.util.concurrent.atomic.AtomicInteger#compareAndSet(int, int)
xchgFoo: atomically get and set the field. Effectively a StoreLoad. See java.util.concurrent.atomic.AtomicInteger#getAndSet(int)
xaddFoo: atomically get and add to the field. Effectively a StoreLoad. See java.util.concurrent.atomic.AtomicInteger#getAndAdd(int)

It is generally expected that a volatile load signals the acquire of a field previously released by a non-plain store.

Modifier and Type	Interface and Description
public interface	MessagePassingQueue< the event/message type T> Message passing queues are intended for concurrent method passing.
public interface	QueueProgressIndicators This interface is provided for monitoring purposes only and is only available on queues where it is easy to provide it.
public interface	SupportsIterator Tagging interface to help testing

Class Summary

Modifier and Type	Class and Description
pack-priv abstract class	BaseLinkedQueue<E> A base data structure for concurrent linked queues.
pack-priv abstract class	BaseLinkedQueueConsumerNodeRef<E>
pack-priv abstract class	BaseLinkedQueuePad0<E>
pack-priv abstract class	BaseLinkedQueuePad1<E>
pack-priv abstract class	BaseLinkedQueuePad2<E>
pack-priv abstract class	BaseLinkedQueueProducerNodeRef<E>
pack-priv abstract class	BaseMpscLinkedArrayQueue<E> An MPSC array queue which starts at initialCapacity and grows to maxCapacity in linked chunks of the initial size.
pack-priv abstract class	BaseMpscLinkedArrayQueueColdProducerFields<E>
pack-priv abstract class	BaseMpscLinkedArrayQueueConsumerFields<E>
pack-priv abstract class	BaseMpscLinkedArrayQueuePad1<E>
pack-priv abstract class	BaseMpscLinkedArrayQueuePad2<E>
pack-priv abstract class	BaseMpscLinkedArrayQueuePad3<E>
pack-priv abstract class	BaseMpscLinkedArrayQueueProducerFields<E>
pack-priv abstract class	BaseSpscLinkedArrayQueue<E>
pack-priv abstract class	BaseSpscLinkedArrayQueueConsumerColdFields<E>
pack-priv abstract class	BaseSpscLinkedArrayQueueConsumerField<E>
pack-priv abstract class	BaseSpscLinkedArrayQueueL2Pad<E>
pack-priv abstract class	BaseSpscLinkedArrayQueuePrePad<E>
pack-priv abstract class	BaseSpscLinkedArrayQueueProducerColdFields<E>
pack-priv abstract class	BaseSpscLinkedArrayQueueProducerFields<E>
pack-priv abstract class	ConcurrentCircularArrayQueue<E> Common functionality for array backed queues.
pack-priv abstract class	ConcurrentCircularArrayQueueL0Pad<E>
pack-priv abstract class	ConcurrentSequencedCircularArrayQueue<E>
public class	IndexedQueueSizeUtil A note to maintainers on index assumptions: in a single threaded world it would seem intuitive to assume: `producerIndex >= consumerIndex`
pack-priv class	LinkedArrayQueueUtil This is used for method substitution in the LinkedArray classes code generation.
pack-priv class	LinkedQueueNode<E>
public class	MessagePassingQueueUtil
public class	MpmcArrayQueue<E> A Multi-Producer-Multi-Consumer queue based on a `io.netty.util.internal.shaded.org.jctools.queues.ConcurrentCircularArrayQueue`.
pack-priv abstract class	MpmcArrayQueueConsumerIndexField<E>
pack-priv abstract class	MpmcArrayQueueL1Pad<E>
pack-priv abstract class	MpmcArrayQueueL2Pad<E>
pack-priv abstract class	MpmcArrayQueueL3Pad<E>
pack-priv abstract class	MpmcArrayQueueProducerIndexField<E>
public class	MpmcUnboundedXaddArrayQueue<E> An MPMC array queue which grows unbounded in linked chunks.
pack-priv class	MpmcUnboundedXaddChunk<E>
public class	MpscArrayQueue<E> A Multi-Producer-Single-Consumer queue based on a `io.netty.util.internal.shaded.org.jctools.queues.ConcurrentCircularArrayQueue`.
pack-priv abstract class	MpscArrayQueueConsumerIndexField<E>
pack-priv abstract class	MpscArrayQueueL1Pad<E>
pack-priv abstract class	MpscArrayQueueL2Pad<E>
pack-priv abstract class	MpscArrayQueueL3Pad<E>
pack-priv abstract class	MpscArrayQueueMidPad<E>
pack-priv abstract class	MpscArrayQueueProducerIndexField<E>
pack-priv abstract class	MpscArrayQueueProducerLimitField<E>
public class	MpscBlockingConsumerArrayQueue<E> This is a partial implementation of the `java.util.concurrent.BlockingQueue` on the consumer side only on top of the mechanics described in `BaseMpscLinkedArrayQueue`, but with the reservation bit used for blocking rather than resizing in this instance.
pack-priv abstract class	MpscBlockingConsumerArrayQueueColdProducerFields<E>
pack-priv abstract class	MpscBlockingConsumerArrayQueueConsumerFields<E>
pack-priv abstract class	MpscBlockingConsumerArrayQueuePad1<E>
pack-priv abstract class	MpscBlockingConsumerArrayQueuePad2<E>
pack-priv abstract class	MpscBlockingConsumerArrayQueuePad3<E>
pack-priv abstract class	MpscBlockingConsumerArrayQueueProducerFields<E>
public class	MpscChunkedArrayQueue<E> An MPSC array queue which starts at initialCapacity and grows to maxCapacity in linked chunks of the initial size.
pack-priv abstract class	MpscChunkedArrayQueueColdProducerFields<E>
public class	MpscCompoundQueue<E>
pack-priv abstract class	MpscCompoundQueueColdFields<E>
pack-priv abstract class	MpscCompoundQueueConsumerQueueIndex<E>
pack-priv abstract class	MpscCompoundQueueL0Pad<E> Use a set number of parallel MPSC queues to diffuse the contention on tail.
pack-priv abstract class	MpscCompoundQueueMidPad<E>
public class	MpscGrowableArrayQueue<E> 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.
public class	MpscLinkedQueue<E> This is a Java port of the MPSC algorithm as presented on 1024 Cores by D.
public class	MpscUnboundedArrayQueue<E> An MPSC array queue which starts at initialCapacity and grows indefinitely in linked chunks of the initial size.
public class	MpscUnboundedXaddArrayQueue<E> An MPSC array queue which grows unbounded in linked chunks.
pack-priv class	MpscUnboundedXaddChunk<E>
pack-priv abstract class	MpUnboundedXaddArrayQueue<R extends MpUnboundedXaddChunk<R, E>, E> Common infrastructure for the XADD queues.
pack-priv abstract class	MpUnboundedXaddArrayQueueConsumerFields<R extends MpUnboundedXaddChunk<R, E>, E>
pack-priv abstract class	MpUnboundedXaddArrayQueuePad1<E>
pack-priv abstract class	MpUnboundedXaddArrayQueuePad2<E>
pack-priv abstract class	MpUnboundedXaddArrayQueuePad3<R extends MpUnboundedXaddChunk<R, E>, E>
pack-priv abstract class	MpUnboundedXaddArrayQueuePad5<R extends MpUnboundedXaddChunk<R, E>, E>
pack-priv abstract class	MpUnboundedXaddArrayQueueProducerChunk<R extends MpUnboundedXaddChunk<R, E>, E>
pack-priv abstract class	MpUnboundedXaddArrayQueueProducerFields<E>
pack-priv class	MpUnboundedXaddChunk<R, E>
public class	QueueFactory Deprecated The queue factory produces `java.util.Queue` instances based on a best fit to the `ConcurrentQueueSpec`.
public class	SpmcArrayQueue<E>
pack-priv abstract class	SpmcArrayQueueConsumerIndexField<E>
pack-priv abstract class	SpmcArrayQueueL1Pad<E>
pack-priv abstract class	SpmcArrayQueueL2Pad<E>
pack-priv abstract class	SpmcArrayQueueL3Pad<E>
pack-priv abstract class	SpmcArrayQueueMidPad<E>
pack-priv abstract class	SpmcArrayQueueProducerIndexCacheField<E>
pack-priv abstract class	SpmcArrayQueueProducerIndexField<E>
public class	SpscArrayQueue<E> A Single-Producer-Single-Consumer queue backed by a pre-allocated buffer.
pack-priv abstract class	SpscArrayQueueColdField<E>
pack-priv abstract class	SpscArrayQueueConsumerIndexField<E>
pack-priv abstract class	SpscArrayQueueL1Pad<E>
pack-priv abstract class	SpscArrayQueueL2Pad<E>
pack-priv abstract class	SpscArrayQueueL3Pad<E>
pack-priv abstract class	SpscArrayQueueProducerIndexFields<E>
public class	SpscChunkedArrayQueue<E> An SPSC array queue which starts at initialCapacity and grows to maxCapacity in linked chunks of the initial size.
public class	SpscGrowableArrayQueue<E> 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.
public class	SpscLinkedQueue<E> This is a weakened version of the MPSC algorithm as presented on 1024 Cores by D.
public class	SpscUnboundedArrayQueue<E> An SPSC array queue which starts at initialCapacity and grows indefinitely in linked chunks of the initial size.

Package io.netty.util.internal.shaded.org.jctools.queues

Interface Summary

Class Summary