Week 9 gave you atomics and a memory model. This week you assemble them into the one data structure your bot actually needs: a bounded single-producer / single-consumer ring buffer that hands ticks from the socket thread to the strategy thread with no mutex, no allocation, and no unbounded queue hiding a slow consumer. Then you chain four of them into a pipeline and watch where it backs up.
tail - head == cap — and say which index each thread owns.push and pop, and name the one pairing that ThreadSanitizer will hold you to.compare_exchange.yield or sleep on purpose rather than by habit.include/spsc_ring.hpp — seven grades, ending in a TSan run
Wire the ring between receive and on_book
An unbounded queue is a latency bug that looks like a memory bug
A lock-free pipeline is a chain of bounded queues, and the queue that matters is the easy case: exactly one thread pushes, exactly one thread pops. Because each index has a single writer, no thread ever needs to retry — a plain atomic load and store with the right ordering is the whole mechanism. Step the ring below and watch the two counters move independently.
The counters never wrap back to zero — they only increase.
The slot is counter & mask. Unsigned overflow of the counters is
well defined and the subtraction stays correct, so you get all 8 slots with no sacrificial element.
—
// producer thread only — it owns tail_ bool push(std::uint64_t v) { const auto t = tail_.load(mo::relaxed); const auto h = head_.load(mo::acquire); if (t - h == cap_) return false; // full buf_[t & mask_] = v; // write payload… tail_.store(t + 1, mo::release); // …then publish return true; }
The release store is the publication. Everything written before it —
here, the payload — is visible to any thread that acquire-loads the same variable and
sees the new value.
// consumer thread only — it owns head_ bool pop(std::uint64_t& out) { const auto h = head_.load(mo::relaxed); const auto t = tail_.load(mo::acquire); if (h == t) return false; // empty out = buf_[h & mask_]; // read payload… head_.store(h + 1, mo::release); // …then free the slot return true; }
Perfect mirror. Each thread reads its own counter relaxed — nobody else
writes it — and reads the other thread's counter acquire. That is the entire
correctness argument, and the whole of it fits on these sixteen lines.
include/spsc_ring.hpp gives you SPSCRing(capacity_pow2),
push(v) → bool, pop(out) → bool, empty(), full().
push returns false when full; pop returns false
when empty. Seven grades: basic, empty_pop, full, fifo, wrap, concurrent, tsan —
make spsc for the first five, then a two-thread run and a
-fsanitize=thread build that must print zero ThreadSanitizer warnings.Three mechanisms make or break the ring: where the two counters live in memory, which memory order publishes the payload, and whether you need a retry loop at all. Take them one at a time.
head_ is written by the consumer; tail_ is written by the producer. Two
size_t next to each other are 16 bytes, so they land in the same 64-byte line by default.
Every producer store then invalidates the consumer's copy of that line and vice versa — two cores
ping-ponging one line through the coherence protocol. Nothing is incorrect; you have simply
serialized two threads through a cache line. Flip the toggle.
—
Figures are representative of two cores on the same die of a ~3 GHz x86-64 part with 64-byte cache lines. Your absolute numbers will differ; the direction and rough factor will not. Measure it in the lab — it is the cheapest three-line win in the whole course.
The permitted-readings table below is the memory model made concrete. Pick an ordering for the
producer's store to tail_ and for the consumer's load of it, then ask the one question
that matters: can the consumer observe the new tail_ but the old payload?
buf_[t & mask_]| Consumer sees tail_ | May read payload | Verdict |
|---|
Note the trap at both ends. relaxed/relaxed
is a data race — undefined behaviour, and TSan will say so. seq_cst/seq_cst
is correct but adds a full barrier: on x86-64 the store becomes an xchg-style locked
operation costing tens of nanoseconds where the release store was free. Release/acquire is not a
compromise here; it is the exact tool.
Add a second producer and the single-writer argument collapses: two threads can read the same
tail_, both write slot t, and one message is lost. The fix is a
compare-and-swap retry loop — claim the slot atomically, and if someone beat you to
it, re-read and try again. Nobody blocks, but everybody retries, and retries are wasted cache-line
round trips. Drag the slider.
// MPSC producer side: claim a slot, then fill it auto t = tail_.load(mo::relaxed); do { if (t - head_.load(mo::acquire) == cap_) return false; // full } while (!tail_.compare_exchange_weak( t, t + 1, mo::acq_rel, mo::relaxed)); buf_[t & mask_] = v; // slot is mine seq_[t & mask_].store(t + 1, mo::release);
Notice the second atomic. Once producers can finish out of
order, the consumer can no longer trust tail_ to mean “everything below this is
written” — it needs a per-slot sequence stamp. MPMC adds the same on the consumer side. That is
the real cost of many writers: not the CAS instruction, but the extra state and the extra cache line
every message now touches.
A CAS only asks “is the value still what I read?” — never “has it been untouched?”. If another thread changes A to B and back to A, your CAS succeeds on a world that moved underneath you. Step through the classic lock-free stack pop.
Every thread completes in a bounded number of its own steps, regardless of what any other thread does. No retry loops at all. Strongest guarantee, hardest to build, and rarely what you need.
Your SPSC push and pop are wait-free. There is no loop in either one — that is why they are the fastest thing here.
At least one thread always makes progress. Individual threads may retry indefinitely, but the system as a whole never stalls, so descheduling or killing a thread cannot wedge the structure.
A CAS-loop MPSC queue is lock-free, not wait-free. One unlucky producer can starve while others succeed.
A thread can be stopped by another thread's inaction. A mutex holder that is descheduled, page-faults, or is preempted by a higher-priority thread stops everyone waiting on it.
This is the tail-latency failure mode. Median cost looks fine; the p99.9 carries the one time the holder lost its core.
One ring is a lab exercise. Your bot is four stages chained by rings — feed handler → book builder → strategy → order gateway — and the end-to-end latency is not the sum of the stage costs. It is the sum of the stage costs plus every queue that is not empty. Turn up the arrival rate and watch which ring fills first.
Each bar is one stage's service time; the badge between two
stages is the ring that connects them. Queueing delay is computed from the classic
ρ/(1−ρ) shape, so it is finite until utilisation reaches one and then it is not.
Refuse the push and count it. Cheapest, and correct for anything idempotent or re-sent. Wrong for a stream of incremental book deltas — skip one and your book is silently diverged from the venue's.
Overwrite the stale entry. Right when only the latest value matters — a top-of-book quote, a mark price. The consumer always sees fresh data and you never queue work you would throw away anyway.
Merge on the way in: keep one slot per symbol and update it in place. Turns a burst of 40 updates on one name into one unit of consumer work. This is the answer that actually holds a p99.9 through a message storm.
What none of the three is: growing the queue. An unbounded queue does not fix a slow consumer, it hides one — converting a throughput problem you could have measured into a memory-and-latency blowout you discover in production. A bounded ring turns the same event into an explicit decision at the moment it happens, with a counter you can graph.
Your consumer pops and finds the ring empty. What now? This is the trade you are actually making
when you write while (!q.pop(x)) {}, and it is a real trade: latency against a whole core.
—
—
The honest summary: busy-spin buys you roughly a hundred nanoseconds of wake latency for the price of one core burning at 100 % forever. That is a good trade for a market-data consumer on a pinned core and a terrible one for a logging thread. Most bots need exactly one spinning thread; the others should sleep.
Every one of these has shipped in a submission, and four of the five pass a single-threaded test suite. Open them.
relaxed and the single-threaded tests passThis is the most common failure and it is invisible until TSan. With
relaxed on both the store to tail_ and the load of it, nothing orders the
payload write against the index publication. The consumer is permitted to see
tail_ == 1 and read an uninitialised slot. On x86-64 you will probably never observe
it, because the hardware happens not to reorder store-store — which is exactly what makes it
dangerous: it is a data race that only shows up on ARM, or after the compiler hoists a load next
release.
make spsc is green. basic, empty_pop, full, fifo, wrap all pass. The
tsan grade is the one that fails, and the correct response is not to weaken the test.
Fix: release on each thread's store to its own counter,
acquire on each thread's load of the other's. Two words. Then re-run
g++ -O1 -g -pthread -fsanitize=thread and require zero ThreadSanitizer warnings.
seq_cst, so it is “definitely safe”The opposite reflex, and it is correct — just slow. seq_cst demands a single total
order across all sequentially-consistent operations in the program, which on x86-64 turns your free
release store into a locked read-modify-write and drains the store buffer. You have added tens of
nanoseconds to an operation whose entire budget was a few.
Worse, it hides your reasoning. A reviewer cannot tell which orderings you needed and which you panicked into, so the next person to touch the file has to redo the analysis from scratch.
Fix: use the weakest ordering you can justify in a comment. Relaxed for the counter you own, acquire/release for the pairing that publishes the payload. The starter's rubric explicitly checks for “not all relaxed, not all seq_cst”.
% is on the hot pathA non-power-of-two capacity forces index % cap. Integer division is 20–40 cycles
and cannot be pipelined the way a mask can; you have put a division in the innermost loop of your
tick path to save a rounding decision at construction time.
The related bug: some implementations waste one slot to distinguish full from empty, then use a
power of two anyway, and now capacity 1024 stores 1023 items. With monotonic counters you do not
need the sacrificial element at all — empty is head == tail and
full is tail - head == cap, which are different tests.
Fix: assert the capacity is a power of two in the constructor, store
mask_ = cap - 1, and index with &. Keep the counters monotonic and
let unsigned wraparound do its (well-defined) job.
Correct, race-free, TSan-clean — and running at a fraction of its potential throughput because
head_ and tail_ share a 64-byte line. Each producer store invalidates the
consumer's cached copy, so every single push and every single pop pays a
cross-core coherence miss on data neither thread needed to share.
The tell is a throughput number that barely moves when you make the payload smaller, plus a profiler showing time in the atomic load rather than in your code.
Fix: alignas(64) on each counter, and check
sizeof afterwards to confirm the padding actually landed. The stretch goal is better
still: cache the other side's counter in a plain member and only re-read the atomic when the
cached value says you are full or empty.
It drops nothing and delays everything. A std::deque behind a mutex grows happily
during a message storm; each push allocates, the consumer falls further behind, and every tick now
waits behind a queue of stale ticks. You are trading on a book that is one second old and your
logs show no errors at all.
The same bug in a different costume: a bounded ring whose push failure you
if (!q.push(v)) { /* try again */ } in a loop. Now the producer — your socket reader —
blocks on the consumer, and TCP back-pressure propagates all the way to the venue.
Fix: a fixed ring, an explicit policy on push == false (drop newest,
drop oldest, or coalesce), and a counter for how often it fired. If that counter is nonzero in a
normal session, your consumer is too slow — fix that, do not enlarge the queue.
Three questions, instant feedback, nothing recorded.
Q1In an SPSC ring, which single pairing makes out = buf_[h & mask_] a race-free read?
Q2Why is the ABA problem irrelevant to an SPSC ring buffer?
Q3Your ring's push returns false a few thousand times per session. A teammate proposes growing the capacity from 1,024 to 1,048,576. What actually happens?
include/spsc_ring.hpp until all seven grades pass:
basic, empty_pop, full, fifo, wrap, concurrent, tsan. make spsc gets you
the first five.spsc_ops_per_sec. Then run the
-fsanitize=thread build with SPSC_N=200000 and require zero warnings.release to relaxed, confirm the
single-threaded tests still pass, and confirm TSan catches it. That contrast is the lesson.alignas(64), re-measure throughput, put it back. Report the factor you
saw and your machine's line size.push == false a real policy — drop newest, drop oldest, or coalesce per
symbol — plus a counter. Graph the counter.