Reading guide Draft

Reading map

11 min read

On this page

Chapter 1 — Hardware: memory hierarchy and the CPU

A cache miss costs about 100 L1 hits, and a branch mispredict about 15 to 20 cycles. They explain much of the CPU work; queueing, scheduling and network delays set additional limits.

Topics

  • Latency ladder, approximate: register 0.3 ns, L1 1 ns, L2 4 ns, L3 10 to 40 ns, DRAM 80 to 100 ns, NVMe 20 µs, same-DC network 50 to 500 µs, Tokyo to Singapore 70 ms.
  • Cache lines are 64 bytes; data layout decides how many lines a loop touches. Spatial and temporal locality, hardware prefetchers, struct-of-arrays versus array-of-structs.
  • False sharing: two threads writing to different fields in the same line serialise each other.
  • Pipelines, out-of-order execution, branch prediction, and why a mispredict flushes the pipeline.
  • NUMA: memory attached to the other socket is slower, and the kernel will happily put you there.
  • SIMD, briefly: what it is and when it is not worth the trouble.

Lab

  1. Stride walk. Allocate a 256 MB Vec<u64>, sum every k-th element for k = 1, 2, 4 … 4096. Predict the curve, then plot time per element against stride. Then hold stride fixed and sweep the working-set size to look for the L1, L2 and L3 capacity changes; a fixed 256 MiB stride sweep alone does not locate them.
  2. Branchy versus branchless. Sum elements greater than 128 in an array of random bytes, sorted and unsorted. Run perf stat -e branches,branch-misses. Then rewrite with a conditional move and compare.
  3. False sharing. Two threads each incrementing their own counter: first in adjacent fields of one struct, then padded to 64 bytes with #[repr(align(64))]. Predict the ratio, then measure.
  4. Stretch: linked list versus Vec traversal of 10 million nodes. Explain the ratio using the latency ladder.

Check: describe what the stride curve shows on your machine and where the working-set sweep suggests L2 ends.

Chapter 2 — The OS gets in the way

A single context switch or page fault costs more than the whole budget of a hot-path iteration. The job is to get the kernel out of the loop and keep it out.

Topics

  • What a syscall actually costs (hundreds of ns to a few µs) and why a hot loop makes none.
  • Scheduler preemption, timer interrupts, and the jitter they inject. isolcpus, nohz_full, rcu_nocbs, IRQ affinity.
  • CPU pinning with sched_setaffinity; one thread, one core, forever.
  • Page faults, mlockall, and why the first touch of memory is slow. Transparent and explicit huge pages, TLB reach.
  • Busy-polling versus sleeping: trading CPU for latency, and why you never sleep in the hot path.
  • The allocator usually serves requests in user space, but growth can trigger syscalls, copies and page faults: preallocate hot-path storage at startup.

Lab

  1. Jitter histogram. A loop that reads rdtsc back to back and records the gap. Run unpinned, then pinned, then pinned on an isolated core. Plot p50, p99, p99.9 and max for each. Predict the max before running.
  2. Count the syscalls. Run Chapter 1’s stride walk under strace -c and perf trace. Then add a println! inside the loop and watch what happens.
  3. First touch. Allocate 1 GB, time the first write pass and the second. Repeat with MAP_POPULATE and with 2 MB huge pages via madvise.
  4. Stretch: a spin-wait loop versus a std::thread::park wakeup, measuring wake latency between two pinned threads.

Check: explain why p99 and max matter more than p50 for a trading system.

Chapter 3 — Concurrency and memory ordering

A contended mutex can put a hot thread behind another thread’s wake-up. Single ownership and message passing avoid much of that sharing; their correctness still depends on what the CPU and compiler may reorder.

Topics

  • What a mutex really costs: the uncontended fast path, the contended futex syscall, and priority inversion.
  • Atomics and the Rust memory model: Relaxed, Acquire, Release, SeqCst. What each one forbids the compiler and the CPU from doing.
  • Happens-before, and why “it passed the test” proves nothing on x86 (strong ordering hides bugs that ARM exposes).
  • Compare-and-swap, the ABA problem, and why single-producer single-consumer avoids most of it.
  • Cache coherence (MESI): a write to a shared line invalidates every other core’s copy, and that invalidation is the real cost of sharing.
  • Design rule: one writer per cache line, and share by message not by memory.

