E
- public class SpscArrayQueue<E> extends SpscArrayQueueConsumerField<E> implements QueueProgressIndicators
This implementation is a mashup of the Fast Flow
algorithm with an optimization of the offer method taken from the BQueue algorithm (a variation on Fast
Flow), and adjusted to comply with Queue.offer semantics with regards to capacity.
For convenience the relevant papers are available in the resources folder:
2010 - Pisa - SPSC Queues on Shared Cache Multi-Core Systems.pdf
2012 - Junchang- BQueue- Efficient and Practical Queuing.pdf
This implementation is wait free.
MessagePassingQueue.Consumer<T>, MessagePassingQueue.ExitCondition, MessagePassingQueue.Supplier<T>, MessagePassingQueue.WaitStrategy
Modifier and Type | Field and Description |
---|---|
(package private) long |
p01 |
(package private) long |
p02 |
(package private) long |
p03 |
(package private) long |
p04 |
(package private) long |
p05 |
(package private) long |
p06 |
(package private) long |
p07 |
(package private) long |
p10 |
(package private) long |
p11 |
(package private) long |
p12 |
(package private) long |
p13 |
(package private) long |
p14 |
(package private) long |
p15 |
(package private) long |
p16 |
(package private) long |
p17 |
C_INDEX_OFFSET, consumerIndex
P_INDEX_OFFSET, producerIndex, producerLimit
lookAheadStep, MAX_LOOK_AHEAD_STEP
buffer, mask
UNBOUNDED_CAPACITY
Constructor and Description |
---|
SpscArrayQueue(int capacity) |
Modifier and Type | Method and Description |
---|---|
long |
currentConsumerIndex()
This method has no concurrent visibility semantics.
|
long |
currentProducerIndex()
This method has no concurrent visibility semantics.
|
int |
drain(MessagePassingQueue.Consumer<E> c)
Remove all available item from the queue and hand to consume.
|
int |
drain(MessagePassingQueue.Consumer<E> c,
int limit)
Remove up to limit elements from the queue and hand to consume.
|
void |
drain(MessagePassingQueue.Consumer<E> c,
MessagePassingQueue.WaitStrategy w,
MessagePassingQueue.ExitCondition exit)
Remove elements from the queue and hand to consume forever.
|
int |
fill(MessagePassingQueue.Supplier<E> s)
Stuff the queue with elements from the supplier.
|
int |
fill(MessagePassingQueue.Supplier<E> s,
int limit)
Stuff the queue with up to limit elements from the supplier.
|
void |
fill(MessagePassingQueue.Supplier<E> s,
MessagePassingQueue.WaitStrategy w,
MessagePassingQueue.ExitCondition e)
Stuff the queue with elements from the supplier forever.
|
private long |
lvConsumerIndex() |
private long |
lvProducerIndex() |
boolean |
offer(E e)
Called from a producer thread subject to the restrictions appropriate to the implementation and
according to the
Queue.offer(Object) interface. |
private boolean |
offerSlowPath(E[] buffer,
long mask,
long producerIndex) |
E |
peek()
Called from the consumer thread subject to the restrictions appropriate to the implementation and
according to the
Queue.peek() interface. |
E |
poll()
Called from the consumer thread subject to the restrictions appropriate to the implementation and
according to the
Queue.poll() interface. |
boolean |
relaxedOffer(E message)
Called from a producer thread subject to the restrictions appropriate to the implementation.
|
E |
relaxedPeek()
Called from the consumer thread subject to the restrictions appropriate to the implementation.
|
E |
relaxedPoll()
Called from the consumer thread subject to the restrictions appropriate to the implementation.
|
int |
size()
This method's accuracy is subject to concurrent modifications happening as the size is estimated and as
such is a best effort rather than absolute value.
|
private void |
soConsumerIndex(long v) |
private void |
soProducerIndex(long v) |
calcElementOffset, calcElementOffset, capacity, clear, iterator
contains, containsAll, isEmpty, remove, removeAll, retainAll, toArray, toArray, toString
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
isEmpty
long p01
long p02
long p03
long p04
long p05
long p06
long p07
long p10
long p11
long p12
long p13
long p14
long p15
long p16
long p17
public boolean offer(E e)
Queue.offer(Object)
interface.
This implementation is correct for single producer thread use only.
offer
in interface java.util.Queue<E>
offer
in interface MessagePassingQueue<E>
e
- not null, will throw NPE if it isprivate boolean offerSlowPath(E[] buffer, long mask, long producerIndex)
public E poll()
Queue.poll()
interface.
This implementation is correct for single consumer thread use only.
poll
in interface java.util.Queue<E>
poll
in interface MessagePassingQueue<E>
public E peek()
Queue.peek()
interface.
This implementation is correct for single consumer thread use only.
peek
in interface java.util.Queue<E>
peek
in interface MessagePassingQueue<E>
public int size()
MessagePassingQueue
size
in interface java.util.Collection<E>
size
in interface MessagePassingQueue<E>
size
in class java.util.AbstractCollection<E>
Integer.MAX_VALUE
but less or equals to
capacity (if bounded).private void soProducerIndex(long v)
private void soConsumerIndex(long v)
private long lvProducerIndex()
private long lvConsumerIndex()
public long currentProducerIndex()
QueueProgressIndicators
currentProducerIndex
in interface QueueProgressIndicators
public long currentConsumerIndex()
QueueProgressIndicators
currentConsumerIndex
in interface QueueProgressIndicators
public boolean relaxedOffer(E message)
MessagePassingQueue
Queue.offer(Object)
this method may return false without the queue being full.relaxedOffer
in interface MessagePassingQueue<E>
message
- not null, will throw NPE if it ispublic E relaxedPoll()
MessagePassingQueue
Queue.poll()
this method may return null without the queue being empty.relaxedPoll
in interface MessagePassingQueue<E>
public E relaxedPeek()
MessagePassingQueue
Queue.peek()
this method may return null without the queue being empty.relaxedPeek
in interface MessagePassingQueue<E>
public int drain(MessagePassingQueue.Consumer<E> c)
MessagePassingQueue
M m;
while((m = relaxedPoll()) != null){
c.accept(m);
}
There's no strong commitment to the queue being empty at the end of a drain. Called from a
consumer thread subject to the restrictions appropriate to the implementation.drain
in interface MessagePassingQueue<E>
public int fill(MessagePassingQueue.Supplier<E> s)
MessagePassingQueue
while(relaxedOffer(s.get());
There's no strong commitment to the queue being full at the end of a fill. Called from a
producer thread subject to the restrictions appropriate to the implementation.fill
in interface MessagePassingQueue<E>
public int drain(MessagePassingQueue.Consumer<E> c, int limit)
MessagePassingQueue
M m;
while((m = relaxedPoll()) != null){
c.accept(m);
}
There's no strong commitment to the queue being empty at the end of a drain. Called from a consumer
thread subject to the restrictions appropriate to the implementation.drain
in interface MessagePassingQueue<E>
public int fill(MessagePassingQueue.Supplier<E> s, int limit)
MessagePassingQueue
for(int i=0; i < limit && relaxedOffer(s.get(); i++);
There's no strong commitment to the queue being full at the end of a fill. Called from a producer
thread subject to the restrictions appropriate to the implementation.fill
in interface MessagePassingQueue<E>
public void drain(MessagePassingQueue.Consumer<E> c, MessagePassingQueue.WaitStrategy w, MessagePassingQueue.ExitCondition exit)
MessagePassingQueue
int idleCounter = 0;
while (exit.keepRunning()) {
E e = relaxedPoll();
if(e==null){
idleCounter = wait.idle(idleCounter);
continue;
}
idleCounter = 0;
c.accept(e);
}
Called from a consumer thread subject to the restrictions appropriate to the implementation.drain
in interface MessagePassingQueue<E>
public void fill(MessagePassingQueue.Supplier<E> s, MessagePassingQueue.WaitStrategy w, MessagePassingQueue.ExitCondition e)
MessagePassingQueue
int idleCounter = 0;
while (exit.keepRunning()) {
E e = s.get();
while (!relaxedOffer(e)) {
idleCounter = wait.idle(idleCounter);
continue;
}
idleCounter = 0;
}
Called from a producer thread subject to the restrictions appropriate to the implementation.fill
in interface MessagePassingQueue<E>