Concurrency labs

3.10 Lab

Rules for every measurement

The rules of the earlier labs stand: predict first, release build, warm up, pin, performance governor, three runs, and p50, p99 and max, never a mean. This chapter adds three. Record the architecture (uname -m), and for every run the cores used and what they share: siblings, one L3, two L3s or two sockets, read from lscpu -e. Run loom tests in release mode, with RUSTFLAGS="--cfg loom" and LOOM_MAX_PREEMPTIONS at 2 or 3, and record how many executions each one explored. And if any AArch64 machine is within reach, run Lab 3.1 there as well; a small cloud instance is enough.

Lab 3.1 — message passing (ch03-concurrency/src/bin/message_passing.rs, tests/mp_loom.rs)

The binary has two modes. In message-passing mode, two threads are pinned to two cores that share an L3. The writer counts k from 1 to 100 million, storing data = k and then flag = k. The reader loops, loading flag and then data, and counts a stale read whenever data is less than the flag it just saw. --relaxed makes every access Relaxed; --release-acquire makes the store of flag Release and its load Acquire. In store-buffering mode, --sb, the two threads run 10 million rounds. In each round both wait at a spin barrier, then thread A stores x = 1 and loads y while thread B stores y = 1 and loads x, and the round counts if both loads returned 0. --sb runs with Release/Acquire and with SeqCst. The loom test models both patterns with two threads.

Reason it out. On x86-64, stores leave the buffer in order and loads appear in order, so message passing should show 0 stale reads in 100 million iterations in both variants, and cargo asm should show the two variants are the same instructions. Each iteration moves the two lines between the cores, so expect 20–100 ns an iteration, 2–10 s a run. On AArch64 the Relaxed variant can show stale reads, anywhere from none to thousands per 100 million depending on the core, and the Release/Acquire variant none. Store buffering is the case x86 does show. With Release/Acquire, expect rounds where both loads return 0, somewhere between one round in a thousand and one in a hundred thousand depending on how tightly the barrier lines the two threads up. With SeqCst, expect none, with each round 10–20 ns slower for the two xchgs; the barrier dominates a round, so expect 200–500 ns a round and 2–5 s a run. Under loom the Relaxed message-passing model should fail within the first few dozen executions, printing a trace in which flag is 1 and data is 0. The Release/Acquire model should pass after a few tens of executions, in well under a second.

Pitfalls. A zero on x86 is not evidence of correctness, and that is the lesson of the lab. Two siblings share an L1 and a core, so pick two physical cores. The barrier must spin: a std::sync::Barrier parks its threads, the two stores then land microseconds apart, and the reordering window is never hit. Under loom’s documented model, SeqCst loads and stores are treated as AcqRel, so the direct SeqCst store-buffering model can report an outcome real SeqCst forbids; model it with fence(SeqCst) between each store and load, which loom does handle. Write down the stale reads per 100 million for each variant and architecture, the both-zero rounds per million for each store-buffering variant, the nanoseconds per iteration and per round, and loom’s execution counts.

Lab 3.2 — contended counter (ch03-concurrency/src/bin/counter.rs)

Four threads are pinned to four physical cores that share an L3, and each performs 10 million increments. --mutex shares one Arc<Mutex<u64>>. --atomic shares one AtomicU64 and calls fetch_add(1, Relaxed). --per-thread gives each thread its own padded counter with a single writer, bumped with a load and a store. --per-thread-rmw gives each its own padded counter bumped with fetch_add. --unpadded gives each its own counter, bumped with fetch_add, but packs the four side by side in one struct. The binary prints the wall time, the nanoseconds per increment (wall time divided by 40 million), and each thread’s finish time. Run --mutex again under strace -f -c -e trace=futex and perf stat -e context-switches.

Reason it out. --per-thread is a load and a store to a line the core owns, with store-to-load forwarding making each increment a chain of about 5 cycles: 1–2 ns, so 10–20 ms for 10 million, with the four threads running in parallel. --per-thread-rmw costs a locked instruction each, about 5 ns: 50 ms. --atomic puts 40 million increments on one line. Each needs ownership, and a core often gets a few done before it loses the line, so expect 15–50 ns per increment overall. That is throughput, the wall time divided by 40 million, not the latency of one increment, which the ladder puts at 50–300 ns: the four cores’ waits overlap, and each often does a few increments per ownership. In total, 0.6–2 s, 30–100 times --per-thread. --unpadded should land in the same range as --atomic, because the counters are separate and the line is not. --mutex pays two locked instructions per increment on a line that bounces, plus the slow path whenever a thread outlasts its spin. Expect 2–10 times --atomic, 2–10 s, with hundreds of thousands to millions of futex calls and context switches to match. Expect uneven finish times too: with an unfair lock, the first thread can finish in half the time of the last.

