How CPUs fight latency

Put the memory wall from 0.4 in a single core's terms. Our reference CPU runs its P-cores at about 5 GHz (one cycle every 0.2 ns), while a trip to DRAM costs roughly 90 ns. Miss every cache on one load and the core has ~450 cyclesin which, naively, there is nothing to do. Bakhvalov puts it at "more than three hundred clock cycles" on current hardware. From the CPU's perspective, a last-level cache miss feels like a very long time.¹

Caches (0.5) make that miss rare. This chapter is about the other half of the fight: the machinery that keeps the core busy anyway, and the one enemy that machinery cannot beat. Everything here stays qualitative; you never program these mechanisms, but you feel them in every benchmark you'll run.

Every trick a CPU plays is the same bet stated four ways: find work that doesn't depend on the thing we're waiting for. The hardware view: a core splits into an in-order frontend that fetches x86 instructions and decodes them into fixed-length micro-operations (µops), and an out-of-order backend that executes those µops whenever their inputs are ready. CS:APP calls the two halves the instruction control unit and the execution unit.²³

Pipelining. An instruction passes through stages (fetch, decode, execute, memory, write-back), and every stage works on a different instruction each cycle, like laundry overlapping in washer and dryer.⁴⁵ Even single arithmetic units pipeline internally: a floating-point multiply takes 5 cycles to finish, but a fully pipelined multiplier starts a new multiply every cycle.⁶

Superscalar issue.There isn't one pipeline: the backend of our reference core is 6-wide, dispatching µops to 12 execution ports each cycle; mainstream cores in 2024 issue 6–9 instructions per cycle.⁷

Out-of-order execution.When a load misses, the core doesn't freeze in program order. Decoded µops wait in a reorder buffer (512 entrieson our reference core's Golden Cove), and any instruction whose inputs are ready executes, regardless of program position. Results are then retiredstrictly in order so the program can't tell. The miss still takes 90 ns; it just stops being the only thing happening.⁸

Prefetching. The memory system watches your address stream. Walk memory sequentially (the row-major sweep from 0.6) and the hardware prefetcher recognizes the pattern and fetches the next lines beforeyou ask, converting would-be misses into hits. This is exactly why "access data sequentially" is rule one of cache-friendly code.⁹

Speculation.A branch would stall the frontend until its condition resolves, so the branch prediction unit guesses the outcome and the core barrels ahead, executing the predicted path without committing results until the guess is confirmed. Modern predictors routinely exceed 95% accuracy; the catch is the misprediction penalty (measured at ~19 cycles on CS:APP's reference machine) paid to flush the speculative work and refill the pipeline.¹⁰¹¹

SourcesCS:APP 3e §5.7 · pp. 553–561Bakhvalov 2e §3.2–3.3, §3.8 · pp. 39–47, 64–71

All four tricks need the same raw material: independent work. Register renaming even manufactures some: the 16 architectural registers your assembly names are aliases onto roughly 300 physical ones, which erases the false collisions (two instructions merely reusing the same register name). But a true value-flows-to-value dependency, what Bakhvalov calls a dependency chain, survives renaming by definition. Only genuine data flow constrains the machine.¹²¹³

Give the core a loop where iteration i+1 needs nothing from iteration i (summing an array) and it keeps dozensof loads in flight at once: CS:APP's Haswell had two load units holding up to 72 pending reads each; Golden Cove issues up to three loads per cycle with 16 line-fill buffers and a 48-entry queue of outstanding uncore requests. That is memory-level parallelism, and it is the real reason streaming code hides DRAM latency.¹⁴¹⁵

Now walk a linked list: p = p->next. The address of the next load is insidethe current one. Until this miss returns, the next load cannot even be named: there is nothing to reorder, nothing to prefetch, nothing to speculate about. The chain serializes memory latency: you pay per link, in full, single file. CS:APP turns this into a measurement technique: a linked-list traversal's time per element exactly equals the load latency (their list_len clocks 4.0 cycles per element, the documented L1 hit latency), because the loads form one unbroken dependency chain.¹⁶ Parallelism is where latency-hiding lives, and a chain is where parallelism dies.

Now look at a die photo of a modern CPU with this arithmetic in mind. The actual arithmetic units are a sliver. The rest (megabytes of cache, the 512-entry window and its schedulers, predictors with 12K-entry branch target buffers, prefetchers) is all latency-fighting machinery, spent per thread to make one stream of dependent instructions run fast.¹⁸

Hold that image. Topic 1 opens with the other answer to the same 450-cycle problem: strip out the machinery, and when a thread stalls, just run a different thread. Thousands of them. That single design swap is the entire difference between a CPU and a GPU (1.1).