Speculative execution: Worked examples — Hardware deep dive

This is the hands-on companion to Speculative execution. The parent note told you what speculation is and why CPUs gamble on branches. Here we drill the arithmetic: for every kind of branch a program can throw at a CPU, we compute the exact cycle cost, decide whether speculation wins or loses, and prove it.

Before we touch numbers, four quantities do all the work. Let's earn each symbol.

Definition The four numbers every example uses

Pipeline depth $D$ = the number of stages an instruction passes through from the moment it is fetched to the moment it commits (writes its result to architectural state). Picture a conveyor belt with $D$ workstations in a fixed order — fetch, decode, rename, issue, execute, … , commit. At any instant there can be up to $D$ different instructions on the belt, each frozen at a different workstation. Two clarifications that matter later: (i) $D$ counts all stages including fetch and commit, not just execution; (ii) an instruction only leaves the belt (frees its Reorder buffer (ROB) slot) at the final commit stage, which is exactly why speculative results can sit half-finished on the belt and be thrown away cheaply. If $D = 15$ , up to 15 partially-done instructions occupy the belt at once.
Misprediction penalty $P$ = the cycles lost when a guess is wrong (derived below). From the parent note, $P = D + R$ where $R$ is the refetch latency (1–3 cycles to grab the correct instruction from cache). We use $P = 17$ (so $D = 15$ , $R = 2$ ) unless told otherwise.
Prediction accuracy $a$ = the fraction of branches guessed correctly, a number between $0$ and $1$ . Its partner is the miss rate $m = 1 - a$ .
Stall cost $S$ = the cycles a CPU wastes if it refuses to guess and instead waits for the branch condition to resolve. Crucially, $S$ is not a free parameter: it is fixed by which pipeline stage computes the branch condition. Call that the resolve stage $r$ (counting from the fetch stage as stage $1$ ). Then $S = r - 1$ : the CPU can't fetch the next correct instruction until stage $r$ produces the answer, so it idles for the $r - 1$ cycles in between. A branch resolved early (near the front of the pipeline) has a small $S$ ; one resolved late has a large $S$ . This is why $S$ differs between examples — it tracks where in the pipeline the branch lives, not an arbitrary choice.

One derived idea ties $a$ , $m$ and $P$ together: the average cost per branch. $avg cost = m \times P = (1 - a) P$ Why multiply? Only the fraction that miss pays the penalty $P$ ; the correct ones pay $0$ extra. Multiplying "how often we pay" by "how much we pay" is the definition of an expected (average) cost.

Formula Why the penalty is

$P = D + R$ (and the precise version) When a branch mispredicts, two distinct things happen — the penalty is their sum.

Flush the wrong work: Between the stage where the branch was fetched and the resolve stage $r$ where its condition is finally known, the pipeline kept fetching from the predicted path. Every instruction fetched in those $r - 1$ cycles is on the wrong path and must be squashed — its partial result in the Reorder buffer (ROB) discarded before it can commit. So the precise flush count is $r - 1$ , not $D$ .
Refetch the right path ( $R$ cycles): The front of the pipeline now fetches from the correct target — an instruction-cache hit, $R \approx 1$ – $3$ cycles (see Pipeline hazards).

The exact penalty is therefore $P = (r - 1) + R$ . We quote the headline formula $P = D + R$ because it is the worst case: it assumes the branch resolves at the last stage, i.e. $r - 1 = D$ , so the whole belt is wrong. Textbook branches (compare-and-jump whose operands are ready) resolve much earlier, so their real penalty is smaller — this is exactly the gap Example 7 exploits. When an example gives you $r$ , use $P = (r - 1) + R$ ; when it just says "penalty $P$ ", that number already bundles the resolve stage in for you.

Definition The 2-bit saturating counter (used in Example 2)

