Concepts and theorems · Intermediate

Branch predictors: choose a path before the condition is resolved

Separate prediction, speculation and retirement when reasoning about branch costs and optimizations.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Continue before the outcome is known
  2. Compare predictable and irregular traces
  3. Branchless code has other costs
  4. Use counters with equivalent work
  5. Ask Logeia about this articleCheck your understanding

Continue before the outcome is known

Waiting for every branch outcome before fetching the next instructions can leave a pipeline without useful work. A branch predictor chooses a likely direction or target using information such as previous outcomes, allowing speculative work to start earlier. Executing a predicted path is different from committing its effects as the program’s architectural result. The processor must still preserve the required execution semantics. If the prediction proves wrong, work from the incorrect path is discarded and fetching is redirected. This improves average progress when predictions are useful, but introduces a recovery cost when they are not.

Compare predictable and irregular traces

Imagine a loop branch that continues 999 times and exits on its thousandth evaluation. A predictor that learns useful history may let most iterations proceed without waiting for the branch to resolve. The same instruction can behave differently when inputs generate an irregular outcome sequence. Yet a fifty-fifty split of taken and not-taken outcomes does not by itself mean unpredictability: an alternating pattern may be learnable. Predictability depends on the sequence and predictor design, not just the aggregate proportion. Keep the representative input trace when comparing two implementations or changing data ordering.

Branchless code has other costs

Replacing a branch with a conditional selection or mask operation can reduce misprediction costs, but may perform work that the original path skipped or create a longer dependency chain. It is not safe to evaluate both sides when one side has side effects, invalid memory accesses or language-defined exceptions. Overflow rules and other semantics also matter. Branchless code is therefore a candidate transformation with specific conditions, not a universally faster style. Compare the cost of extra work against prediction and recovery behaviour while preserving the required observable result for every valid input.

Use counters with equivalent work

Measure branch counts, misprediction counts and elapsed work with equivalent inputs. A fixed penalty per misprediction is not portable across processors and can depend on surrounding work and dependencies. Speculation also raises security questions about microarchitectural traces, which are separate from whether wrong-path architectural results are discarded. A performance improvement does not establish that secret-dependent code is safe. Keep those questions distinct: throughput measurements describe execution cost, while confidentiality analysis considers what an observer can infer. Both require an explicit model of the hardware and the input-dependent behaviour being examined.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 7

Prepare for AI systems · STEP 4

Choose a learning path