SPSC ring buffer

Deep dive

How it works

In: one item to push (producer thread) or a pop request (consumer thread) · Out: pushed, or full; the oldest item, or empty · State: a power-of-two array, tail (producer-owned) and head (consumer-owned), each on its own cache line · Cost: O(1) wait-free, no atomic read-modify-write; order of 40-100 ns per cache-line transfer between cores

 head (consumer)        tail (producer)
     v                      v
 [ . | A | B | C | D | . | . | . ]     size = tail - head, cap = 8

1. Push: if tail - head_cache == cap, refresh head_cache = head.load(Acquire); still full → fail. Write the slot, then tail.store(tail+1, Release).
2. Pop: if head == tail_cache, refresh tail_cache = tail.load(Acquire); still empty → fail. Read the slot, then head.store(head+1, Release).
3. Release on tail makes the slot write visible before the new tail; acquire on the consumer side pairs with it. Symmetrically, release on head guarantees the consumer finished reading a slot before the producer reuses it.

Code

use std::cell::UnsafeCell;
use std::mem::MaybeUninit;
use std::sync::atomic::{AtomicUsize, Ordering::{Acquire, Release}};
use std::sync::Arc;

#[repr(align(128))] // 128: Apple M-series lines and Intel adjacent-line prefetch
struct Pad<T>(T);

struct Shared<T> {
    head: Pad<AtomicUsize>, // next slot to read; written only by the consumer
    tail: Pad<AtomicUsize>, // next slot to write; written only by the producer
    buf: Box<[UnsafeCell<MaybeUninit<T>>]>,
    mask: usize,
}
unsafe impl<T: Send> Send for Shared<T> {}
unsafe impl<T: Send> Sync for Shared<T> {}

pub struct Producer<T> { s: Arc<Shared<T>>, tail: usize, head_cache: usize }
pub struct Consumer<T> { s: Arc<Shared<T>>, head: usize, tail_cache: usize }

pub fn channel<T>(cap: usize) -> (Producer<T>, Consumer<T>) {
    let cap = cap.max(2).next_power_of_two();
    let buf = (0..cap).map(|_| UnsafeCell::new(MaybeUninit::uninit())).collect();
    let s = Arc::new(Shared { head: Pad(AtomicUsize::new(0)), tail: Pad(AtomicUsize::new(0)), buf, mask: cap - 1 });
    (Producer { s: s.clone(), tail: 0, head_cache: 0 }, Consumer { s, head: 0, tail_cache: 0 })
}

impl<T> Producer<T> {
    pub fn push(&mut self, v: T) -> Result<(), T> {
        let cap = self.s.mask + 1;
        if self.tail.wrapping_sub(self.head_cache) == cap {
            self.head_cache = self.s.head.0.load(Acquire); // consumer's reads of freed slots happen-before our writes
            if self.tail.wrapping_sub(self.head_cache) == cap { return Err(v); }
        }
        // SAFETY: slot is outside [head, tail), so the consumer does not touch it.
        unsafe { (*self.s.buf[self.tail & self.s.mask].get()).write(v); }
        self.tail = self.tail.wrapping_add(1);
        self.s.tail.0.store(self.tail, Release); // publish the slot
        Ok(())
    }
}

impl<T> Consumer<T> {
    pub fn pop(&mut self) -> Option<T> {
        if self.head == self.tail_cache {
            self.tail_cache = self.s.tail.0.load(Acquire); // pairs with the producer's Release
            if self.head == self.tail_cache { return None; }
        }
        // SAFETY: slot is inside [head, tail): initialized and owned by us until head moves.
        let v = unsafe { (*self.s.buf[self.head & self.s.mask].get()).assume_init_read() };
        self.head = self.head.wrapping_add(1);
        self.s.head.0.store(self.head, Release); // hand the slot back
        Some(v)
    }
}

impl<T> Drop for Shared<T> {
    fn drop(&mut self) { // both handles are gone: drop items still in the ring
        let (mut h, t) = (*self.head.0.get_mut(), *self.tail.0.get_mut());
        while h != t {
            unsafe { self.buf[h & self.mask].get_mut().assume_init_drop(); }
            h = h.wrapping_add(1);
        }
    }
}

