branch prediction and the misprediction penalty

A pipelined CPU fetches instructions many cycles before it executes them, but a branch (an if, a loop test, a function-pointer call) creates a problem: until the branch's condition is computed, the CPU does not yet know which instructions come next. Waiting for the answer would idle the whole pipeline on every branch — and branches are everywhere, roughly one in five instructions. So the CPU does not wait. It GUESSES, with a piece of hardware called the branch predictor, and speculatively keeps fetching down the guessed path.

The branch predictor learns patterns from a branch's history to predict, for each branch, whether it will be taken and, via the branch target buffer (BTB), what address it will jump to. Modern predictors are astonishingly good — well above 95% accurate on typical code — because most branches are highly regular (a loop is taken every iteration but the last; an error check is almost never taken). When the prediction is right, the speculatively-fetched instructions were the correct ones and there is essentially zero cost: the branch was effectively free. When the prediction is WRONG, everything fetched and executed down the wrong path must be thrown away — the pipeline is flushed — and fetching restarts from the correct target. That flush is the branch misprediction penalty, typically 15 to 20+ wasted cycles on a deep pipeline, because that is how many in-flight stages get discarded.

This asymmetry — a correctly predicted branch is nearly free, a mispredicted one costs a deep flush — is what makes branch behavior a real performance factor. A branch that is hard to predict (one that goes each way about half the time in no learnable pattern, classically branching on random or unsorted data) can cost an order of magnitude more than a predictable one, which is the famous reason that processing SORTED data can be much faster than the same code on shuffled data. It is also why branchless code exists: when a branch is genuinely unpredictable, replacing it with branch-free arithmetic removes the misprediction risk entirely.