Skip to content

The branch predictor learns your benchmark

Level: 301 · deep dive

Stub — an outline, not a lesson. There is no runnable example behind this page yet, so nothing on it has been through the check that backs every other claim in this library. The bullets below are the questions the finished page has to answer.

One line: Run a benchmark on the same input again and again and the CPU's branch predictor memorises it — so below some size you measure a program whose branches are free, and above it one whose branches are not.

The questions this page has to answer

  • The talk's state_machine benchmark has two states and four data-dependent paths. Why does its cost per element jump at a data size that depends on the CPU — 8K elements on a Comet Lake laptop, 16K on Lunar Lake, and barely at all on an AMD EPYC virtual machine, per the talk's notes?
  • How does the sorted control — the same values, the same memory, predictable branches — prove the jump is the predictor and not the cache?
  • What perf stat shows: the branch-miss rate climbing from 0.02% to 18.10% while the instruction count stays the same.
  • Which behaviour is the question — a warm predictor or a cold one — and how do you feed a benchmark unpredictable input without timing the random-number generator?
  • This library's measuring machine, an Intel Core i5-10500, is a Comet Lake too. Does the cliff reproduce here, at the same size?

In the talk

Confounding factors (slide source ↗).

See also