Complexity and constants

• Uncontended push+pop on one core: a few ns. Cross-core, without index caching: every op misses on the other side's index line, order of 50-100 ns per op. With caching: amortized to one miss per "lap" of the ring plus the slot lines themselves.
• Slot data moves between cores too: 8-byte items = 8 per line, so one line transfer per 8 items.
• Round-trip latency (ping-pong) between two cores on one socket: order of 100-200 ns; across sockets or chiplets 2-3× more.
• On x86 acquire/release are plain movs; on ARMv8 they are ldar/stlr (or ldapr), still cheap.

Efficiency

• Cost: uncontended push+pop on one core takes a few ns. Across cores without index caching, each op misses on the other side's index line, order of 50-100 ns; with cached indices that is one miss per lap of the ring plus one line transfer per 8 eight-byte items. Ping-pong latency between two cores on one socket is order of 100-200 ns. Bound: cache-line transfer latency.
• Levers:
  • cache the other side's index privately — shared index line moves only when the ring looks full or empty (FastForward, Giacomoni et al. 2008) — always
  • batch: several slots per release store of tail — index traffic cut by the batch size (as in Implementation notes) — bursty producers
  • head, tail and buffer on separate cache lines — no false sharing — always
  • power-of-two capacity and free-running indices — & mask, no wasted slot — always
  • pin to separate physical cores — avoids SMT sibling effects that distort measurements — benchmarking and latency-critical threads
• Naive → standard → state of the art:
  • Mutex<VecDeque> · lock handoff, order of µs under contention
  • Lamport ring, acquire/release indices · wait-free, one index-line miss per op
  • cached indices plus batching · order of 100-500 M small items/s

Implementation notes

• Batching: write several slots, then one release store of tail; read tail once, consume all available, then one store of head. Cuts index-line traffic by the batch size.
• Blocking: spin a bounded number of iterations (with std::hint::spin_loop()), then park. To park safely set a "sleeping" flag, re-check the index after a SeqCst fence, then futex-wait/eventfd; the other side checks the flag after its store (also with a SeqCst fence). Missing either fence loses wakeups.
• Keep head, tail and the buffer on separate cache lines (the Pad above); otherwise producer and consumer false-share.
• For kernel-shared rings (io_uring), the same protocol is spelled smp_store_release/smp_load_acquire on the ring header indexes.
• Power-of-two capacity turns % cap into & mask; indices as free-running usize make full vs empty unambiguous without a wasted slot.

Pitfalls

• Relaxed store of tail: the consumer may see the new tail before the slot data (real on ARM; on x86 the compiler can still reorder).
• Reading head/tail with relaxed loads for the full/empty check and then touching the slot: same bug in the other direction.
• Sharing one handle between two threads (e.g. wrapping the producer in a Mutex per call is fine, cloning it is not); the type system above prevents cloning.
• Using cap non-power-of-two with wrapping indices: tail & mask breaks; use % cap and bounded indices then.
• Benchmarks that run producer and consumer on SMT siblings show unrealistically low latency; pin to separate physical cores to measure.

Variants and alternatives

In production

• Operating systems: Linux io_uring submission/completion rings (man page), virtio vrings (spec), Linux kfifo (lock-free for one reader and one writer).
• Networking: DPDK rte_ring in single-producer/single-consumer mode (guide).
• Audio: JACK jack_ringbuffer (source); real-time Rust crate rtrb.
• Finance and low-latency messaging: LMAX Disruptor (paper); Rust crate ringbuf.

Implementations

Sources

• Leslie Lamport, Specifying Concurrent Program Modules, ACM TOPLAS 5(2), 1983. paper
• John Giacomoni, Tipp Moseley, Manish Vachharajani, FastForward for Efficient Pipeline Parallelism: A Cache-Optimized Concurrent Lock-Free Queue, PPoPP 2008. paper
• Mara Bos, Rust Atomics and Locks, O'Reilly, 2023.
• LMAX, Disruptor: High performance alternative to bounded queues for exchanging data between concurrent threads, technical paper. paper