--- title: "Branch Prediction" description: "Speculative execution and misprediction cost" source: https://vizlearn.app/cs/architecture/branch-prediction access: premium (interactive player requires Lifetime; this doc is free) --- # Branch Prediction Branch prediction is how a pipelined CPU keeps working through a conditional jump it has not resolved yet. It guesses which way the branch will go, fetches instructions down the guessed path, and discards that work if the guess is wrong. A two-bit counter per branch site is right most of the time on real code, where branches repeat. Think of a short-order kitchen. A regular customer orders the same thing every Tuesday, so the cook starts it before the order arrives. Usually the plate is ready early and everyone wins. Occasionally the customer orders something else, and the cook scrapes a half-finished dish into the bin. The cost of being wrong is not one wasted second — it is however much food was already on the stove. A CPU's stove holds one instruction per pipeline stage, and modern stoves are deep. ## How Branch Prediction Works A five-stage pipeline fetches a new instruction every cycle: IF, ID, EX, MEM, WB. A conditional branch computes its condition in EX, which is two cycles after it was fetched. By then the fetcher has already pulled in two more instructions, and it had to pull them from *somewhere* — either the instruction right after the branch, or the branch's target. Nobody knows which is correct yet. That is the whole problem, and it exists because fetching is fast and deciding is not. You have two options. Stall the fetcher until the branch resolves, and pay two dead cycles on every single branch — including the ones that were completely predictable. Or guess, keep fetching, and pay only when the guess is wrong. Nearly every pipelined processor built for speed in the last thirty years guesses. The guess comes from a small table indexed by the branch's address. This lesson shows one entry, because the interesting behaviour is what a *single* entry does over time. Three ways to fill it, and the lesson runs all three over the same history: **Always taken** stores nothing. A branch at the bottom of a loop jumps backwards, and a loop that runs `n` times takes that branch `n − 1` times out of `n`, so "always taken" is right `(n − 1)/n` of the time — far better than a coin on a long loop, and no better than one at `n = 2`. It is wrong exactly once per loop, at the exit. **One bit of history** stores the last outcome and predicts it again. It learns, which sounds strictly better, and it has one catastrophic weakness: a single surprise wipes out everything it knew. **Two bits** store a saturating counter from 0 to 3. The high bit is the prediction — 2 and 3 mean taken, 0 and 1 mean not taken. Each outcome nudges the counter one step toward what actually happened, and it saturates rather than wrapping. Picture the four values in a row with a line drawn down the middle: which side of the line you are on is the prediction, and how far you are from the line is how much evidence it would take to change your mind. From either end, one surprise steps you toward the line and a second in a row crosses it; from a weak state next to the line, one surprise is enough. That reluctance is the entire design, and it is worth exactly one thing: a loop that ends does not convince the predictor that loops never repeat. ## Branch Prediction Step by Step The default run watches one branch — the `blt` closing an inner loop of four trips — while an outer loop enters it three times. The outcomes are taken, taken, taken, not taken, repeated three times. The predictor is a two-bit counter starting cold at `00`, strongly not taken, which is a machine that has never seen this branch before. Each iteration issues four instructions, and a misprediction costs two. 1. **Execution 1.** The counter reads `00`, so the guess is NOT TAKEN and the fetcher runs straight past the branch. The loop is on its first trip, `j = 1 < 4`, so the branch is taken — wrong. The two instructions behind it are squashed, two cycles are gone, and the counter moves `00 → 01`. Note what did *not* happen: the prediction is still NOT TAKEN. One surprise moved the counter without changing its mind. 2. **Execution 2.** Same guess, same outcome, wrong again. The counter moves `01 → 10` and crosses the line. Those two misses are the price of hysteresis, paid once, on a cold entry. 3. **Execution 3.** The counter reads `10`, the guess is TAKEN, and the branch is taken. Nothing is squashed and the counter saturates upward to `11`. 4. **Execution 4.** `j = 4`, so the loop exits and the branch is not taken. The guess was TAKEN, so this one is wrong: squash, two more cycles. The counter steps back `11 → 10` — still on the taken side. 5. **Execution 5.** The outer loop re-enters, and the branch is taken again. The counter still reads `10`, so the guess is TAKEN and it is right. **This is the beat the whole lesson exists for.** A one-bit predictor would have flipped to NOT TAKEN at the exit and mispredicted here. The counter absorbed the exit as noise. 6. **Executions 6 and 7** are taken and predicted taken. The counter is already at `11`, so the updates do nothing — extra evidence for something you are already sure of is free. 7. **Executions 8 through 12** repeat the pattern exactly: one miss at each loop exit (executions 8 and 12), everything else correct. Final tally: 5 mispredictions out of 12, 58 cycles of which 10 were spent on work that got thrown away — 17% of the run. Three of those five misses were loop exits, which no predictor in this lesson avoids. Two were the cold start. The final frame puts all three predictors on that same history side by side, and the counts are worth sitting with. The one-bit history misses 6 times, and *where* it misses matters more than the count: it misses in pairs, at every loop boundary — the exit, and then the re-entry it flipped itself out of. Always-taken misses 3 times, only at the exits, which makes it the best of the three on this input. That is not a bug in the lesson. On a pure loop, "assume the backward branch repeats" is already an excellent heuristic, and it is why static prediction survived as long as it did. Dynamic predictors earn their keep somewhere else — on the sorted data below, always-taken misses six times and the two-bit counter misses twice. ## Why a Misprediction Costs More Than One Cycle The penalty is not a property of the branch. It is the number of instructions the machine had already fetched when the verdict arrived, which is the depth at which the branch resolves. Here that is two. On a modern core that resolves branches a dozen or more stages in, the same five mispredictions would cost about sixty cycles instead of ten. Deeper pipelines buy clock speed and sell it back every time they guess wrong, which is why prediction accuracy became a first-class design problem rather than a footnote. The arithmetic is short: cycles = instructions + penalty × mispredictions. For B branch executions, losing five percentage points of accuracy adds 0.05 × B × penalty cycles. A penalty of 20 makes that extra cost ten times the cost at a penalty of 2; its share of the program also depends on branch frequency. ## Sorted vs Shuffled: Same Values, Different Predictability Both data scenarios run the branch `v >= 128` over the same twelve values. One has them sorted, the other shuffled. Nothing else moves: same code, same instructions, same comparisons, same number of takens. Sorted, the history is six not-takens followed by six takens — one transition in the entire run. The two-bit counter mispredicts twice, on the first two taken outcomes after that turn, and the one-bit history mispredicts only once, because a single transition is the one case where having no hysteresis is an advantage. Shuffled, there is no pattern to hold. The counter mispredicts seven times, which is worse than always-taken's six: chasing noise costs more than ignoring it. Fifty-two cycles against sixty-two, from the ordering alone. This is the mechanism behind the most-asked question in the topic, "why is processing a sorted array faster than an unsorted one." The gap is only 19% here because the penalty is two and the loop body is four instructions. The benchmarks people cite show several times that, and the arithmetic says why: on a core where a misprediction costs fifteen or twenty cycles and the body is a handful of instructions, the mispredictions *are* the runtime. ## Edge Cases - **A cold entry guesses from its initial state, not from evidence.** The first execution of a branch is decided by whatever the table was reset to — here `00`, which predicts NOT TAKEN. The guess is perfectly deterministic; what it is not is informed. It matters when a branch runs a handful of times and disappears when it runs a million. - **The default loop pays for each exit.** The last trip is not taken while every previous trip was, and none of the three predictors here gets it right, so this repeated four-trip loop entered `k` times contributes exactly `k` exit mispredictions — three of the default run's five. Real cores do better than that: a loop predictor that learns the trip count, or a global-history predictor that recognises the surrounding branches, can call the exit correctly. - **A saturated counter ignores agreement.** At `11`, another taken branch changes nothing. The counter is not counting occurrences; it is holding a position. - **A perfectly alternating branch defeats one-bit history completely.** Taken, not taken, taken, not taken: what just happened is never what happens next, so a one-bit predictor is wrong on all 12 executions — worse than a constant. Starting at 00 in this preset, the two-bit counter alternates between 00 and 01, keeps predicting not taken, and gets half of them. - **Real tables alias.** Two branches whose addresses collide share an entry and train each other. This lesson shows one entry and one branch, so aliasing never appears. ## Common Mistakes - **Thinking a misprediction costs one cycle.** In this model it costs two cycles, from the branch's fetch to EX resolution. Real recovery cost depends on branch-resolution latency, front-end recovery, and issue width; it is not simply the total pipeline depth. The branch instruction itself is cheap; what is expensive is everything fetched behind it. - **Treating a misprediction as an error.** Nothing is raised, nothing is logged, no result is wrong. The machine quietly redoes work it had already started. It is the most expensive thing a CPU does that a debugger will never show you. - **Assuming a smarter predictor always wins.** On this lesson's default loop, static always-taken beats both dynamic predictors — three misses against the one-bit predictor's six and the two-bit counter's five. History helps when there is history worth having. - **Trying to fix an unpredictable branch by optimizing its body.** If the branch is data-dependent on random data, no predictor recovers the loss. The fixes are to change the data, to change the code so there is no branch (a conditional move, arithmetic on the comparison result), or to accept the cost. Measure before picking one: sorting an array to help a single loop usually costs more than the loop saves unless you wanted it sorted anyway, and compilers often turn a short branchy body into branchless code without being asked. - **Reading the counter as a probability.** `11` does not mean "75% likely taken". It means "two consecutive not-takens away from changing my mind". It is a position, not an estimate. ## A Note on Simplification This lesson animates a deliberately small machine. It shows one branch site with one predictor entry; a real core carries a table of thousands indexed by branch address, usually combined with a branch target buffer and a tournament of several predictors picking whichever has been doing better lately. Modern designs use global history — what *other* branches did recently — because branches correlate with each other, which is a whole level this page does not touch. The pipeline is equally idealized: five stages, one instruction retiring per cycle, no cache misses, no data hazards, and branches resolved in EX. Real processors are deeper, execute out of order, and can have hundreds of instructions in flight when a branch resolves. The shape of the story survives all of that — guess, fetch, verify, discard — but the numbers on screen belong to the small machine. Treat this as an explainer, not a substitute for a computer architecture course.