How Modern CPUs Execute Code: Pipelines, Branches and Memory

At GOTO Chicago 2024, Matt Godbolt offers a simplified view of modern CPU pipelines, branch prediction and memory, with a focus on x86 examples. He recommends measuring real workloads rather than relying on intuition or a simulator alone.

The front end fetches and decodes instructions; the execution machinery can run independent operations out of order while respecting dependencies. Retirement commits instructions in program order in the simplified model, even though execution may have been reordered.

A branch predictor guesses control flow early enough to keep a long pipeline supplied. Correct guesses avoid wasted work; a misprediction requires the processor to discard speculative work and restart on the correct path.

Register renaming reduces false dependencies caused by reusing architectural registers. Multiple execution units can work in parallel when their inputs and resources are available.

Godbolt gives a high-level account of predictors using branch locations and history. He compares a loop over random data with the same data sorted, illustrating that predictable control flow can affect runtime even through a language interpreter.

A Bloom filter example introduces a probabilistic set test: it can say definitely absent or possibly present, allowing false positives. Godbolt uses the example to inspect the cost of operations in an execution pipeline.

In Compiler Explorer he uses llvm-mca to simulate instruction scheduling. A dynamic modulus can lead to expensive division in his example; choosing a power-of-two table size allows a mask, but that choice can affect hashing behavior and must be evaluated for the application.

The compiler may replace division by a known constant with a sequence of multiplications and shifts. The details depend on the compiler, target and data types, so inspect generated code and benchmark before making changes.

Memory access and cache behavior can dominate runtime. In his linked-list experiment, sequential layout is much faster than randomized pointers because access patterns, dependencies and prefetching differ. The numbers describe his test, not every machine.

He closes with top-down performance analysis and perf counters to distinguish front-end, speculation, execution and memory bottlenecks. The talk covers one core and leaves multicore coherence and SIMD for further study.