Bounded MPMC Queue

A lock-free, bounded, multi-producer multi-consumer (MPMC) queue in Rust using only std. Based on Dmitry Vyukov's classic bounded MPMC queue algorithm.

Design

Core data structure

The queue is a fixed-size circular buffer of slots, each containing an atomic sequence counter and the stored value:

┌──────────┬──────────┬──────────┬──────────┐
│ Slot 0   │ Slot 1   │ Slot 2   │ Slot 3   │  ← Box<[Slot<T>]>
│ seq: 4   │ seq: 5   │ seq: 2   │ seq: 3   │
│ val: ... │ val: ... │ val: ... │ val: ... │
└──────────┴──────────┴──────────┴──────────┘
                         ↑ head=2              ↑ tail=5 (wraps to slot 1)

Two cache-padded atomic counters track the next positions for consumers (head) and producers (tail). Cache-line padding (128 bytes) prevents false sharing between cores contending on head vs tail.

How it works (Vyukov's algorithm)

Each slot has an atomic sequence number that acts as a state machine:

Producing (try_push):

1. Read tail. Compute the target slot index (tail & mask).
2. Read the slot's sequence. If sequence == tail, the slot is writable.
3. CAS tail from its current value to tail + 1. If the CAS fails, another producer won — retry.
4. Write the value into the slot.
5. Store sequence = tail + 1 (Release), signalling consumers.

Consuming (try_pop):

1. Read head. Compute the target slot index (head & mask).
2. Read the slot's sequence. If sequence == head + 1, the slot is readable.
3. CAS head from its current value to head + 1. If the CAS fails, another consumer won — retry.
4. Read the value out of the slot.
5. Store sequence = head + capacity (Release), freeing the slot for the next lap of producers.

If the sequence check shows the slot isn't ready (full for producers, empty for consumers), try_push/try_pop returns immediately. The blocking push/pop variants retry with exponential backoff (spin-loop hint → thread yield).

Why this works

The CAS on tail/head ensures exactly one thread wins each slot. The sequence counter acts as a handoff: a producer sets it to tail + 1 only after writing, and a consumer sets it to head + capacity only after reading. No two threads ever access a slot's value concurrently.

Capacity constraint

Capacity is rounded up to the next power of two (minimum 2) so that index & mask replaces the modulo operation. A minimum of 2 is enforced because with capacity=1 the "readable" and "next-writable" sequence numbers for the same slot collide.

unsafe usage

There are 4 uses of unsafe, each justified:

Location	Reason
CachePadded::new	Initialises padding bytes to zero via raw pointer writes. Padding is never read as meaningful data.
try_push — slot value write	Writes to UnsafeCell<MaybeUninit<T>> after the producer won the CAS on tail, guaranteeing exclusive access.
try_pop — slot value read	Reads from UnsafeCell<MaybeUninit<T>> after the consumer won the CAS on head, guaranteeing exclusive access and that the value was previously written.
Drop — draining remaining items	Drops unconsumed items between head and tail. Called with &mut self so no concurrent access is possible.

API

pub trait BoundedQueue<T: Send>: Send + Sync {
    fn new(capacity: usize) -> Self;
    fn push(&self, item: T);         // blocks if full
    fn pop(&self) -> T;              // blocks if empty
    fn try_push(&self, item: T) -> Result<(), T>;  // non-blocking
    fn try_pop(&self) -> Option<T>;                 // non-blocking
}

Running

# Tests (12 tests: single-threaded, concurrent, stress, blocking, drop safety)
cargo test

# Benchmarks (symmetric + asymmetric throughput across thread counts and capacities)
cargo bench --bench throughput

Project layout

src/lib.rs                  Queue trait, implementation, and tests
benches/throughput.rs       Throughput benchmarks
BENCHMARK_RESULTS.md        Recorded benchmark numbers and analysis