liveBook · Manning

Branch prediction

As explained in The Coder Cafe

Branch prediction is a CPU technique that speculatively selects the likely path of a conditional control-flow instruction before its condition is resolved.

A conditional jump creates a problem for an instruction pipeline: the CPU may need to know the jump’s outcome before it can fetch the right next instruction. Waiting leaves the fetch unit idle. Branch prediction guesses the outcome early so fetching can continue. section 8.1.1

Consider a simple predictor that always guesses the jump will not be taken. If it is right, the pipeline keeps moving; in the worked timing example, that saves two cycles. If it is wrong, the CPU flushes the incorrectly fetched instructions and fetches from the correct path. The resulting gap is a pipeline bubble; the wrong guess costs three cycles in that example. These timings illustrate the tradeoff, not a fixed cost for every CPU. section 8.1.1

// Something before
if(a == 0) {
  foo()
} else {
  bar()
}
// Something after

The if/else listing shows why a conditional choice presents two possible instruction paths. section 8.1.1

Branch prediction improves instruction throughput by avoiding waits when a guess is correct, but a wrong guess wastes work. The always-not-taken rule is only a teaching example, not a description of modern prediction techniques. section 8.1.1 section 8.3

How The Coder Cafe covers it

How deep it goes
Works through correct and incorrect guesses, including cycle counts and pipeline flushing, but defers real predictor techniques.
Examples
Uses an if/else function call and an always-not-taken guess to contrast a two-cycle saving with a three-cycle loss.
What it assumes
Builds on conditional code and pipeline stages while defining conditional branches, stalls, and bubbles in context.
What you can do after
Evaluate/understand it by tracing how correct guesses avoid waits and incorrect guesses trigger pipeline flushes.
How it connects
Connects conditional jumps with instruction pipelining, instruction fetching, pipeline stalls, and pipeline bubbles.

Also explained in

Compare how 4 books explain branch prediction →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of The Coder Cafe. The section links point to the parts of the book it draws on.