Designing around messages

3.9 Sharing by message

Each of the mechanism sections ended on what its mechanism costs. This section turns those costs into how a program’s threads are laid out, how data crosses between them, and how the result is checked, and ties each choice to the mechanism it answers. It is the only place in the chapter that reads as a list of things to do, and that is deliberate. The principle under all of it fits in one line: one writer per cache line, and share by message, not by memory.

How the threads are laid out

1. Each piece of mutable state has exactly one thread that writes it. A thread’s own counters, its own indices, its own buffers are written by that thread alone, and other threads read them or receive copies. Separate independently written values into different lines. One writer per value alone does not prevent false sharing, and even a single-writer line must regain ownership after readers acquire copies.
2. Each hot thread is pinned to a core of its own, and threads that hand data to each other are pinned to cores that share an L3. On one socket that is a transfer of 50–100 ns; between two L3s or two sockets it is two to three times that, on every hand-off. lscpu -e gives the L3 of every core, and the ping-pong matrix of Lab 3.3 confirms it. Hyperthread siblings share an L1 and would make transfers nearly free, but they also share the core’s execution units, so a hot thread’s sibling is left idle rather than given its partner.
3. No lock on the hot path. A lock’s uncontended cost is affordable; its contended cost is a wake-up of 5–200 µs, and a preempted holder’s is milliseconds, both landing in the tail. Locks stay where their simplicity is worth more than their tail: startup, configuration, the control path, anything that runs a few times a second.

How data crosses

1. A stream of items between two threads goes through a single-producer single-consumer ring: no CAS, no ABA, nothing to reclaim, and the producer’s Release on its write counter paired with the consumer’s Acquire. A thread with several inputs gets one ring per input and polls them in turn, instead of sharing one multi-producer queue whose tail every producer writes.
2. A value that many threads read and only the latest of which matters goes through a seqlock when it fits in a line or two, and through a snapshot pointer when it is larger and changes rarely. Never through an RwLock or an Arc clone on every read, because both make readers write a shared line.
3. Every independently written value sits on its own line. crossbeam_utils::CachePadded<T> aligns to 128 bytes on x86-64, AArch64 and powerpc64 (on x86 because the adjacent-line prefetcher pulls lines in pairs), to 256 on s390x, to 32 on some 32-bit targets, and to 64 elsewhere. The producer’s fields go together on one line and the consumer’s on another, so that each line has one writer.
4. Counters bumped by several threads become one counter per thread, each with a single writer, summed by whoever reads them. A counter with one writer can use a local increment and a relaxed atomic store for publication; concurrent readers still need atomic loads.

How the hand-offs are ordered

1. Every hand-off is a Release store paired with an Acquire load, and each pair is named in a comment at both ends. Relaxed is kept for values that order nothing, such as statistics and the single-writer counters above. SeqCst is kept for the rare case that needs a single total order, a thread that must see another’s store before it acts on its own, as in the two-flag pattern, and the comment says why. A design that avoids the two-flag pattern avoids the one ordering that costs on x86.
2. Each side of a ring keeps its own counter in a plain local variable and a cached copy of the other side’s, and reads the other side’s line only when the cached copy says the ring is full or empty. That keeps the cross-core reads to as few as the design allows.

How it is checked

1. Every structure that uses an ordering has a loom test, run with RUSTFLAGS="--cfg loom" in continuous integration, that drives it through full, empty and wrap-around with two or three threads.
2. The unit tests also run under Miri, which catches data races in the plain accesses around the atomics.
3. The test suite and the litmus tests of Lab 3.1 run on an AArch64 machine as well as on x86-64, because the x86 box cannot show three of the four reorderings.
4. perf c2c on a running system shows HITMs only on lines that were designed to be shared: ring counters, ring slots, seqlocks. A HITM anywhere else is a line with two writers, or a read that was not meant to cross.
5. strace -f -e trace=futex -c and perf trace -s show zero futex calls from the hot threads after warm-up, and their voluntary_ctxt_switches stay flat.

The table

Three caveats

Correctness is proved against the model, not measured. A structure that has run for a month on x86 under full load has been tested against one of the four reorderings, and against the compiler’s choices of that month.

Lock-free code is harder to write than locked code, and its bugs are rarer and worse. The proven crates, crossbeam for channels and CachePadded, rtrb for a single-producer single-consumer ring, are the default; a hand-written structure earns its place with its loom tests.

And all of it assumes each hot thread has a core to itself. A spinning consumer on a shared core is preempted like any other thread, and its producer then waits behind it exactly as it would behind a lock.