Pitfalls. A per-thread counter kept in a plain local variable is folded by the compiler into one addition at the end, so use the atomic or std::hint::black_box. Two threads on siblings halve the real cores. The mutex numbers vary more from run to run than the others, so take all three runs seriously. Spreading the four threads across two sockets multiplies the --atomic and --mutex times by two or three. Write down the wall time, nanoseconds per increment and ratio to --per-thread for each variant, and the futex count for --mutex.

Lab 3.3 — ping-pong (ch03-concurrency/src/bin/pingpong.rs)

Two threads share one padded AtomicU64. Thread A stores an odd value and spins until it sees the next even one; thread B spins until it sees an odd value and replies with the next even one. After warm-up, A times a million round trips with rdtsc and reports p50, p99 and max in nanoseconds. Run it for two siblings, two cores sharing an L3, two cores on different L3s of one socket if the part has them, and two sockets if the box has them. --matrix runs every pair of cores and prints the p50 of each.

Reason it out. Each round trip moves the line twice, once each way. Two siblings keep the line in their shared L1, so expect tens of nanoseconds a round trip, the cost of the store buffer and the pipeline rather than of a transfer. Two cores sharing an L3 on a client part’s ring or inside one AMD core complex take 25–40 ns a hop, 50–80 ns a round trip; on a server part’s mesh, 50–80 ns a hop, 100–160 ns a round trip. Two L3s on one socket take 80–120 ns a hop, 160–240 ns a round trip. Two sockets take 120–250 ns a hop, 250–500 ns a round trip. On a quiet pinned box the p99 should sit within 10–20% of the p50, and the max should show the 1–5 µs of a timer tick unless the cores are isolated. The matrix should come out in blocks: low values for pairs inside one L3, a higher plateau between L3s, and the highest between sockets.

Pitfalls. spin_loop compiles to pause, which takes about 140 cycles on Intel parts since Skylake-SP and so can add up to 35 ns a hop; run with and without it. Read rdtsc on one thread only, so that the two ends of every interval come from the same core’s clock. Make sure the two threads really are where you think: taskset or sched_setaffinity, checked with ps -eLo tid,psr,comm. Write down p50, p99 and max for each placement, and the ratio of the two-socket p50 to the one-L3 p50.

Lab 3.4 (stretch) — a 16-slot ring checked with loom (ch03-concurrency/src/spsc.rs, tests/spsc_loom.rs)

Require N to be a non-zero power of two, and validate that capacity fits the counter arithmetic. Write Ring<const N: usize> with N slots of UnsafeCell<MaybeUninit<u64>>, where MaybeUninit is storage that may not hold a valid value yet and must not be read until it has been written. Give it two AtomicU64 counters, head and tail, and try_push and try_pop following the protocol in section 3.8. Expose separate, non-cloneable producer and consumer handles so safe callers cannot create a second writer or reader; any unsafe impl Sync relies on that API invariant, the full/empty checks and both ordering pairs. A small module re-exports the atomic and cell types from loom under cfg(loom) and from std otherwise. The loom test runs a producer that pushes 1 to K, retrying when the ring is full, and a consumer that pops K items and asserts they arrive as 1 to K. Run it with N = 2 and K = 3, then with N = 16 and K = 18 under LOOM_MAX_PREEMPTIONS=2. Then break the ring twice on purpose, once by making the store of head Relaxed and once by making the producer’s load of tail Relaxed, and run loom on each. Finally, without loom, push 100 million items through the 16-slot ring between two cores that share an L3.

Reason it out. With N = 2 and K = 3 the model reaches full, empty and wrap-around within a handful of operations; expect hundreds to a few thousand executions and a few seconds. N = 16 with K = 18 explores far more and takes minutes. Each broken version should fail within the first few hundred executions: loom checks that every access to one of its UnsafeCells is ordered by happens-before against every conflicting access, so the first fails on the consumer’s read of a slot the producer wrote, and the second on the producer’s write to a slot the consumer is still reading, which needs K greater than N to reach. The benchmark has 16 slots and no cached copies of the other side’s counter, so every push reads the tail line and every pop reads the head line, and the ring swings between full and empty. Expect 30–100 ns an item, 3–10 s for 100 million.

Pitfalls. loom’s UnsafeCell has with and with_mut methods that take closures instead of get, so the slot access goes through them. A model with too many items never finishes; start with N = 2. A loom pass covers only what the test drives, so a test with K no larger than N never wraps and proves nothing about the second pair. In the benchmark, put head and tail on separate padded lines, or the measurement is of false sharing. Write down the execution counts and times for both loom runs, which broken version failed and with what message, and the nanoseconds per item.