A branch predictor needs a tiny memory of "what did this branch do last time?". The simplest useful one is a 2-bit saturating counter: a single number that can hold four states, from most-confident-taken to most-confident-not-taken: $3 = strongly taken, 2 = weakly taken, 1 = weakly not-taken, 0 = strongly not-taken$ Rules: after a branch is actually taken, add $1$ (but never above $3$ ); after not-taken, subtract $1$ (never below $0$ ). "Saturating" means it sticks at the ends — it cannot overflow past $3$ or under $0$ . Prediction rule: predict taken when the counter is $\geq 2$ , not-taken when $\leq 1$ . Why two bits and not one? A 1-bit predictor flips its guess on every single miss, so it mispredicts twice on a loop (once entering, once exiting). Two bits add hysteresis: one surprise nudges the counter but does not flip the prediction, so a single anomaly (like a loop exit) costs only one miss, not two. That hysteresis is the whole reason Example 2 has exactly one miss.

The scenario matrix

Branches don't come in infinite varieties — they come in a handful of behaviour classes. This table is the full list. Every cell gets a worked example below.

Cell	Case class	What makes it special	Example
A	Correct guess ( $m = 0$ )	best case, penalty never paid	Ex 1
B	Single wrong guess in a long run	one miss amortised over many hits	Ex 2 (loop)
C	50/50 unpredictable ( $a = 0.5$ )	worst realistic case, gamble may lose	Ex 3
D	Degenerate: $a = 1$	limiting value, penalty term vanishes	Ex 4
E	Degenerate: $a = 0$ (always wrong)	pathological, penalty every time	Ex 4
F	Break-even point	the exact accuracy where gamble = stall	Ex 5
G	Real-world word problem	mixed branch mix in real code	Ex 6
H	Exam twist: deeper pipeline	$P$ grows, changes the verdict	Ex 7
I	Security cell (correctness, not speed)	Spectre leak count, not cycles	Ex 8

Now we work every cell.

Worked example Example 1 — Cell A: the perfect guess

A branch is predicted taken and the condition indeed comes out taken. Pipeline depth $D = 15$ , penalty $P = 17$ . What is the extra cost of this branch versus a magical CPU that knew the answer for free?

Forecast: Guess before reading on — is the cost $17$ , $0$ , or something in between?

Identify the miss rate. The guess is correct, so $m = 0$ . Why this step? $m$ is the only thing that unlocks the penalty; if it's zero, nothing else matters.
Apply the average-cost formula. $cost = m \times P = 0 \times 17 = 0$ cycles. Why this step? The formula says only misses pay; a hit costs the same as knowing the answer.
Interpret. The speculated instructions were already in the Reorder buffer (ROB) and simply commit. No flush, no refetch.

Verify: Sanity check — a correct prediction is by definition indistinguishable in cost from perfect knowledge, so $0$ extra cycles is right. Units: cycles $\times$ dimensionless fraction = cycles. ✓

Worked example Example 2 — Cell B: one miss in a long loop

for (int i = 0; i < 100; i++) { sum += array[i]; }

The loop branch $i < 100$ is taken 99 times and not taken once (the exit). Penalty $P = 17$ . This branch is resolved at the very last stage ( $r = 16$ in a $D = 15$ pipeline, so its condition depends on the loop counter finishing execution), giving a stall cost $S = r - 1 = 15$ cycles — a full pipeline drain. Compare speculation against a CPU that stalls that $S = 15$ cycles on every iteration.

Forecast: How many total stall cycles does each strategy burn?

Count the branches. The branch executes once per iteration → $100$ times. Why this step? Cost scales with branch count, so we need it first.
Count the misses. Trace the 2-bit counter (defined above). It starts "weakly taken" ( $= 2$ ); each taken iteration adds $1$ and saturates at $3$ ("strongly taken") within two iterations, and stays there predicting taken correctly for iterations 0–98. On the final check $i$ becomes $100$ , so the branch is not taken while the counter still predicts taken → exactly 1 miss. Because the counter has hysteresis it does not double-miss on that single anomaly. Why this step? This is Cell B's whole point: the pattern is regular except for one boundary, and the 2-bit design guarantees that boundary costs one miss, not two.
Speculation cost. $1 miss \times 17 = 17$ cycles total. Why this step? Direct application of penalty-per-miss.
Stall cost. $100 branches \times S = 100 \times 15 = 1500$ cycles. Why this step? Because this branch resolves at the last stage ( $S = 15$ ), the safe CPU idles a full pipeline depth on every branch, hit or not.
Stall-cycle ratio. $\frac{1500}{17} \approx 88.2$ : speculation wastes about $88 \times$ fewer stall cycles than always-stalling. Why this step? This is a ratio of wasted cycles, not overall program speedup — the real end-to-end speedup is smaller because useful work runs in both cases. We report it purely to show how dramatically the stall overhead shrinks.

