Core Concepts¶

The conceptual foundation for the rest of the guide: bounded vs unbounded queues, lock-free vs wait-free progress guarantees, the SPSC / SPMC / MPSC / MPMC quadrant, and how capacity and segments work under the hood.

Read this once, then return to the topic-specific guides as needed.

Bounded vs Unbounded¶

When you know the upper bound¶

A bounded queue has a fixed compile-time capacity N. The queue allocates its storage once, never grows, and rejects further pushes when full (push returns false). This is the right choice when your traffic has a known ceiling — an audio buffer at 64 samples, an HTTP worker pool with 256 in-flight requests, a sensor pipeline at 1 kHz with a 100 ms tolerance.

Bounded queues are wait-free for SPSC and lock-free for the contended multi-thread variants. No allocation happens during operation. Memory cost is exactly N * sizeof(T) plus a few cache-line-aligned counters.

When you don't¶

An unbounded queue grows segment by segment. Push always succeeds (until the allocator runs out). The cost is per-segment allocation when the current segment fills, and — for the multi-cardinality unbounded shapes (any arm with a multi producer or multi consumer) — DEBRA epoch-based reclamation to free retired segments safely under contention.

Pick unbounded when bursts can dwarf the steady-state rate (log aggregation across hundreds of producers, event collection during a load test, work scheduling where you would rather grow memory than drop work).

Backpressure semantics¶

A bounded queue full means push returns false. Whether you retry, sleep, or drop is application policy. An unbounded queue has no "full" — backpressure has to come from somewhere else (rate limiting at the producer, monitoring on segment count, OOM as a last resort).

For the full decision guide, see Bounded vs Unbounded.

Lock-Free vs Wait-Free¶

Per-operation guarantees¶

Two progress guarantees, in increasing strength:

Lock-free: at least one thread makes progress on every step of the algorithm. Individual threads may retry their CAS loop indefinitely, but the system as a whole never stalls. A preempted thread cannot stop others.
Wait-free: every thread completes its operation in a bounded number of steps, regardless of what other threads are doing. The strongest progress guarantee available without locks.

Mutex-based code is neither. A holder that gets preempted while holding the lock blocks every other thread until it is rescheduled.

Where lockfreequeues sits¶

Cardinality shape	push	pop
bounded SPSC (`newSpscQueue`)	wait-free	wait-free
bounded SPMC (`newSpmcQueue`)	wait-free	lock-free
bounded MPSC (`newMpscQueue`)	lock-free	wait-free
bounded MPMC (`newMpmcQueue`)	lock-free	lock-free
unbounded SPSC (`newUnboundedSpscQueue`)	wait-free	wait-free
unbounded SPMC (`newUnboundedSpmcQueue`)	wait-free	lock-free
unbounded MPSC (`newUnboundedMpscQueue`)	lock-free	wait-free
unbounded MPMC (`newUnboundedMpmcQueue`)	lock-free	lock-free

The single-cardinality side of each shape (the single-producer or single-consumer end) is wait-free because there is no CAS contention — only one thread races for that cursor. The contended (multi) sides use a CAS loop and are lock-free.

For the slot-level state machine that backs push and pop, see Slot Ownership Typestates. For the broader thread-safety contract, see Safety Model.

SPSC / SPMC / MPSC / MPMC quadrant¶

The four producer/consumer patterns and the queue type that implements each.

One-table summary¶

Producers	Consumers	Bounded constructor	Unbounded constructor
1	1	`newSpscQueue`	`newUnboundedSpscQueue`
1	many	`newSpmcQueue`	`newUnboundedSpmcQueue`
many	1	`newMpscQueue`	`newUnboundedMpscQueue`
many	many	`newMpmcQueue`	`newUnboundedMpmcQueue`

In v5 every shape is one of two unified generics: bounded queues are BQueue[T, ccProd, ccCons, N, P, C] and unbounded queues are Queue[T, ccProd, ccCons, ST, S, MaxThreads]. The cardinality is carried by the ccProd / ccCons parameters (ccSingle or ccMulti); the smart constructors above are thin wrappers that pick the right cardinality pair for you. The constructor names stay mnemonic: Single vs Multiple, producer, single vs multiple, consumer. newSpscQueue = Single-producer / Single-consumer; newMpmcQueue = Multi-producer / Multi-consumer.

For the full API reference, see the API pages: Bounded Queue (BQueue) and Unbounded Queue (Queue).

When to pick which¶

The choice is made by counting threads, not by guessing which queue is "fastest". A queue used incorrectly — say, two producer threads sharing a single-producer (ccSingle) queue — has undefined behaviour.

One producer, one consumer: use newSpscQueue. Wait-free both sides; lowest per-op cost in the library.
One producer, many consumers (fan-out): use newSpmcQueue. The producer side stays wait-free; consumers race a CAS to claim a slot.
Many producers, one consumer (fan-in, the most common server pattern): use newMpscQueue. Producers race; consumer is wait-free.
Many on both sides: use newMpmcQueue. Both sides race.

If your producer or consumer count is "1 most of the time but occasionally 2", you still need the multi-cardinality variant. The library cannot detect at runtime that you are temporarily violating the contract.

Why MPMC is more expensive than SPSC¶

Every additional contended side adds a CAS loop and a per-slot sequence counter. The SPSC shape writes the item, then advances a single tail cursor with a release store — no CAS. The MPMC shape has to publish the item with a release store, advance the tail with a CAS that may lose to other producers, and do the same dance on the consumer side. Under contention, retries multiply.

The published Benchmarks page shows the empirical gap; expect ~3-5× difference between SPSC and uncontended MPMC, growing with producer count.

Capacity, segments, and rollover¶

Bounded ring buffer model¶

A bounded queue is a flat array of N slots plus head and tail cursors. Producers advance the tail, consumers advance the head, and both wrap modulo N (or N + 1 for the SPSC shape, which uses one extra slot to distinguish full from empty without a separate count field).

import options
import lockfreequeues

# Capacity 8: 8 slots usable, plus 1 sentinel for SPSC.
var queue = newSpscQueue[int, 8]()

discard queue.push(1)
discard queue.push(2)
echo queue.capacity()  # 8
echo queue.pop()       # Some(1)

When the tail catches the head (queue full) push returns false. When the head catches the tail (queue empty) pop returns none. Generation rollover for the multi-producer / multi-consumer bounded shapes is handled by Vyukov per-slot sequence counters — see Slot Ownership Typestates → Publication Protocol for the protocol that makes wraparound races structurally impossible.

Unbounded segment-list model¶

An unbounded queue is a singly-linked list of segments, where each segment is a fixed-size array of S slots. Producers fill the current tail segment until it is exhausted, then atomically link a freshly allocated segment and continue. Consumers drain the head segment until it is empty, then advance to the next segment and (for the multi-cardinality shapes) hand the retired segment to DEBRA for safe reclamation.

import options
import lockfreequeues

# Segment size 64 — each segment holds 64 ints. `stEager` is the
# deallocation strategy; the trailing 4 is the debra registry capacity
# (a type-uniform phantom for the SPSC shape, which carries no debra).
# The queue grows segment-by-segment as load demands.
var queue = newUnboundedSpscQueue[int, stEager, 64, 4]()
var producer = queue.getProducer()

producer.push(1)
producer.push(2)
echo queue.segmentCount()  # 1 (no overflow yet)
echo queue.pop()           # Some(1)

Segment size S is the granularity of allocation: small S means more allocations under sustained load, large S means more wasted memory at low load. See Bounded vs Unbounded → Segment size selection for the trade-off.