You have the platform. Now prove it is fast — not fast on average. A 40 µs mean hides the 5 ms tick that lost the race, and every tail spike has a physical cause with a signature you can learn. This week you stop guessing: measure, attribute, fix, re-measure, and ship something that survives contact with a live session.
starters/hw14/tail.cpp — profile it, find the pathology, collapse the tail
HW14: tail_fixed.cpp + a changelog with before/after p99.9
Ship: clean under ASan/UBSan/TSan, released -O3 -march=native -flto
Latency distributions are not Gaussian. They are heavy-tailed and usually bimodal: a tight fast body, and a sparse population of rare catastrophic stalls. The mean sits in the valley between them, describing a tick that nobody ever experiences. Percentiles are not a stylistic preference in this course — they are the only honest summary of a shape like that.
fast body tail
count |#### .
|####### .
|########## . ← p99.9
|######### . lives
|#### . . HERE
+--------------------------→ µs
mean = 40 p99.9 = 210 max = 5200
Report p50, p99, p99.9 and the max, per window. A p99 computed over a whole session hides two minutes where it was the p50 — and the max is the number your risk case has to survive.
The subtlest way to under-report a tail. If you time request to request — start the clock when the previous one finished — then a stall that delays ten requests is recorded once, and the nine it pushed back are simply never sampled. Your histogram loses exactly the events that hurt.
Measure on a fixed schedule: the tick was supposed to be handled at T, so record now − T, including the time you spent not being able to start. That is the number the market saw.
book_snapshot it sent to the order you sent back — a fixed origin it controls, not one
you choose. You cannot omit your way to a good score.The same function, timed five different ways. Pick a machine and a protocol, then read what each statistic reports against what the function actually costs. The true cost here is fixed at 41 ns — everything else is measurement error you chose.
using clk = std::chrono::steady_clock; // stop the optimizer deleting the work you are timing template <class T> inline void do_not_optimize(T& v) { asm volatile("" : "+r,m"(v) : : "memory"); } for (std::size_t i = 0; i < WARMUP; ++i) sink += roll.push(px[i]); // untimed for (std::size_t i = 0; i < N; ++i) { const auto t0 = clk::now(); sink += roll.push(px[WARMUP + i]); // the hot path const auto t1 = clk::now(); do_not_optimize(sink); lat_ns.push_back( std::chrono::duration<double, std::nano>(t1 - t0).count()); }
Three verbs, in order, every time: perf stat for the totals,
perf record for the stacks, perf report or a flame graph to read them.
Intuition about hotspots is wrong more often than it is right, and it is wrong most confidently on
the tail.
# 1. cheap summary counters — always start here
perf stat -d ./build/hft_bot --replay tape.bin
# 2. sample the call stacks at 4 kHz with DWARF unwinding
perf record -F 4000 -g --call-graph dwarf \
./build/hft_bot --replay tape.bin
# 3. read where the cycles went
perf report --stdio | head -40
perf annotate on_book # cycles per source line
# and the picture: fold the stacks into a flame graph
perf script | stackcollapse-perf.pl | flamegraph.pl > tail.svgcache-misses, LLC-load-misses — a DRAM trip is 200+ cycles. Usually the real cost behind a "slow line".branch-misses — a flush is ~15–20 cycles. A hot unpredictable branch is a candidate to make branchless (week 13).page-faults — should be zero after startup on a hot path. Any nonzero count is a tail source you can name.context-switches, cpu-migrations — should also be zero. If they are not, you did not really get the core.-g in the release build. Debug
symbols cost nothing at run time and are the difference between a readable flame graph and a wall
of hex addresses. Optimize and keep symbols.Width is time. Click a frame — or tab to it and press Enter — to see its total time (the frame plus everything it called) against its self time (the frame alone). Wide plateaus are the targets; tall thin spikes are just deep call stacks and cost nothing.
A tick-to-trade path is a chain, and a chain is only as fast as its slowest link on that tick. If each of N stages is "fine" 99% of the time, the odds that all of them are fine is 0.99N — which falls off a cliff faster than anyone's intuition.
| stage | owns it | typical |
|---|---|---|
| wire in / bypass | W13 | 1–3 µs |
| parse / decode | W12 | 1–2 µs |
| book update | W7 | 2–5 µs |
| signal | W7–8 | 1–2 µs |
| decide + risk check | W14 | 1–2 µs |
| serialize | W6 | 1–2 µs |
| wire out | W13 / colo | 1–3 µs |
Seven stages, each owned by a different week of the course. Any one of them can be the reason your p99.9 is a millisecond, which is why the attribution matters more than the total.
There is no garbage collector in C++, and it does not matter: five other mechanisms produce the same shape. Tick a source and watch it appear in the histogram — each one has its own signature, which is how you recognise it in a real session.
starters/hw14/tail.cpp processes two million
synthetic ticks and prints the distribution. Its median is fine; its tail is not. The pathology is on
the hot path and there are two of them stacked — a heap allocation and an O(window) recompute.
// a fresh vector per tick: malloc + push_back growth static double signal(const std::vector<double>& prices, std::size_t i, std::size_t window) { std::size_t lo = i >= window ? i - window : 0; std::vector<double> scratch; // (a) allocates for (std::size_t k = lo; k <= i; ++k) scratch.push_back(prices[k]); double s = 0.0; for (double v : scratch) s += v; // (b) O(window) return s / scratch.size(); }
Measured here with clang++ -O2 -std=c++17 on an
ordinary laptop: p50 458 ns · p99 791 ns · p99.9 1333 ns · max 178 µs. The median is
unremarkable and the max is 390× it.
// O(1) per tick, zero allocation on the hot path struct RollingMean { std::vector<double> buf; // reserved once, used as a ring std::size_t window, count = 0, head = 0; double sum = 0.0; explicit RollingMean(std::size_t w) : buf(w, 0.0), window(w) {} double push(double px) { if (count == window) sum -= buf[head]; // evict oldest else ++count; sum += px; // admit newest buf[head] = px; head = (head + 1 == window) ? 0 : head + 1; return sum / static_cast<double>(count); } };
Same machine, same flags: p50 41 ns · p99 42 ns · p99.9 42 ns. The body got 11× faster and the tail collapsed onto the median — which is the actual deliverable.
i and grows from 1 to window at the start. If your warm-up does not ramp
count the same way, the sink changes — and a faster program that computes
something else is not a fix. Match the warm-up, then diff the sink.Two production metrics decide whether a fast bot is a good bot. The first is the tail, because the board sorts on it. The second is the markout: what the mid did after your fill. A bot with a beautiful p99.9 and a negative markout is not winning — it is being run over quickly.
A markout marks each fill against the reference mid some
time later: markout = sign(side) × (mid_later − mid_at_fill) × qty. Positive means the
market came to you; negative means you were picked off. Choose a cohort of fills and watch the curve
develop across the horizons the arena computes.
// per fill, at each horizon: +100 ms, +1 s, +5 s double markout(int side, double fill_px, double mid_later, double qty) { const double s = (side == BUY) ? 1.0 : -1.0; return s * (mid_later - fill_px) * qty; } // negative and persistent on one symbol or one // counterparty => toxic flow: widen, skew away, or pull.
write or
a string format on the hot path is a guaranteed tail event.-O3 -march=native -flto -DNDEBUG -g.| weight | deliverable |
|---|---|
| 35 pts | A flame graph of your on_book path, plus a correct reading of the hotspots |
| 30 pts | A tail-reduction changelog with a p99.9 improvement proven by the harness |
| 20 pts | Clean ASan/UBSan and TSan runs over the replay |
| 15 pts | A release build with the graded flags, plus a short profiling report |
Note what is not there: a target number.
You are not graded on being faster than a threshold; you are graded on having found a cause,
fixed it, and proved the fix on the same tape. A one-line changelog entry that says "moved the
allocation out of signal(); p99.9 1333 ns → 42 ns" is worth more than a mystery
improvement of any size.
scripts/latency_replay.py drives ./build/hft_bot --replay over a
deterministic tape; scripts/latency_report.py prints p50/p99/p99.9, throughput and the
tail histogram. It is the same code that grades you, so there is no excuse for a surprise.Four of these produce a number that looks fine and is wrong. The fifth produces a number that is right and useless.
You time a pure function, never use the result, and the optimizer — correctly — removes the
call. Now you are timing two clock::now() calls and reporting 0.4 ns as the cost of
your signal. It is the fastest wrong answer in this course, and it gets submitted every year.
The same failure with a subtler face: hoisting. A loop-invariant computation gets lifted out of your timing loop, so you measure it once and divide by a thousand.
Fix: accumulate into a sink you print at the end, and put a
do_not_optimize barrier around it. Then sanity-check the magnitude — if a function
that touches 256 doubles claims 1 ns, it did not run.
A 40 µs mean over a bimodal distribution describes a tick that never happened. And a p99 over a whole session hides a two-minute stretch where it was the p50 — the session-wide number is an average of percentiles, which is not a percentile of anything.
The mirror error is reporting only the min because "that is what the code can do". The market does not give you your best case; it gives you the case you got.
Fix: keep the raw samples. Report p50, p99, p99.9 and the max, per window, with the sample count next to them. Plot the histogram — and if you only ever look at one number, look at p99.9.
Start the clock when the last tick finished, and a 5 ms stall is recorded exactly once — while the ten ticks it delayed are never sampled at all, because you were not there to sample them. Your histogram is a record of the moments the system was healthy.
This is why load generators that back off under stress systematically under-report tails, and why a "p99.9 of 60 µs" from such a harness can coexist with visibly missed races.
Fix: measure against a fixed schedule or an externally stamped origin — for a tick
that arrived at T, record now − T. In the arena the exchange owns
that origin, which is the whole point of it owning the stamp.
A frame with 60% total time and 2% self time is not slow; its children are. Rewriting it buys nothing. Equally, a tall narrow tower in a flame graph is a deep call stack, not a hot one — width is time, height is only depth.
And a sampling profiler is statistical: a symbol with 3 samples out of 4000 is noise. Chasing it is how an afternoon disappears.
Fix: read self versus total before you touch anything, sample long enough that the
hot frames have hundreds of samples, and re-run perf stat after the change. If the
counters did not move, neither did your latency.
This is the one that is technically correct and commercially useless. You made the bot fast, so it now gets filled instantly — and it gets filled instantly precisely when someone better informed wants the other side. Fast fills are selected fills.
It shows up as a healthy fill rate, a healthy latency board position, and a markout at +1 s that is consistently negative on one symbol or against one counterparty. The rebate hides it in the raw P&L, which is exactly why the arena computes markout separately.
Fix: measure markout per cohort — passive versus aggressive, per symbol, per counterparty where you can see it. Where it is persistently negative, widen, skew away, or stop quoting that name. Being fast is a licence to be selective, not a reason to trade more.
Three questions, instant feedback, nothing recorded.
Q1Seven stages, and each is "fast" 99% of the time, independently. What fraction of ticks are fast end to end?
Q2Your flame graph shows signal() at 55% total, 9% self, with operator new, _int_malloc and free beneath it. Where is your tail?
Q3Your bot's p99.9 is 38 µs, fill rate is high, raw P&L is slightly positive from rebates — and the +1 s markout on one symbol averages −12 ¢ per share. What do you do?
starters/hw14/tail.cpp at -O2 — the point is to profile
the algorithm, not a missing optimizer. Run it several times and watch p50 hold
still while p99.9 and max jump around.perf record -g → perf report, then fold the stacks into
a flame graph. No perf? valgrind --tool=callgrind, Instruments, or even
ltrace -c to count the malloc calls — the attribution is the deliverable,
not the tool.tail_fixed.cpp: one reserved ring, one running sum. Match the warm-up so
the sink is unchanged, then quote the before/after ratio.tail_fixed.cpp with an identical sink, plus p50/p99/p99.9
before and after.on_book path, the top tail cause found and
killed, and a measured p99.9 improvement from the harness on the same tape.starters/hw14/tail.cpp is the
pathology; scripts/latency_report.py is the instrument that grades the fix.