Lab

  1. Message passing. Two pinned threads, one writes a sequence number, the other reads it. Implement with Relaxed and observe stale or reordered reads using a flag-plus-data pattern; then fix with Release/Acquire. Run under loom to see the reorderings the hardware hides.
  2. Contended counter. 4 threads incrementing: Mutex<u64>, AtomicU64::fetch_add, then per-thread counters summed at the end. Predict the ordering, measure.
  3. Ping-pong latency. Two threads bounce a value through an AtomicU64, one core-to-core hop each way. Measure round-trip, then repeat across sockets if the box has two.
  4. Stretch: write a 16-slot SPSC queue with only two atomics and check with loom that small bounded executions preserve item order, with no loss or duplication.

Check: state which ordering a producer uses on its write index and which the consumer uses to read it, and why.

Chapter 4 — Networking

The network is where most of the latency lives, and the kernel stack adds 5 to 20 µs on every packet before your code sees a byte.

Topics

  • Where the time goes on a packet: NIC, interrupt, softirq, socket buffer, copy to user space, wake-up. Each step is a place to lose microseconds.
  • TCP versus UDP: ordering, retransmits, Nagle (TCP_NODELAY), and why exchanges use TCP for order entry but multicast UDP for market data.
  • Blocking reads, epoll, busy-polling (SO_BUSY_POLL), and io_uring. Why a hot loop polls and never waits.
  • Kernel bypass concepts: DPDK, OpenOnload, AF_XDP. What they remove and what changes in observability: DPDK, Onload and AF_XDP retain different amounts of kernel involvement and need different capture tools.
  • TLS in the path: the handshake, the per-record decrypt cost, and how user-space TLS, kernel TLS and NIC offload trade copying against record processing; compare them on the target connection.
  • Serialization: fixed binary layouts (SBE, FlatBuffers) versus JSON. Zero-copy parsing, endianness, reading fields straight out of the receive buffer.

Lab

  1. The ladder. Measure ping-pong round-trip for a one-byte message between: two threads via an atomic, two processes via shared memory, two processes via a Unix socket, two processes via TCP loopback, two machines via TCP. Predict each rung first, then plot.
  2. Nagle. Send 1000 small TCP messages with and without TCP_NODELAY; look for stalls caused by Nagle interacting with delayed ACKs; their presence and duration depend on the peer and the write pattern.
  3. Poll versus wait. A TCP echo client using blocking read, then epoll, then a non-blocking busy-poll loop on a pinned core. Compare p99 round-trip.
  4. Parse it. Hand-decode a fixed-layout binary message (say 48 bytes using Chapter 4’s layout: an 8-byte header, u64 sequence, u64 price, u64 qty, u64 timestamp, u8 side and 7 reserved bytes) straight from a byte slice with no allocation. Then parse the same data as JSON with serde_json. Compare cycles per message with perf stat.
  5. Stretch: capture a real exchange feed for 60 seconds with tcpdump, replay it from a file, and measure parse throughput.

Check: name the five hops between NIC and user code and which ones kernel bypass removes.

Chapter 5 — Hot-path data structures

Read Chapter 5 — Shaping the data for the complete explanations, worked examples, and labs.

The hot path allocates nothing, locks nothing, and touches as few cache lines as possible. Every data structure choice follows from those three rules.

Topics

  • Why HashMap is usually wrong: hashing cost, pointer chasing, rehash spikes, and unpredictable memory. Dense arrays indexed by a small integer id instead.
  • Preallocation and object pools: fixed-capacity Vec, slab allocators, arena allocators, and Box as a code smell in the loop.
  • The SPSC ring buffer: power-of-two capacity, head and tail on separate cache lines, cached indices to avoid reading the other side’s line every push.
  • Batching and amortisation: drain everything available, process, then publish once.
  • Branch-free lookups with bitmaps and trailing_zeros / leading_zeros.
  • Rust specifics: #[repr(C)], #[inline], bounds checks and get_unchecked, MaybeUninit, and reading the generated assembly with cargo asm.

