One thread cannot both read the socket and run the strategy without one of them waiting. So you add a second — and the instant two threads touch the same bytes, correctness stops being obvious. Neither the compiler nor the CPU is on your side; the only thing that is, is the happens-before relation, and you have to build it by hand.
relaxed / acquire / release / seq_cst per operation and defend the choice with a happens-before argument.on_book path — graded
Two threads access the same memory location, at least one of them writes, and nothing in the program orders the two accesses. That is the definition, and the consequence is not a wrong value — it is undefined behaviour, which is a much stronger and much worse claim.
The distinction matters because people reason about races as if the hardware simply interleaves their source lines. It does not. The compiler reorders loads and stores of non-atomic data freely, as long as a single-threaded observer could not tell — it may hoist your shared variable into a register for the whole loop and write it back once, deleting every intermediate value another thread might have seen. The CPU reorders too: store buffers, out-of-order execution and the cache-coherency protocol let a core make its writes visible in an order it did not issue them.
Both layers preserve single-threaded semantics perfectly. The illusion only breaks when a second thread looks — which is why a race can pass every test on your laptop, hold under light load, and then produce a number that no interleaving of your source code could ever produce.
Start with the concrete version. ++counter is not one operation; it is a load, an add and
a store, and two threads can interleave between any of them:
long counter = 0; // shared, unsynchronised -> UB void work() { for (int i = 0; i < 1000000; ++i) ++counter; } int main() { std::thread a(work), b(work); a.join(); b.join(); std::printf("counter = %ld (expected 2000000)\n", counter); } // Run it three times: three different answers, all below 2 000 000. // That non-determinism is the signature. Now build it under TSan: // clang++ -std=c++20 -O1 -g -pthread -fsanitize=thread race.cpp // and the tool names it: WARNING: ThreadSanitizer: data race
volatile does not fix this. It means "do not cache this in a
register, do not optimise the access away" — it says nothing about atomicity and nothing about
inter-thread ordering. Rebuild the loop with volatile long counter under TSan and the race
is still reported. volatile is for memory-mapped I/O; it has never been a threading tool
in C++.Four numbers, four orders of magnitude. Every decision in this week's material is a choice between them, and the tail of your tick-to-trade is decided by how often you land on the last one.
Two threads, one shared counter, three micro-operations each:
LOAD, ADD, STORE. You choose who steps next. Find the interleaving
that loses an update — then find the ones that do not, and notice how few of them there are.
STORE precedes B's
LOAD or vice versa. Scale that to a million increments each and the probability that every
single one of them happens to be ordered is indistinguishable from zero — which is why the final count is
always short, and short by a different amount each run.std::atomic does two separable jobs: it makes an operation indivisible, and it
gives you a knob for cross-thread ordering. Conflating them is the most common source of both bugs and
unnecessary cost.
Atomicity is about a single location: no torn reads, no lost updates, the operation either happened or it
did not. Ordering is about everything else — which other memory operations become visible along
with this one. A free-running statistics counter needs the first and none of the second, so
fetch_add(1, memory_order_relaxed) is exactly right and anything stronger is a fence you paid
for and did not use. A handoff of data needs both, and that is what release/acquire
is for.
An atomic RMW must own the cache line exclusively. Uncontended that is a local operation; the moment a second core wants the same line, every increment becomes a line transfer, and the cost grows with the number of cores fighting over it.
The producer writes a payload then sets a flag; the consumer reads the flag then the payload. Choose the memory order on each atomic operation and see which readings the standard permits — and which reorderings you have just legalised.
// The pattern behind every lock-free handoff you will write. // Compiles and passes TSan under clang++ -std=c++20 -O2 -pthread. std::atomic<bool> ready{false}; int payload = 0; // plain data, published by `ready` void producer() { payload = 42; // (1) write the data ready.store(true, std::memory_order_release); // (2) publish it } void consumer() { while (!ready.load(std::memory_order_acquire)) {} // (3) observe it assert(payload == 42); // (4) guaranteed to see (1) } // release (2) synchronizes-with acquire (3), so (1) happens-before (4). // Read the two halves as sentences: // release = "no earlier write in this thread may move AFTER this store" // acquire = "no later read in this thread may move BEFORE this load"
Two failures that are invisible in the source. One is two variables that happen to sit on the same sixty-four bytes. The other is a mutex that is correct, cheap on average, and a tail bomb.
Nothing here is shared logically: each thread owns its own counter. But coherency works on whole lines, so two counters in one line means every increment steals the line back from the other core. Toggle the padding and watch the throughput change by an order of magnitude.
// Two counters, ONE cache line: every increment by either thread invalidates // the other core's copy of the line. Correct, and an order of magnitude slow. struct Shared { std::atomic<uint64_t> a{0}, b{0}; }; // The same two counters, one cache line EACH. Nothing is shared but the name. struct Padded { alignas(64) std::atomic<uint64_t> a{0}; alignas(64) std::atomic<uint64_t> b{0}; }; static_assert(sizeof(Padded) == 128, "each counter owns its own line");
tail_ and reads head_; the consumer does the opposite. Put both indices in one
struct and they land on one line, so the two threads ping-pong that line on every single push and pop —
the exact structure you build next week, ruined by two adjacent declarations. This is why
spsc_ring.hpp's comment tells you to pad the indices before you write a line of the algorithm.Both are correct. A spinlock burns a core to keep the handoff in user space; a mutex hands the core back and pays a syscall to get it again. Which one wins depends on the critical section, the contention, and whether you have a core to spare — and the answer shows up in the tail, not the median.
| primitive | p50 | p99 | p99.9 | fairness | core burned |
|---|
// Test-and-test-and-set: spin on a relaxed LOAD, not on the exchange, so a // waiter reads its own cached copy instead of stealing the line every try. class SpinLock { std::atomic<bool> held_{false}; public: void lock() { for (;;) { if (!held_.exchange(true, std::memory_order_acquire)) return; // got it while (held_.load(std::memory_order_relaxed)) // no transfer std::this_thread::yield(); // or a PAUSE } } void unlock() { held_.store(false, std::memory_order_release); } // publishes bool try_lock() { return !held_.exchange(true, std::memory_order_acquire); } };
acquire on the
successful exchange stops any read inside the critical section from being hoisted above the lock;
release on the unlock stops any write inside it from sinking below. That pair is what makes a
lock a lock — a mutex does exactly the same thing, and its unlock synchronizes-with the next
lock for the same reason.A counter or statistic nobody synchronises on. Message counts, fill counts, a
RollingCounter's tally. You want indivisibility and nothing else — and one counter per
thread if more than one writes.
Any handoff of data between two threads: an SPSC ring, a seqlock snapshot, publishing a freshly built config. The workhorse, and the only one you need for next week's pipeline.
When you genuinely need one global total order over several variables — rare, and usually a sign the design should be simpler. It is the default because it is the easiest to reason about, not because it is the right cost.
A critical section shorter than a context switch, on a machine where the waiter has its own core and no chance of being descheduled while holding the lock. Otherwise it is the worst option available.
Anything off the hot path: start-up, configuration, the control plane, a long critical
section. Correct, fair, well understood — and it may sleep, which is why it stays off
on_book.
The answer more often than any of the above. Per-thread state, a single-writer ring, one owner per cache line. You cannot have a race over memory only one thread touches.
Every one of these passes its unit tests on your laptop. Open them.
volatileIt looks like the threading keyword — it appears in every old codebase near shared variables, and
declaring it does make the symptom change. What volatile guarantees is that the compiler
will not cache the value in a register or elide the access. What it does not guarantee is that
++x is indivisible, or that a write to x is ordered against a write to
anything else.
So the lost-update race survives untouched, and TSan still reports it. In Java volatile
does imply ordering; in C++ it never has. That cross-language false friend is why the mistake is so
persistent.
Fix: std::atomic<T> for anything two threads touch, with an explicit
memory order. Reserve volatile for memory-mapped device registers, where "do not optimise
this access away" is exactly and only what you mean.
relaxed on both sides of a handoffYou made the flag atomic, so TSan is quiet on the flag, and the test passes on x86 every time. What
you have actually written is: the payload write may become visible after the flag, so a consumer
that sees ready == true may still read the old payload. Nothing forbids it.
It passes on x86 because x86-64 does not reorder stores with stores, so the hardware accidentally provides the guarantee you failed to ask for. Run the identical binary logic on AArch64 and the consumer reads zero. This is the single most common way "it works on my machine" becomes a production incident when the fleet is heterogeneous.
Fix: release on the publishing store, acquire on the observing
load — Widget 3 shows exactly which readings each combination permits. Then write the happens-before
argument in a comment, because that comment is the only thing that will stop the next person
"optimising" it back to relaxed.
struct Ring { std::atomic<size_t> head, tail; ... }; — two eight-byte members, so
they share a cache line. The producer writes tail every push and reads head to
check for space; the consumer does the mirror image. Every operation on either side invalidates the
other core's copy of that one line.
The algorithm is lock-free and wait-free and correct, and it runs an order of magnitude slower than it should for a reason that is nowhere in the algorithm — it is in the struct layout. Nothing in a profiler points at a line of code; the cost is spread across every access.
Fix: alignas(64) (or std::hardware_destructive_interference_size)
on each index so each owns its line, and keep a per-side cached copy of the other index so you only
re-read it when you have to. Widget 4 is the throughput difference.
on_book pathAn uncontended std::mutex lock/unlock is a couple of atomic operations — genuinely cheap,
and your benchmark says so. Under contention it blocks in the kernel on a futex, and now your latency
includes a context switch out and a scheduler decision about when to come back: microseconds, not
nanoseconds, and not under your control.
Worse, the contention is correlated with exactly what you care about. Threads collide when the message rate is high, which is when there is something to trade. And priority inversion turns it unbounded: a low-priority thread holding your lock cannot release it until the scheduler runs it.
Fix: no blocking primitive on the hot path. Publish with release/acquire, use a single-producer ring for the handoff, and keep the mutex for the control plane where a five-microsecond pause is free. If you must have mutual exclusion in the hot path, the right question is how to remove the sharing instead.
You ran the racy version a hundred times and it produced the right answer every time, so you shipped it. Races are timing-dependent: on an idle laptop, with two threads and short loops, the interleaving that breaks you may need a preemption that simply never happened. Under load, on more cores, with a different compiler version that keeps the value in a register a little longer, it happens constantly.
The deeper problem is that a race is undefined behaviour, so a passing run proves nothing at all — the optimiser is entitled to assume the race cannot occur and to delete the code that would have handled it.
Fix: reason from the memory model, and let ThreadSanitizer check the reasoning —
-fsanitize=thread -O1 -g, which is what CI greps for. TSan finds races the schedule did not
happen to expose, because it tracks happens-before rather than watching for wrong answers. A clean TSan
run plus a written ordering argument is the standard; "it passed" is not.
Instant feedback, no grading. Pick the answer you would defend in a design review.
Q1Producer: payload = 42; ready.store(true, relaxed); Consumer:
while (!ready.load(relaxed)); read payload; It passes every test on your x86 laptop. What is
the status of this code?
Q2Eight threads each increment their own std::atomic<uint64_t>
in one array with relaxed ordering. Throughput is twenty times worse than one thread alone.
What is wrong?
Q3Your receive thread hands book updates to your strategy thread on the hot path, thousands of times a second. Spinlock or mutex?
++counter each on a plain
long. Run it three times and record three different answers.-O1 -g -pthread -fsanitize=thread and capture the
ThreadSanitizer: data race report — that is your HW9 evidence.volatile first, watch TSan report the race anyway, then fix it with
std::atomic and fetch_add(1, relaxed).relaxed and argue in a comment why it is now unsound even though it still passes.std::mutex and through the atomic. Compare the
maxima, not the means.on_book, and name the edge that makes the payload visible.include/spsc_ring.hpp. Padded indices, acquire/release on
head and tail — everything you built today, assembled into next week's pipeline.