Benchmark Branch Misprediction Overhead

Speculation Has a Cost

Modern CPUs fetch ahead of resolved branches. A misprediction flushes the pipeline, wasting 10 to 20 cycles on typical cores. Tight loops with unpredictable conditions show the penalty clearly in benchmarks.

cCopy
Loading…

Measuring with perf

bashCopy
Loading…

A loop with 50/50 random branches might show ~50% miss rate and run several times slower than a biased or branchless version.

For this exercise, you will craft predictable vs unpredictable branch patterns and compare retired instructions per cycle. This task asks you to tie measured branch-misses events to the 2-bit predictor you implement next.

Working Through the Exercise

Keep the relevant datasheet, ISA manual, or architecture textbook chapter open while you implement. When your output disagrees with the reference trace on the same program, the bug is usually a mis-decoded opcode, a stale register read, or a flag bit left unchanged after arithmetic.

• Trace first: walk one failing input by hand before changing random lines
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

For this exercise, you will use those habits while implementing the requirement in the starter code. Microarchitectural product names change across CPU generations, but the control ideas (fetch, bypass, cache lines, vector lanes) stay stable enough to debug from first principles.