Click or drag to resize

ImperfectBlockingQueueT Class

ImperfectBlockingQueue is a blocking queue designed for very high performance exchanges between threads. Multiple readers and writers can exchange information using the ImperfectBlockingQueue. The design allows for a read node and a write node. Both the read node and write node are assumed to be probablistically incorrect at any given time. Specifically, that means that the read node may have actually been processed and the write node may not actually be the tail. Rather than attempting to correct for this imperfection in the data structure, we leverage it.

When a writer attempts to write to the tail, the tail uses an atomic compare-exchange to exchange the next node with the newly allocated node. If the exchange fails, the thread will iterate through the next member until it finds null and the cycle continue again with the atomic compare-exchange. Using this method, the writer will succeed in writing to the tail atomically. The write node does not need to accurately reflect the true end of tail, so adjusting the write node to the written node is "reasonably" accurate.

When a reader attempts to read from the head, an atomic compare exchange is used to test against the "IsProcessed" field of the node. If the node has been processed, then the reader moves on to the next node until it can successfully perform a CAS against the node. If none can be found, the method will force a sleep to simulate a block. Once found, the reader extracts the value for return and sets the head equal to the node just read. Again, since we're probablistic, this is fine. Since we've successfully read from the node, we're assured that all nodes before us have been processed. Being "reasonably" accurate with the read node is fine since the next reader will simply advance from this point.

This class was tested against various concurrent reader/writer models was equal to or outperformed all other models in all cases. However, it still appears that during tight iterations that there is about a 4-1 call ratio between CAS and the Push method which means there is still some efficiency to be squeezed out.

Inheritance Hierarchy
SystemObject
  com.espertech.esper.compat.collectionsImperfectBlockingQueueT

Namespace:  com.espertech.esper.compat.collections
Assembly:  NEsper.Compat (in NEsper.Compat.dll) Version: 8.0.0.0
Syntax
C#
public sealed class ImperfectBlockingQueue<T> : IBlockingQueue<T>

Type Parameters

T

The ImperfectBlockingQueueT type exposes the following members.

Constructors
  NameDescription
Public methodImperfectBlockingQueueT
Initializes a new instance of the ImperfectBlockingQueueT class.
Public methodImperfectBlockingQueueT(Int32)
Initializes a new instance of the ImperfectBlockingQueueT class.
Top
Properties
  NameDescription
Public propertyCount
Gets the number of items in the queue.
Top
Methods
  NameDescription
Public methodClear
Clears all items from the queue
Public methodIsEmpty
Public methodPop
Pops an item off the queue. If there is nothing on the queue the call will pend until there is an item on the queue.
Public methodPop(Int32, T)
Pops an item off the queue. If there is nothing on the queue the call will pend until there is an item on the queue or the timeout has expired. If the timeout has expired, the method will return false.
Public methodPush
Pushes an item onto the queue. If the queue has reached capacity, the call will pend until the queue has space to receive the request.
Top
See Also