Class CQueue<T>

java.lang.Object
io.perl.api.impl.CQueue<T>
Type Parameters:
T - queued element type
All Implemented Interfaces:
Queue<T>
public final class CQueue<T> extends Object implements Queue<T>
An unbounded, non-blocking multiple-producer, single-consumer (MPSC) queue.

Concurrency model

Any number of producer threads may call add(Object). Exactly one consumer thread owns poll() and clear(). A producer allocates one node, walks forward from the producer tail when that hint lags, and publishes the node by comparing and setting the last node's next reference. That successful compare-and-set is the enqueue linearization point. A best-effort tail update reduces later traversal but is not required for correctness.

The consumer reads the successor of its thread-confined head with acquire semantics, clears the successor's item, and advances the head without a compare-and-set. Publication through the producer's compare-and-set and the consumer's acquire read establishes visibility of the queued element. Per-producer order and the global order of successful link operations are preserved. Empty poll() calls return null; consequently null elements are rejected.

Why it can be faster than the JDK queue

This class deliberately implements only the operations required by PerL. Unlike ConcurrentLinkedQueue, it does not support multiple consumers, iterators, interior removal, size traversal, or bulk collection operations. The sole consumer therefore avoids the item compare-and-set and concurrent-head compare-and-set required by a multi-consumer queue. Separately padded head and tail holders reduce false sharing between consumer and producer cache lines. Use ./gradlew :perl:cqueuePerformanceTest to run the JDK 25 JMH comparison; results are host-specific.

Allocation and garbage collection

Every successful enqueue allocates one Node, just as JDK 25 ConcurrentLinkedQueue does. The consumer clears the item reference before advancing the head, so a consumed node does not retain the user's payload. Under normal producer progress, retired predecessor nodes become unreachable as the consumer advances. The padded head and tail objects add constant per-queue memory overhead, not per-element overhead.

Retired heads are self-linked in batches of 16. A producer that was suspended while holding a retired node detects the self-link and restarts from a release-published recovery head. Batching amortizes the extra retirement store while bounding the chain retained by a stale producer cursor. JDK 25 ConcurrentLinkedQueue still provides the stronger general-purpose reclamation implementation because it also handles iterators, multiple consumers, and interior dead-node removal. PerL's production queue array currently uses that JDK queue; CQueue is intended for controlled MPSC deployments where lower coordination cost is the priority.

Usage constraints

  • Do not call poll() or clear() from more than one thread, concurrently or sequentially without external ownership transfer.
  • Do not enqueue null.
  • Apply external backpressure if an unbounded producer backlog is not acceptable.

  • Constructor Summary

    Constructors
    Constructor
    Description
    CQueue()
    Creates an empty MPSC queue with one sentinel node.

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    add(T data)
    Add data of type T to queue.
    void
    clear()
    Clear queue and reset internal state.
    T
    poll()
    Return data of type T from queue, or null if none is available.

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • CQueue

      public CQueue()
      Creates an empty MPSC queue with one sentinel node.

  • Method Details

    • poll

      public T poll()
      Description copied from interface: Queue
      Return data of type T from queue, or null if none is available.
      Specified by:
      poll in interface Queue<T>
      Returns:
      next element, or null when the queue is empty

    • add

      public boolean add(T data)
      Description copied from interface: Queue
      Add data of type T to queue.
      Specified by:
      add in interface Queue<T>
      Parameters:
      data - element to add to the queue
      Returns:
      true if the element was added successfully

    • clear

      public void clear()
      Description copied from interface: Queue
      Clear queue and reset internal state.
      Specified by:
      clear in interface Queue<T>