the SPSC ring buffer (and MPMC)
/ ES-PEE-ES-SEE /
Often you do not need a fully general queue that anyone can push to from anywhere — you have exactly one thread producing items and exactly one thread consuming them, like an audio thread feeding samples to the sound card. For this special case there is a beautifully simple and fast structure: the single-producer, single-consumer (SPSC) ring buffer. It is a fixed-size array used circularly, and it can be made lock-free with no CAS at all.
Here is the trick. You keep a head index (where the consumer reads) and a tail index (where the producer writes), both wrapping around the array modulo its size — usually a power of two so wrapping is a cheap bit mask, index & (N - 1), instead of a division. The producer only ever writes the tail; the consumer only ever writes the head. Because each index has exactly one writer, you never need compare-and-swap — a plain atomic store with release ordering and a plain atomic load with acquire ordering is enough to publish each item safely. The buffer is full when advancing tail would collide with head, and empty when head equals tail. That single-writer-per-index property is the whole reason SPSC is so cheap and so easy to get right.
The contrast is the multi-producer, multi-consumer (MPMC) ring buffer, where many threads share each index. Now you are back to needing CAS to claim a slot, and you must handle two threads racing for the same index, partially written slots, and wrap-around hazards — it is dramatically harder, and high-quality MPMC queues (such as Dmitry Vyukov's bounded MPMC queue) use a per-slot sequence number to coordinate. The family also includes SPMC and MPSC. The honest lesson is to use the weakest variant that fits: if your problem is truly SPSC, do not pay for MPMC.
/* SPSC: one writer per index means no CAS, just release store / acquire load. */ bool push(T v) { /* producer only */ size_t t = tail; /* relaxed: we are the only writer of tail */ if (((t + 1) & (N - 1)) == atomic_load_acquire(&head)) return false; /* full */ buf[t] = v; atomic_store_release(&tail, (t + 1) & (N - 1)); /* publish */ return true; }
With a power-of-two size, wrap-around is a bit mask; with one writer per index, a release store is enough to publish — no CAS needed.
SPSC needs no CAS precisely because each index has a single writer; the moment you have multiple producers or consumers you need CAS (or per-slot sequence numbers) and the difficulty jumps sharply.