Look at the figure: the tall black bar is stalling (1500), the tiny red sliver is speculation (17). The red bar is the whole reason speculation exists.

Verify: $100 \times 15 = 1500$ ✓; $1 \times 17 = 17$ ✓; $1500/17 = 88.2 \dots$ ✓. Units: (branches)(cycles/branch) = cycles throughout. ✓

Worked example Example 3 — Cell C: the coin-flip branch

if (rand() % 2 == 0) process_even(); else process_odd();

Accuracy $a = 0.5$ (pure guessing). Penalty $P = 17$ . Here the condition (rand() % 2) is computed early — the value is already sitting in a register, so the compare resolves at stage $r = 3$ , giving stall cost $S = r - 1 = 2$ cycles. Which strategy wins?

Forecast: Guess before computing — does speculation help or hurt here?

Miss rate. $m = 1 - a = 1 - 0.5 = 0.5$ . Why this step? Half of all guesses are wrong for a coin flip.
Gamble cost. $(1 - a) P = 0.5 \times 17 = 8.5$ cycles per branch on average. Why this step? Expected penalty of speculating.
Safe cost. Because this branch resolves early (stage $r = 3$ ), stalling costs only $S = 2$ cycles per branch, always. Why this step? $S$ comes straight from the resolve stage; an early-resolving branch is cheap to wait on.
Compare. $8.5 > 2$ , so speculation LOSES by $6.5$ cycles per branch. Why this step? This overturns the naive "speculation is always good" belief — Cell C is where it fails, precisely because the stall alternative is so cheap here.

Verify: $0.5 \times 17 = 8.5$ ✓; $8.5 - 2 = 6.5$ ✓. This is why real chips ship confidence estimators that fall back to stalling when the predictor is unsure. Units: cycles vs cycles. ✓

Worked example Example 4 — Cells D & E: the two degenerate extremes

Same branch, same $P = 17$ , but two limiting accuracies. Compute the average penalty at $a = 1$ (perfect) and $a = 0$ (always wrong).

Forecast: At the two extremes, what are the costs — and is $a = 0$ really the maximum possible penalty?

Cell D, $a = 1$ . $m = 1 - 1 = 0$ , so cost $= 0 \times 17 = 0$ cycles. Why this step? This is the limiting best case; the penalty term is switched fully off.
Cell E, $a = 0$ . $m = 1 - 0 = 1$ , so cost $= 1 \times 17 = 17$ cycles every branch. Why this step? This is the limiting worst case; you pay the full penalty each time.
Bound the whole formula. Since $m$ ranges over $[0, 1]$ , the average cost $(1 - a) P$ is trapped in $[0, P] = [0, 17]$ . Why this step? It proves no branch can ever cost more than the full penalty $P$ — a useful sanity ceiling.

Verify: $(1 - 1) \cdot 17 = 0$ ✓; $(1 - 0) \cdot 17 = 17$ ✓; and $0 \leq 8.5 \leq 17$ places Example 3 correctly inside the bound. ✓

Worked example Example 5 — Cell F: the break-even accuracy

Take the same early-resolving branch as Example 3, so its stall cost is $S = 2$ (resolve stage $r = 3$ ), with $P = 17$ . At what accuracy $a$ does speculation exactly equal that 2-cycle stall? Below this, speculation is a net loss.

Forecast: Guess whether the break-even accuracy is closer to 50% or to 90%.

