latency.lab
Module 12 · capstone

Systems, Performance & the Order Book

Level: masteryTime: multi-dayPrereq: Modules 00–11

By the end you can

Big-O isn't the whole story: the cache

Modern CPUs are far faster than memory. To hide the gap they use caches — small, fast memory holding recently used data. Accessing data already in cache (a "hit") is ~1 ns; going to main memory (a "miss") is ~100 ns. That 100x gap means how your data is laid out often matters more than its Big-O.

This is why std::vector (contiguous, cache-friendly) frequently beats std::list (scattered nodes, cache-hostile) even for operations where the list has better Big-O. When you walk a vector, the CPU prefetches the next elements; when you walk a list, each node is a potential cache miss.

The trading-firm mindset

At a low-latency shop, nanoseconds are money. Engineers obsess over cache lines (64 bytes), false sharing, branch prediction, and memory layout. You don't need mastery of all of it now — but showing you think about layout, not just Big-O, sets you apart from the average new grad.

Benchmarking honestly

Reporting "it's fast" means nothing. Report throughput and latency percentiles, measured across many runs, and state your hardware.

bench.cpp
#include <chrono>
#include <vector>
#include <algorithm>

auto t0 = std::chrono::steady_clock::now();
for (const auto& op : operations) book.apply(op);   // the work
auto t1 = std::chrono::steady_clock::now();

auto ns = std::chrono::duration_cast<std::chrono::nanoseconds>(t1 - t0).count();
double per_op = double(ns) / operations.size();
std::cout << per_op << " ns/op, " << 1e9 / per_op << " ops/sec\n";

For percentiles, record each operation's latency into a vector, sort it, and read the values at the 50th, 95th, and 99th percentile positions. The p99 (tail latency) is what trading firms care about most — the worst case under which you still must perform.

The capstone: a limit order book

Everything in this course converges here. The order book is the perfect capstone because it exercises the entire syllabus at once, and it's the single most relevant project you can show a trading firm.

What the order book uses from this course

  • Integer prices in ticks (Module 01) — never floating point for money
  • Structs for Order/Trade, a class with invariants for OrderBook (Module 04)
  • RAII / Rule of Zero so it never leaks (Modules 04–05)
  • std::map per side for the best price at begin(), unordered_map for O(1) cancel-by-id (Module 07)
  • std::list at each price level for stable addresses + O(1) erase (Module 07)
  • Benchmarking with percentiles (this module)
  • All of it verified under AddressSanitizer (Module 11)

The full specification — the data model, the three operations, the matching algorithm, the market-data interface, the build layout, the test plan, and the benchmark to run — lives on its own page so you can keep it open while you build:

Open the Order Book specification →

This is the trophy

When it's done — matching correct, tests passing under ASan, benchmark reporting p50/p95/p99 with your hardware in the README — that single repository is stronger evidence than any line on your resume. It is the concrete proof that you can do the job. Pin it on your GitHub.

Takeaways

  • Cache locality often dominates Big-O in practice; contiguous data (vector) is cache-friendly.
  • Benchmark with throughput and latency percentiles (p50/p95/p99), and always state hardware.
  • Tail latency (p99) is what low-latency firms optimize for.
  • The order book integrates the entire course: ticks, RAII, the right containers, benchmarking, sanitizers.
  • Ship it on GitHub with a real README. It's your single best interview asset.
Live

Loading starter code…

Checkpoint · Systems & Performance

6 questions · pass at 70%

Q01
Roughly how much slower is a main-memory access than an L1 cache hit?
WhyAn L1 hit is ~1 ns; a main-memory access is ~100 ns — about two orders of magnitude. This gap is why data layout and cache locality matter so much.
Q02
Why can std::vector outperform std::list even when list has better Big-O for an operation?
WhyContiguous memory lets the CPU prefetch and stay in cache. A linked list scatters nodes across memory, so traversal incurs frequent cache misses that dominate real runtime.
Q03
Which metric do low-latency trading firms care about MOST?
WhyAverages hide bad outliers. Firms optimize the tail (p99/p99.9) because a rare slow path can miss a market opportunity or violate obligations.
Q04
When benchmarking, why report percentiles and hardware rather than just "it is fast"?
Whyp50/p95/p99 characterize the real distribution; stating hardware makes the numbers meaningful and reproducible. This is how credible benchmarks are reported.
Q05
In the order book, why is the best price available in O(1)?
WhyBids/asks are sorted maps (bids descending, asks ascending), so the best price is always at begin() — O(1) to read, O(log n) to insert/erase levels.
Q06
Why validate the finished order book under AddressSanitizer?
WhyA matching engine juggles pointers and list nodes; ASan surfaces any memory error with exact locations, proving the code is memory-safe — exactly what a reviewer wants to see.

Finished Module 12?

Then take the Final Exam & interview simulation.

+ Note