Pipelines and branch prediction

1.6 Inside the core: the pipeline

Each instruction is fetched, decoded into internal operations, given renamed registers, held until its inputs are ready, executed, and finally retired, which makes its result visible. A modern core has 15–20 stages and, like an assembly line, works on many instructions at once.

Two features make it fast. It is superscalar: it retires four to six instructions per cycle and has several execution ports, including multiple ALUs and two or three load units. And it executes out of order. Instructions enter the reorder buffer in program order, execute whenever their inputs are ready, and retire in program order, so the program cannot tell. The buffer’s few hundred entries set how far ahead the core can look for independent work.

The limit is dependencies. If instruction B needs A’s result, B waits however many ports are idle. A dependency chain runs at the sum of its latencies.

Worked example: one accumulator or four

A floating-point add has a latency of about 3–4 cycles, and the core can start two per cycle. In sum1, each add needs the previous sum, so the loop completes one add every 4 cycles and the second adder idles. For 4,096 values (32 KB, resident in L1), that is about 16,000 cycles, roughly 4 µs. In sum4, four independent chains interleave, and the core completes about one add per cycle: roughly 1 µs. The instructions and data are the same. Only the dependency structure changed, and the loop is four times faster. Eight accumulators approach the limit of two adds per cycle.

Here sum1 means one loop-carried sum; sum4 means four partial sums combined after the loop. Four serial adds take about 16 cycles, while four independent chains can sustain about one add per cycle under the stated assumptions.

The compiler will not do this for floats. Floating-point addition is not associative, so reordering changes the last bits of the result, and Rust will not change your answer unasked. For integers it splits chains and vectorises by itself. The rounding difference also bites when reconciling P&L bit-for-bit: two correct sums of the same fills can disagree.

Chains hide in trading code too. Parsing an ASCII price digit by digit, v = v * 10 + d, costs about 4 cycles per digit, so an eight-digit field takes about 32 cycles however wide the core is. Section 1.9 shows how to break that chain.

What a stall looks like

When the oldest instruction in the reorder buffer is a load waiting on DRAM, nothing behind it can retire. Younger independent instructions still execute until, after about 100 cycles, the buffer is full. The core then idles for the remaining 250 or so cycles of the miss. perf stat shows this as low instructions per cycle (IPC): compute-bound code runs at 2–4 IPC, memory-stalled code at 0.2–0.5. An L1 or L2 hit is small next to the window, so the core stays busy; a DRAM miss is hidden only for its first hundred cycles.

1.7 Branch prediction

A conditional branch decides which instruction comes next, but the front of the pipeline fetches instructions 15–20 stages before the back computes the condition. Waiting would idle the core on every branch, and typical code has one every five or six instructions. So the core guesses and executes the guessed path speculatively. A right guess costs nothing. A wrong one means discarding everything after the branch and restarting: 15–20 cycles, about 4–5 ns.

How the predictor guesses

The simplest predictor keeps a small saturating counter per branch: if it has mostly been taken recently, predict taken. That handles biased branches. Modern predictors add history. The core records the outcomes of the last few dozen to few hundred branches as a string of bits, the global history, and combines it with the branch’s address to index tables of counters. It can therefore learn that a branch is taken after “taken, not-taken, taken”, or that a loop exits on its eighth iteration. Current designs keep several tables using different history lengths and trust whichever has been most accurate. Indirect branches, such as dyn Trait calls, get a similar structure that predicts the target.

Which branches are cheap and which are poison

Branches with a pattern are nearly free: a loop’s back-edge, an error check that never fires such as if seq != expected_seq { recover_gap() }, or any regular pattern the predictor can learn.

Branches on unpredictable data are poison. No predictor beats 50% on a coin flip. The expected cost is mispredict rate × penalty: 0.5 × 15–20 cycles, so 8–10 cycles on average per execution. A branch that goes one way 90% of the time costs about 0.1 × 17.5 ≈ 2 cycles once learned; at 99%, about 0.2.

Three branches from a book handler show the range.

• if side == Side::Bid picks a half of the book. Bids and asks arrive in close to random order, so it is near 50/50. Remove it by indexing: books[side as usize] turns two code paths into one.
• if new_best != old_best decides whether to requote. The top of book changes on perhaps 5–20% of updates, so the branch is mostly well predicted. It mispredicts at the moments that matter, but rarely enough not to contort the code.
• if qty == 0 { delete_level() } else { update_level() } follows the mix of cancels and modifies, which can reach 30–40% deletes. The arms do different work, so a select cannot replace it. A level-based book can encode deletion as quantity zero, but must still update the best-price cursor immediately if the deleted level was best; deferring that work would expose a stale quote.

Branch-free techniques in Rust

When a branch only chooses between two already available values, express the choice directly: let chosen = if condition { a } else { b };.

This form is readable, and LLVM normally compiles it to cmov, which selects between two registers without branching. “Normally” is the problem, so check. cargo asm, from the cargo-show-asm crate, prints one function’s assembly; objdump -d -M intel on the release binary also works. A cmov means a select. A conditional jump such as ja or jle inside the loop means a branch.

The honest caveat

Branch-free code does the work of both paths every time, and its result depends on both inputs, which lengthens dependency chains. A predicted branch lets the core skip one path and speculate past the decision. On predictable branches the branchy version is usually as fast or faster; Lab 1.2 shows this on sorted data. Branch-free is a tool for unpredictable branches, not a style. Measure with perf stat -e branches,branch-misses before and after.

One trading-specific trap: during a quiet market, other code retrains the predictor, and the first message after a lull mispredicts more than the thousandth. It is the cache’s cold-start problem again.