A pipelined CPU must fetch instructions before a branch outcome is known. It predicts a direction and discards wrong-path work if the guess is incorrect. Better predictions reduce this wasted work.
A simulator comparing three predictors on identical branch outcomes
1. Choose an outcome pattern (T = taken, N = not taken)
2. Process branches one at a time
The top row shows actual outcomes; the next three show prior predictions. Green is correct and red is incorrect. The diagram shows the two-bit predictor's current state.
A one-bit predictor misses twice around a loop boundary
A one-bit predictor repeats the previous outcome. A loop is mostly T followed by one N: it misses that N, then predicts N and misses the first T of the next run.
A two-bit predictor tolerates a single exception
A two-bit saturating counter has four states. From strongly taken, one N moves it only to weakly taken, which still predicts T. Two consecutive N outcomes are needed to reverse a strongly taken prediction. This reduces loop-boundary misses, though simple predictors can still struggle with alternating patterns.
Branch prediction in code
On a sorted array, repeatedly evaluating if (x >= 128) produces long runs of N and T that are easy to predict. Random order can be much harder and may slow branch-heavy code. The effect depends on the CPU and compiler; branchless transformations or data layout can help. Mispredictions discard work in the Pipeline , so deeper pipelines can have a greater penalty.