1 · Memory and the CPU Draft
Chapter 1 — Memory and the CPU
On this page
A modern server core can finish four or more instructions per clock cycle, and at 4 GHz a cycle lasts 0.25 ns: 4 GHz is 4 × 10⁹ cycles per second, so one cycle is 1 ÷ (4 × 10⁹) s = 0.25 × 10⁻⁹ s. Four cycles make a nanosecond and 4,000 make a microsecond. Left to itself, the core is absurdly fast. It is rarely left to itself. Most slow programs are not computing slowly. They are waiting.
They wait for two things above all. The first is a cache miss: the data is not in the core’s small private caches and must come from further away, as far as main memory about 100 ns away. The second is a branch mispredict: the core guessed which way an if would go, ran ahead, was wrong, and must throw the work away. Nearly every low-latency technique in this book, from fixed arrays and padded structs to pinned threads and branch-free parsers, exists to avoid one of these two events on the hot path.
Put numbers on a budget. A market-data-driven quoter must go from the last bit of an exchange packet arriving at the network card to a quoting decision in 2 µs: 8,000 cycles at 4 GHz. The card, the PCIe transfer and a kernel-bypass receive path take about 1 µs on good commodity hardware. That leaves roughly 1 µs, or 4,000 cycles, to decode the message, update the book and decide.
A load that misses every cache and goes to DRAM costs about 90 ns, or 360 cycles. If each load needs the previous one’s result to know its address, the loads cannot overlap, and 1 µs buys eleven of them. Eleven trips to memory and nothing else: no parsing, no arithmetic. A mispredict costs 15–20 cycles, about 5 ns, so the same microsecond buys about 200. That sounds like plenty until a byte-by-byte parser executes a branch every few instructions, on data that makes the branch a coin flip.
Eleven is the number to remember. A cold lookup in a general-purpose hash map can cost two or three DRAM misses, and a tree of price levels costs one per node walked. And the budget must hold at the 99th percentile, which is exactly where the cold misses live.
The labs specify experiments to implement under ch01-hardware/; companion code is not included in this checkout. The estimates below are predictions to test, not results from those missing binaries.
Trading terms used in this chapter
The vocabulary (book, tick, quoter, hot path and the rest) and the CPU basics this chapter builds on are defined in Chapter 0 — The machine from the top, sections 0.9 and 0.10; read it first if any of them is new.