Branch prediction

In short: Branch prediction guesses which way a program goes at a branch so the CPU pipeline does not have to wait for the result.

In more detail: Modern CPUs fetch and start instructions long before the condition’s result is known. If the prediction is right, execution continues without a pause. If it is wrong, the work is discarded, costing roughly 10 to 20 cycles.

In Depth

• Simplest form: A counter per branch remembers whether it was taken last time.
• Better: History-based predictors use the last branch outcomes as a pattern. Modern CPUs hit over 95 % of branches.
• Visible effect: Summing the values above 128 in an array is faster when the array is sorted, because the branch pattern then becomes predictable.
• Counter-measures in code: Branch-free formulations (conditional moves), sorted data, taking rare cases out of the hot loop.
• Security: Speculative execution led to flaws such as Spectre that required software and microcode mitigations.
• Context: Part of speculation alongside out-of-order execution.

See also: CPU structure