Set gamble = safe. $(1 - a) P = S \Rightarrow (1 - a) \cdot 17 = 2$ . Why this step? Break-even is defined as the point where both strategies cost the same; we use the same $S = 2$ as Example 3 because it is the same branch.
Solve for the miss rate. $1 - a = \frac{2}{17} \approx 0.1176$ . Why this step? Isolate the miss rate first; it's what the penalty multiplies.
Solve for accuracy. $a = 1 - \frac{2}{17} = \frac{15}{17} \approx 0.882 = 88.2%$ . Why this step? Convert miss rate back to the accuracy the hardware quotes.

The red line in the figure is the gamble cost $(1 - a) \cdot 17$ falling as accuracy rises; the black horizontal line is the fixed stall cost $2$ . They cross at $88.2%$ — left of the cross, stall; right of it, speculate.

Verify: $(1 - 15/17) \cdot 17 = (2/17) \cdot 17 = 2$ ✓ equals $S$ . And $15/17 = 0.882 \dots$ ✓. This explains why chips need $> 88%$ accuracy on a short-stall branch to justify the gamble. ✓

Worked example Example 6 — Cell G: real-world mixed workload

A program runs $1, 000, 000$ branches. $80%$ are loop/biased branches at $a = 0.98$ ; $20%$ are data-dependent branches at $a = 0.60$ . Penalty $P = 17$ . How many total cycles are lost to mispredictions, and what is the overall miss rate?

Forecast: Guess the overall accuracy — is it closer to 98% or dragged down toward the 60% group?

Split the branches. Predictable: $0.80 \times 1 0^{6} = 800, 000$ . Data-dependent: $0.20 \times 1 0^{6} = 200, 000$ . Why this step? Each group has its own miss rate, so we cost them separately.
Misses in each group. Predictable: $800, 000 \times (1 - 0.98) = 16, 000$ . Data-dependent: $200, 000 \times (1 - 0.60) = 80, 000$ . Why this step? Miss count = branches × miss rate, per group.
Total misses & cycles. $16, 000 + 80, 000 = 96, 000$ misses; cost $= 96, 000 \times 17 = 1, 632, 000$ cycles. Why this step? Add the groups, then apply the shared penalty.
Overall miss rate. $\frac{96 , 000}{1 , 000 , 000} = 0.096 = 9.6%$ , so overall accuracy $= 90.4%$ . Why this step? Shows the "small" 20% bad-branch slice dominates the misses (80k of 96k), pulling accuracy well below 98%.

Verify: $16000 + 80000 = 96000$ ✓; $96000 \times 17 = 1632000$ ✓; $96000/1 0^{6} = 0.096$ ✓. Note $80000 > 16000$ — the unpredictable minority causes most of the pain. ✓

Worked example Example 7 — Cell H (exam twist): the deeper pipeline

An exam gives you a 20-stage pipeline with refetch $R = 4$ , so the worst-case $P = 20 + 4 = 24$ . A branch has accuracy $a = 0.90$ . Its condition resolves at stage $r = 4$ — the same early resolve as the register-ready compares of Examples 3 and 5, because it too is a simple compare-and-jump whose operands are already in registers, so its condition is known by stage 4 regardless of how deep the rest of the pipeline is. That gives stall cost $S = r - 1 = 3$ cycles. Does the deeper pipeline flip the speculate/stall verdict?

Forecast: Deeper pipelines are "better" for throughput — but do they make speculation safer or riskier?

Worst-case penalty. $P = 20 + 4 = 24$ cycles. Why this step? Deeper pipeline ⇒ more stages to potentially flush ⇒ bigger worst-case $P$ . We use $P = 24$ as the headline number the exam quotes.
Stall cost. The branch resolves at stage $r = 4$ , so $S = r - 1 = 3$ cycles — this depends only on the resolve stage, not on the total pipeline depth. Why this step? Note the asymmetry: deepening the pipeline blew up $P$ but left $S$ untouched, because the condition still resolves at the same early stage 4.
Gamble cost. $(1 - 0.90) \times 24 = 0.10 \times 24 = 2.4$ cycles. Why this step? Same average-cost formula, new $P$ .
Compare to stall. $2.4 < 3$ , so speculation still wins — but only by $0.6$ cycles. Why this step? Reveals the twist: deeper pipelines raise $P$ while $S$ stays fixed, shrinking speculation's margin toward zero.
Contrast with the shallow chip. On $P = 17$ with the same $S = 3$ : gamble $= 0.10 \times 17 = 1.7 < 3$ , margin $1.3$ . Why this step? Same accuracy and same resolve stage, but the deeper pipeline more than halves the safety margin ( $1.3 \to 0.6$ ) — the lesson the exam is testing: deeper pipelines make each misprediction hurt more, so they demand ever-better predictors.