Lab

  1. Build the SPSC ring buffer from Chapter 3’s stretch into a real one: u64 slots, capacity 4096, Acquire/Release on two atomics, cached head and tail. Benchmark throughput and per-item latency against std::sync::mpsc and a Mutex<VecDeque>. Predict the ratios first.
  2. Pad it. Move head and tail onto the same cache line and measure again. Explain the result with Chapter 1’s false-sharing lab.
  3. Map versus array. 10 million lookups of symbol id to position: HashMap<u32, Position>, then Vec<Position> indexed by id. Count cache misses with perf stat -e cache-misses.
  4. Zero allocation. Run the ring buffer benchmark with a counting global allocator and assert the hot loop makes zero allocations after warm-up.
  5. Stretch: a 64-bit bitmap over 64 buckets; find the next set bit above index i with trailing_zeros and compare to a linear scan.

Check: draw the ring buffer with its two indices and explain which thread owns which cache line.

Chapter 6 — Market data and order books

Read Chapter 6 — The book for the complete explanations, worked examples, and labs.

For the lab’s bounded range of price ticks, an aggregated order book can use a dense array of levels with cursors at the best bid and best ask. Correct updates and sequence recovery matter as much as the representation.

The chapter connects market dynamics with the storage and queueing techniques developed in the earlier chapters.

Topics

  • What a limit order book is: price levels, queue priority, bid and ask, spread, depth, top-of-book versus full depth.
  • Market data feeds: snapshot plus incremental deltas, sequence numbers, gap detection, and recovery. What a stale book costs you.
  • Book representations: BTreeMap (simple, slow), sorted Vec, and the price-indexed dense array with best-price cursors (O(1) level lookup, cache-friendly; finding a new best after a deletion may require a scan or bitmap). Why crypto’s wide price ranges need a sliding window or bitmap on top.
  • Hot-path events: trade, level update, level delete, and what the strategy actually needs from each (usually just top-of-book changed, yes or no).
  • Where a market maker spends its time: quote, inventory skew, cancel-replace. Enough to make the final project meaningful.

Lab

  1. Build a book. Implement apply(update) and best_bid() / best_ask() on three structures: BTreeMap<Price, Qty>, a sorted Vec, and a dense array of 65,536 price ticks with cursors. Same interface, same tests.
  2. Replay. Feed each one a captured or synthetic stream of 10 million updates (Chapter 4’s capture, or a generator). Measure updates per second and p99 update latency. Predict the ranking first.
  3. Break it. Drop one message from the stream and show the book diverging. Then add sequence-gap detection that forces a resync.
  4. Stretch: handle a price moving outside the dense array’s window without a full rebuild.

Check: explain when the dense array wins, how best-price searches work, and what it costs in memory.

Chapter 7 — Measurement and the trading loop

Read Chapter 7 — The number for the complete explanations, worked examples, and labs.

You cannot improve what you measure wrong, and averages hide exactly the latencies that lose money. The final project connects the earlier chapters’ pieces into one strategy loop, linked to feed and output threads by rings, and profiles it.

Topics

  • Percentiles, not averages: p50, p99, p99.9, max. Why the tail is the product.
  • Clocks: rdtsc versus Instant::now(), TSC invariance, and clock-domain traps across cores.
  • Histograms: hdrhistogram, log-scale buckets, and recording without allocating in the loop.
  • Benchmark hygiene: warm-up, pinning, CPU frequency scaling, black_box, and coordinated omission.
  • Profiling: perf record plus flame graphs, perf stat counters, and reading cargo asm for the hot function.
  • Replay harnesses: deterministic input, deterministic output, and diffing two variants.

Lab — final project

  1. Assemble. A feed thread parses Chapter 4’s binary messages from a replay file into Chapter 5’s SPSC ring buffer. A pinned strategy thread drains it, applies updates to Chapter 6’s dense-array book, and runs a toy quoter: if the mid moved more than one tick, emit a cancel-replace into an output ring buffer.
  2. Instrument. Timestamp with rdtsc at message decode and at order emit. Record decode-to-emit latency into a preallocated, non-resizing hdrhistogram. Measuring wire-to-decision also requires a calibrated NIC receive timestamp and an endpoint at the decision. Report p50, p99, p99.9, max.
  3. Profile. perf record the strategy thread and produce a flame graph. Find the top three functions and say whether each is expected.
  4. Vary. Swap in the BTreeMap book and the Mutex<VecDeque> queue one at a time and re-measure. Each swap should be explainable from an earlier chapter.
  5. Close the loop. Read a feed handler’s hot path and, for each of ten lines, identify the chapter that explains it.

Check: produce one histogram and one flame graph, and use them to justify a concrete change to the feed handler.