SPSC capacity, padding, and cached counters

5.6 Passing between threads: the SPSC ring buffer

Every update the feed thread on core 2 decodes must reach the strategy thread on core 3, every one and in order, without either thread stopping for the other, and Chapter 3’s ring is what carries them. A ring buffer is a fixed array used as a circle, the slot after the last being the first, so that one allocation made at startup carries an endless stream while the reader stays within N items of the writer. That ring has N slots and two counters that only grow: head, the items written, stored only by the producer, and tail, the items read, stored only by the consumer. With a single producer and a single consumer, SPSC for short, each counter has one writer, and no lock or read-modify-write is needed. The producer writes a slot and then stores head with Release; the consumer loads head with Acquire and then reads the slot, so it sees the whole item. A second pair runs back the other way, the consumer’s Release store of tail after its read and the producer’s Acquire load of tail before its write, so that no slot is overwritten while still being read:

The protocol settles the ordering and nothing else, and the 16-slot ring built on it as a lab, which read the other side’s counter on every item, with no cached copies, passed an item in 30–100 ns. This section keeps the ordering exactly and adds the four things it left for later: a capacity that makes the slot index one instruction, counters that do not share a cache line, copies of the other side’s counter that spare a line transfer on almost every item, and batching.

Capacity: a power of two

The slot for count c is c mod N, and computing it is the first cost. With a capacity known only at run time, c % n is a div instruction, 20–40 cycles on every push and pop, as much as all the rest of a push. When N is a power of two, 2^k, the remainder is the low k bits of c, and masking keeps them: c & (N - 1), one AND, 1 cycle. For N = 4,096 the mask is 4,095, twelve one-bits, and count 1,000,005 lands in slot 581, as 1,000,005 mod 4,096 would. For a constant N the optimiser already makes % N that AND when N is a power of two, and a multiply and shifts of a few cycles otherwise; the ring writes the mask itself so that nothing depends on the optimiser noticing. A const block makes the rule unbreakable: const { assert!(N.is_power_of_two()) } in ring() is evaluated by the compiler for each N used, and ring::<Update, 3000>() fails to compile with “ring capacity must be a power of two”.

The counters are monotonic: they count items from the start of the run and only grow, and the slot is derived from them by the mask, never stored. A u64 advanced a billion times a second takes 2^64 / 10^9 seconds, 584 years, to wrap, so in practice it never does. Counting rather than indexing also makes full and empty different conditions: empty when head == tail, full when head - tail == N. A ring that kept slot indices from 0 to N − 1 would find them equal in both cases, and would have to leave one slot unused, or keep a flag, to tell the two apart.

Padding: head and tail on their own lines

Coherence moves whole 64-byte lines, not variables, so two values written by two cores in one line send it back and forth on every write though neither core reads the other’s value: false sharing, as Chapter 1 measured it. The ring invites it. The producer writes head on every push and the consumer tail on every pop, and two AtomicU64s declared side by side sit in one line, so every push must take the line from the consumer’s cache before it can store, and every pop take it back: 50–100 ns on every push and every pop, whatever either side reads. Nothing on the reading side helps, because the cost is in the writes.

The cure is layout. #[repr(align(64))] struct Padded(AtomicU64) makes the wrapper start on a 64-byte boundary, and since a type’s size is always a multiple of its alignment, it is 64 bytes long and nothing else can share its line. Rust may order Ring’s fields as it likes, but each Padded fills a whole line, so in any order head, tail and the pointer to the slots lie on three lines, the third written once at construction and only read after. The crossbeam-utils crate’s CachePadded<T> does the same for any T but pads to 128 bytes on x86-64, two lines, because Intel’s adjacent-line prefetcher fetches lines in pairs and so can couple two neighbours that never share a line.

Padding does nothing about the slots, and nothing can. Each slot is written by the producer and read by the consumer, so its line must cross: true sharing, the data itself, the one transfer the ring exists to make. With 32-byte Updates, two to a line, a slot line crosses once when the consumer reads it after the producer has filled it. The producer’s next write to it, a lap of N items later, only takes ownership back, a wait absorbed by its store buffer, the queue that lets a core run on before its stores complete. A consumer reading right behind the producer, item by item, can pull a line across for each of its two updates, which batching avoids.

Cached copies of the other side’s counter

With the counters apart, the protocol still crosses a line on every item, both ways. A push first loads tail, which the consumer has probably just stored, so the load misses and fetches the consumer’s line, 50–100 ns; a pop first loads head, just stored by the producer, another transfer. Neither load needs an exact value. The producer needs only to know there is room, and since tail only grows, an old value of it can only understate the room: if an old copy says there is space, there is. So the producer keeps cached_tail, a plain u64 in its own struct, and checks room against that; only when the copy says full does it load the real tail with Acquire, keep the value, and check again. The consumer does the same with cached_head, since an old head can only understate the items waiting. The orderings are untouched: every value in a copy came from an Acquire load of what a Release store wrote, and carries that pair’s guarantee for as long as it is used.

In steady state, then, a push reads and writes only lines the producer owns: its own struct with cached_tail, the slot, and head, which it alone stores and so reads back with Relaxed. How rarely a copy is refreshed depends on which side is ahead. A producer feeding a consumer that keeps up finds the ring nearly empty at each refresh, so the new copy allows almost N more pushes: about one load of tail per 4,096 pushes in a 4,096-slot ring. The consumer gains less in that steady state, because a consumer that has caught up must look at head to see anything new, and the look is the transfer that brings the news. What it gains is that one look covers every item queued behind it.