Verify: $20 + 4 = 24$ ✓; $0.10 \times 24 = 2.4$ ✓; $0.10 \times 17 = 1.7$ ✓; margins $3 - 2.4 = 0.6$ and $3 - 1.7 = 1.3$ ✓. Deeper pipeline = higher misprediction stakes, unchanged stall cost. ✓

Worked example Example 8 — Cell I: the security cell (correctness, not cycles)

A Spectre-style cache side-channel leaks one byte at a time. Reading each byte requires the attacker to correctly distinguish which of $256$ possible values got pulled into cache, using a timing probe. If probing all 256 cache lines takes $256 \times 200 = 51, 200$ cycles per byte, how many cycles to leak a $16$ -byte secret key, and how does this cell differ from all the above?

Forecast: Guess — is this a performance question or a correctness question?

Cycles per byte. One probe sweep = $256 \times 200 = 51, 200$ cycles. Why this step? Each of 256 possible byte values maps to one cache line to time; the fast (already-cached) line reveals the value.
Total for the key. $16 \times 51, 200 = 819, 200$ cycles. Why this step? Bytes leak independently, so multiply per-byte cost by key length.
The categorical difference. Cells A–H all asked "is speculation fast?" This cell asks "is speculation safe?" Recall from the four-numbers box that a speculative instruction leaves the belt only at commit — so a squashed wrong-path load never commits, yet it already pulled a secret-indexed line into the cache. That footprint in microarchitectural state survives the rollback and is measurable by timing. Why this step? This is the whole point of Cell I: the architectural result is perfectly correct, and speculation still leaks the secret through the cache — a correctness/security failure with zero cycle-count symptom in the program itself.

In the figure, the red cache line is the one the secret byte touched — every other line is cold (slow); the hot red line is fast, and its position is the secret.

Verify: $256 \times 200 = 51200$ ✓; $16 \times 51200 = 819200$ ✓. Units: (lines)(cycles/line)(bytes) = cycles. This is why mitigations (lfence, retpolines, predictor flushing) exist even though speculation never corrupts architectural state — see the parent note's Spectre discussion. ✓

Recall Quick self-test

Average penalty formula ::: $(1 - a) P$ , where $a$ is accuracy and $P$ is the misprediction penalty. Precise vs headline penalty ::: Precise $P = (r - 1) + R$ ; headline $P = D + R$ is the worst case where the branch resolves at the last stage ( $r - 1 = D$ ). What sets the stall cost $S$ ::: The resolve stage $r$ where the branch condition is computed; $S = r - 1$ . Early-resolving branches are cheap to stall on, late ones expensive. Why a 2-bit counter misses only once at loop exit ::: Its hysteresis means one surprise nudges but does not flip the prediction, so a single anomaly costs one miss, not the two a 1-bit predictor would. Speculate-vs-stall rule ::: Speculate only when $(1 - a) P < S$ . Break-even accuracy for $P = 17$ , $S = 2$ ::: $a = 1 - 2/17 = 15/17 \approx 88.2%$ . Why a deeper pipeline is riskier for speculation ::: It increases the worst-case $P$ while $S$ (set by the resolve stage) stays fixed, so the same miss rate costs more cycles and the margin over stalling shrinks. Which cell is about correctness not speed ::: Cell I — Spectre-style cache side channels; a squashed speculative load still leaves a cache footprint.

See also: Speculative execution · Out-of-order execution · Instruction-level parallelism (ILP) · Superscalar architecture · Pipeline hazards