Branch Predictor: gshare & 2-Bit Saturating Counters

Why Branch Prediction Exists

Pipelined CPUs split instruction execution into stages such as fetch, decode, execute, and writeback, so that multiple instructions are in flight simultaneously, each at a different stage. This overlap is what lets a chip issue an instruction nearly every cycle instead of waiting for one to fully finish before starting the next. The problem is that conditional branches do not reveal their outcome until relatively late in the pipeline, often at the execute stage, yet the fetch stage needs to know immediately which instruction comes next. Without any prediction, the pipeline would have to stall completely at every branch until the condition resolves, which on a 15-to-20-stage pipeline could waste a huge fraction of total execution time given that branches appear roughly every five to seven instructions in typical code. Branch prediction converts this stall into a bet: guess the direction, keep fetching and executing speculatively, and pay the penalty only when wrong. Because most branches are highly biased, loop backedges are taken the vast majority of the time and many if-conditions favor one outcome consistently, a well-designed predictor can be right well over 90 percent of the time on real workloads, turning what would be a severe bottleneck into a minor one. This single idea, more than almost any other microarchitectural technique, is responsible for the multi-gigahertz, deeply pipelined, high-IPC processors we use today.

The 2-Bit Saturating Counter

The simplest useful predictor state is a single bit per branch: taken or not-taken, updated to match the last outcome. But a single bit flips its prediction after just one anomaly, which hurts loops that are taken every iteration except the last one, since the final exit mispredicts and then the very next entry into the loop also mispredicts because the bit flipped. The fix, proposed in early predictor research and still used as a building block today, is the 2-bit saturating counter, a small state machine with four states typically labeled strongly-not-taken, weakly-not-taken, weakly-taken, and strongly-taken. Each correct taken prediction pushes the counter toward strongly-taken, and each correct not-taken prediction pushes it toward strongly-not-taken, but the counter saturates at the extremes rather than wrapping around. Crucially, a single mispredicting outcome only moves the counter one step, from strongly-taken to weakly-taken for instance, rather than flipping the prediction outright. This means a loop that is taken 99 times and not-taken once will only mispredict on that one anomalous iteration, then immediately return to predicting taken correctly, rather than mispredicting twice as a naive 1-bit scheme would. In the simulation, watch the counter value climb and fall as the loop executes, and notice how it takes two consecutive wrong outcomes in the same new direction before the prediction itself actually changes.

From Simple Counters to gshare

A table of 2-bit counters indexed purely by the branch's own address, called a bimodal predictor, works well for branches whose behavior is roughly constant, but it cannot capture correlations between branches. Many real branches depend on context: an if statement's outcome might depend on whether a previous, different branch was taken a few instructions earlier. The gshare predictor, introduced by Scott McFarling in 1993, captures exactly this correlation cheaply. It maintains a global history register, a shifting bit pattern recording whether each of the last N branches anywhere in the program was taken or not, and combines that history with the branch's own program counter using an XOR operation to produce an index into the counter table. Because the index now depends on both the branch's identity and the recent global pattern of branch outcomes, gshare can distinguish between the same branch appearing in different behavioral contexts, effectively giving it a much larger, more specialized set of counters without needing a separate table per branch. The XOR hashing also helps spread different branches across the table to reduce destructive aliasing, where two unrelated branches collide on the same counter and corrupt each other's predictions. This global-history approach was a major leap over purely per-branch schemes and directly influenced the tournament and TAGE predictors used in today's high-performance CPUs.

The Cost of Getting It Wrong

A misprediction is not free, and its cost scales directly with how deep and wide the pipeline is. When the branch finally resolves in the execute stage and disagrees with the earlier prediction, every instruction fetched and partially executed along the wrong path must be squashed, their effects discarded before they can modify architectural state, and the front end must restart fetching from the correct target address. The delay before useful instructions are flowing through the pipeline again is called the misprediction penalty, and on modern superscalar cores it commonly ranges from 10 to 20 cycles, sometimes more on very deep pipelines. If a branch mispredicts even 5 percent of the time and appears every six instructions, the average cycles-per-instruction overhead from mispredictions alone can rival the cost of memory stalls. This is why chip designers invest enormous transistor budgets, often more silicon area than the arithmetic units themselves, into ever more sophisticated predictors: perceptron-based predictors, TAGE with multiple history lengths, and loop predictors that detect fixed iteration counts directly. The simulation visualizes this penalty explicitly, showing the pipeline stages draining and refilling after a mispredicted guess, so the abstract cycle count becomes a visible stall you can watch happen.

Why Software Feels the Difference

Branch prediction is invisible in the sense that it never changes a program's correctness, only its speed, but that speed effect is large enough to shape how performance-conscious code is written. Sorting an already-sorted array is famously faster than sorting a random one partly because comparison branches become highly predictable once data is ordered. Replacing an unpredictable branch with branchless code, using bitwise arithmetic or conditional-move instructions to compute both outcomes and select between them, can be a genuine optimization technique precisely because it eliminates a source of pipeline flushes entirely. Compilers also use profile-guided optimization to lay out code so that the common path of a branch falls straight through in memory, which pairs well with prediction by making the fetch pattern simpler. Interpreters and virtual machines suffer particularly badly from branch mispredictions in their dispatch loops, since a bytecode interpreter's central switch statement is essentially a giant, hard-to-predict indirect branch, which is one reason just-in-time compilation and threaded dispatch techniques exist. Even database query engines and video codecs are tuned with an eye toward branch predictability. Once you can see, as this simulation shows, that a misprediction discards real completed work and stalls the entire pipeline for a dozen-plus cycles, the recurring advice to write predictable branches stops being folklore and becomes a direct, mechanical consequence of how hardware actually executes your code.

Frequently asked questions

Try it live

Everything above runs in your browser — open Branch Predictor: gshare & 2-Bit Saturating Counters and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.