arthrop0d

Brief articles on varied topics.

CPU Branch Predictors and Speculative Execution

performance

A CPU branch predictor is hardware that guesses which way a conditional branch will go, and often where execution will continue, before the branch condition is known. The processor uses that guess to keep fetching and executing instructions instead of waiting for every decision.

The problem: branches interrupt the instruction stream

A modern processor does not finish one instruction before starting the next. It uses an instruction pipeline, a sequence of stages that fetch, decode, execute, and retire many instructions at once. This overlap increases throughput, but a branch makes the next instruction uncertain.

if (request_is_valid) {
    handle_request();
} else {
    reject_request();
}

The processor can fetch and decode the branch itself, but it may need to wait for request_is_valid to be loaded from a register or computed by an earlier instruction. Until then, it does not know whether the next instruction is in handle_request or reject_request.

Without prediction, the front of the pipeline would have to stop at many branches. The processor would eventually learn the answer, but several pipeline stages might sit idle. Since branches are common, that loss would significantly reduce performance.

A predictor makes a provisional choice so the processor can continue.

What the predictor records

The predictor maintains small hardware tables containing patterns from earlier executions. It does not normally store complete instructions or a high-level understanding of the program. It records clues such as:

The address of the current instruction is the program counter, commonly called the PC. The predictor uses some bits of the PC to find an entry in its tables. An entry often contains a small saturating counter: a value that moves toward “taken” or “not taken” after each outcome and does not change beyond its limits. A two-bit counter, for example, can require two contrary outcomes before changing a strong prediction.

That persistence matters. A loop usually takes its backward branch many times and then does not take it once when the loop ends. Remembering the recent pattern lets the predictor guess correctly most of the time.

A separate structure called a branch target buffer, or BTB, caches the destination address associated with a branch. Predicting “taken” is useful only if the processor can also quickly determine where the target is. For function returns, processors commonly use a return-address stack, which remembers likely return destinations separately from ordinary branch history.

Different CPUs combine these ideas in different ways. Some track the history of one branch; others use the outcomes of recent branches as context for predicting the next one. Table entries can also be shared by multiple branches when their addresses map to the same slot. This is called aliasing and can make otherwise unrelated branches interfere with one another. These implementation details vary, but the purpose is the same: use cheap records of the past to guess the near future.

How execution runs ahead

Consider a conditional branch whose condition is still being calculated. The predictor supplies two answers:

  1. whether the branch is likely to be taken; and
  2. which address should be fetched next.

The fetch unit follows that predicted path. Instructions fetched this way are speculative: they are being processed on the assumption that the prediction is correct, not because the branch has been confirmed.

The processor can decode these instructions and send their operations to execution units. Their results are held in internal structures rather than immediately made permanent. This prevents an incorrect path from changing architectural state such as the registers and memory visible to the program.

Meanwhile, the branch itself moves through the pipeline. Once its input values are available, the processor evaluates the real condition and computes the actual destination. The branch is then resolved, meaning the CPU now knows whether the prediction was correct.

If it was correct, the speculative instructions are allowed to continue toward retirement. Retirement is the ordered point at which completed instructions become the official state of the program. The prediction has effectively hidden the branch's waiting time.

The predictor also learns from the result. It updates its history and target information so that a later execution of the same or a similar branch can make a better guess.

What a misprediction costs

A branch misprediction occurs when the predicted direction or destination differs from the resolved branch. By then, the processor may have fetched and partially executed several instructions from the wrong path.

Those instructions cannot be retired as program results. The CPU discards them, clears the affected pipeline state, and redirects instruction fetch to the correct address. Fetch and decode must begin filling the pipeline with the correct path again. Work on independent instructions may also have consumed execution-unit capacity and entries in internal queues while it was speculative.

The result is a gap in useful progress. The cost is often described as a number of cycles, but it depends on the processor: deeper pipelines and more aggressive out-of-order designs generally have more work to discard. A predictable branch can be nearly hidden; an unpredictable branch in a hot loop can repeatedly interrupt forward progress.

A misprediction does not make the wrong instructions part of the program. It makes the CPU spend resources processing them before throwing them away.

This is why performance reports may mention branch-miss rates, and why profilers expose hardware counters for branches and mispredictions. A branch whose outcome follows a stable pattern is usually inexpensive. A branch driven by effectively random input, such as a filter over unsorted data, gives the predictor little reliable history and can cost much more than its source-code size suggests.

← All articles