Everything measured so far has been about what happens after an instruction is decoded. This concept is about the decision that happens before, and it is the decision a modern CPU makes most often and most aggressively: where is the next instruction?
And the answer is that the core does not know. It guesses, before it can possibly know, and then acts on the guess. So a branch is a bet, and the question is how good the betting is — and the answer, measured on this machine, is better than most people expect.
$ ./cycbench 2>&1 | sed -n '/5. BRANCHES/,/6. LONG/p'
5. BRANCHES
----------
body min ticks vs floor
branch never taken (control) 0.8261 1.00x
branch period 64 0.7814 0.95x
branch period 16 0.8024 0.97x
branch period 4 0.7428 0.90x
branch period 1 (alternating) 0.7681 0.93x
BRANCHLESS, same data+work 1.7792 2.08x
The direction period makes NO difference: a branch that
repeats with period 1, 4, 16 or 64 costs the same as one that
is never taken. The predictor learns all of them.
Read that table and then read it again, because the first row is the control and it is the highest. A branch that is never taken measures more than a branch that alternates every single iteration. That is not a measurement error to be explained away — it is the finding. On this machine the branch costs nothing at any period, and what varies between the rows is the noise.
Why a core must guess, and what it does when it guesses wrong:
That last point is the one that makes speculation a real design problem rather than a performance trick. A speculatively executed store is a problem the hardware must be able to undo, and on a machine with a store buffer it can: the store sits in the buffer, uncommitted, until the branch resolves. If the branch went the other way, the buffered store is simply never committed.
And the reason branches are predicted rather than merely resolved is a number. Every branch in your program, taken or not, is a place where the front end must stop and wait for a register it does not have yet. If every branch cost a pipeline flush, a loop with a loop-carried dependency — which is every loop — would serialise completely. The measurement in the latency concept makes that concrete: a dependent chain of 8 costs 11× the floor, and a not-taken branch inside it would cost that much again if the core waited.
So the design is: predict, and be right almost always. The interesting question is what “almost always” means, and how a predictor gets to be right.
And that model makes a sharp prediction, which is the experiment the next section runs. If a pattern that repeats within the predictor’s history is free, then the penalty should appear only when the period exceeds the history — and the period at which it appears is a measurement of the history length.
First attempt, and it failed in an instructive way. A branch on a rotating register bit:
$ ./br2 # period 1..64, from a rotating register branch pattern ticks/iter vs branchless branch never taken (control) 0.6065 0.45x branchless, same work (control) 1.3339 1.00x direction period 64 0.6676 0.50x direction period 32 0.6637 0.50x direction period 16 0.6640 0.50x direction period 8 0.6656 0.50x direction period 4 0.6635 0.50x direction period 3 0.7670 0.57x direction period 2 0.6634 0.50x direction period 1 (alternating) 0.6631 0.50x
Completely flat. Period 1, period 3, period 64, a branch that is never taken — all within 3% of each other, and the never-taken control is the slowest row in the table. A rotating 32-bit register makes the direction repeat every 32 iterations, and the predictor learned all of it.
Two things are visible here, and the second is the more useful.
First: the branch is genuinely free. The cost of a perfectly-predicted branch is not zero, but it is below this instrument’s noise floor — smaller than the 15% run-to-run spread measured in the instrument concept. The whole front end keeps moving, and nothing downstream ever learns a guess was made.
Second: the “branchless” control is the slowest row in the table — twice the cost of the branch it is supposed to replace, using the same data and the same conditional work. That is the surprise, and it is dealt with at the end of this concept because the first two explanations for it were both wrong.
So the period is not the interesting variable. The interesting variable is how far back the pattern reaches, and to move that you need a pattern longer than the predictor’s history. A table of pseudorandom bits, walked with a sequential index:
$ ./cycbench 2>&1 | sed -n '/6. LONG-PERIOD/,/7. ALIGN/p'
6. LONG-PERIOD PATTERNS, and the limit of this machine
---------------------------------------------------
table depth ticks/iter vs depth 2
2 1.7790 1.00x
4 2.0365 1.14x
8 1.9985 1.12x
16 2.1403 1.20x
32 1.3985 0.79x
64 1.6090 0.90x
128 1.5915 0.89x
256 2.0648 1.16x
1024 1.5455 0.87x
4096 1.7982 1.01x
16384 1.9909 1.12x
65536 1.6765 0.94x
Also flat. Depth 2 and depth 65536 differ by 0.94× — the 65536 case is faster than the depth-2 case, which is noise, not a result. The table is not monotonic, not periodic, and shows no step anywhere.
So the experiment did not find the predictor’s history length, because there was no step to find. The next concept takes that seriously rather than treating it as a null result, because a null result here has two very different explanations and this machine can only measure one of them.
The “replace an unpredictable branch with a conditional move” advice is one of the most repeated pieces of performance folklore, and it is the standard advice for code with data-dependent branches. So the measurement is worth taking seriously, and the two explanations this course wrote down for it were both wrong.
branch version 1:\n\tadd $1,%%r8\n\tror $1,%%r11\n\t
jc 1f\n\tadd $1,%%r8\n\t1:\n\tdec %%rcx\n\tjnz 1b
branchless version 1:\n\tadd $1,%%r8\n\tror $1,%%r11\n\t
adc $0,%%r8\n\tdec %%rcx\n\tjnz 1b
measured: 0.7428 vs 1.7792 -- 2.40x SLOWER
Retraction 1: “the flags register has no rename, so flag-writing instructions serialise.” Wrong. Four TESTs, which all write the flags, cost 1.45× the floor. Writing the flags repeatedly is nearly free.
Retraction 2: “reading the flags is what costs” — the obvious replacement. Also wrong. Four ROR+ADC pairs measured 4.46× against 4.23× for the RORs alone: a difference of 1.05×. Reading the flags costs nothing extra.
And what survives is not an interesting explanation. The four-ROR row is expensive because those four RORs all target one register and so form an ordinary loop-carried chain. Three candidate explanations, two retracted, and the survivor is a plain dependency that the latency concept already described.
Which leaves the branchless result needing an honest reading, and the artifact says this in its own output rather than leaving a reader to infer it:
That is the correct reading and it is much less dramatic. The branchless version is doing more work and is not saving anything, because the branch it replaced was free. The folklore says conditional moves are free; the measurement says they cost an operation, and the folklore is silent about the fact that the branch was free to begin with.
There is a real version of the advice, and it is narrower. Branchless code helps when the branch is genuinely mispredicted often, because it trades a mispredict for an operation. This machine never produced a mispredict, so the trade could not be observed here — and the honest statement is that the folklore’s precondition was never met, rather than that the advice is wrong in general. The next concept is about exactly that missing measurement.
$ cd courses/exe/assets/samples $ ./cycbench 2>&1 | sed -n '/5. BRANCHES/,/6. LONG/p' $ python3 crosscheck.py 2>&1 | sed -n '/^F /,/^G /p'
Then find a branch this predictor cannot learn, which is the exercise the course could not complete:
1. Get a hardware counter. This is the step
that makes the rest possible, and it is
gated on your machine, not on your skill:
perf stat -e branch-misses,branches ./prog
If that works you have something this course
did not, and you should do the experiment the
course could not: make a branch genuinely
unpredictable, COUNT the misses, and compare
the count with the timing. The two together
settle what timing alone cannot.
2. If you have no PMU, find a mispredict by
brute force instead. The best source of
genuinely unpredictable data that is cheap
to consume is a HASH of the iteration counter
with a large odd constant -- the sign of the
result has a period of about 2^63, which is
longer than any plausible history:
for (long i = 0; i < n; i++) {
if ((i * 0x9E3779B97F4A7C15L) >> 63) ...
}
(Careful: the compiler may turn that into a
branchless CMOV, which is a DIFFERENT
measurement. Check the disassembly with the
ISA course's decoder before you believe what
you wrote.)
3. Now test the folklore directly, on a
machine where you can count misses. Write a
branchy loop and a branchless one, do the
same work, and compare misses AND time:
// branchy
for (i = 0; i < n; i++)
if (p[i] & mask) sum += p[i];
// branchless
for (i = 0; i < n; i++)
sum += (p[i] & mask) ? p[i] : 0;
(Now you can answer the question properly.
Expect the branchless form to win when the
mask makes the branch unpredictable and to
LOSE when it is predictable -- and the
crossover is the interesting number.)
4. Measure a REAL conditional branch's cost, not a
synthetic one, and find where the folklore's
precondition actually holds in code you use:
objdump -d prog | grep -cE '\bj(e|ne|a|ae|b|be|g|ge|l|le|s|ns)\b'
(Every one of those is a branch that could
mispredict. This course's synthetic branch was
free; those are the ones that decide whether
the branchless advice applies to your code.)
5. Finally, and this is the one worth the most:
find the point at which the predictor gives up
on YOUR machine, by bisection rather than by
a fixed ladder. Take the table-walk
experiment and binary-search the depth:
depth where time stops being flat = the
predictor's effective history, in branches
Repeat it with the loop in a different place
in memory, and with a different body size. If
the depth changes, the predictor is not
indexing on history alone -- and the shape of
that dependence is a real measurement of the
predictor's structure that no amount of
reading about it will give you.
Exercise 3 is the one that settles the concept, and it needs a PMU to do properly — which is precisely the point of the next concept. With a counter you can compare the branchless form’s miss count against the branchy form’s time, and the crossover between them is a real, actionable number. Without one you have a timing difference and two possible explanations, and the honest answer is to say so.
Exercise 2 has a trap worth knowing before you start. The compiler will replace a data-dependent if with a conditional move on its own, which means you can write a branch, look at the source, and measure something that has no branch in it at all. The ISA course’s decoder is the check: count the conditional branches in the disassembly, not the ifs in the source. That is the third time in this collection that the source and the bytes have told different stories, and the rule is always the same — the code is the evidence and the source is a hypothesis about it.
The connection to the opcode-map concept is exact and it was set up two courses ago. That concept measured 0F 0B as UD2 and explained that a compiler emits it after a noreturn call so that a fall-through dies at the next instruction. That is speculation’s failure mode stated as an encoding, and this concept supplies the other half: speculation’s failure mode is a mispredicted branch, and the machine’s answer to both is the same — a deliberately undefined instruction that faults. The PIC-cost concept’s nine-instructions-against-seventeen is the same idea one level up, since every branch in a PIE is a branch whose target the linker has not filled in yet.
The connection to the dependency concept is a sharpening rather than a new topic. That concept established that a dependency is a constraint on when an instruction may start. This concept is the case where the constraint is unresolvable in principle: a branch’s target depends on a register, and the register’s value depends on work that has not run, so the front end must either wait or guess. Guessing is strictly better on a machine that guesses right, which is what the measurement shows, and the whole design of a modern out-of-order core follows from that being true.
Two connections outward, both about speculation’s reach. The encoding-limits concept measured that PIC needs a disp32 per access and therefore a relocation per access, and the relocations concept measured the doubling that follows. Those are static costs, and this concept is where the dynamic one would be measured — more relocations means more front-end work means more branches to predict, and the two interact. The experiment that would settle it is a timing comparison of the same computation built PIE and non-PIE, which spans two courses and was not run. And The image-loading course established that the auxv is read at startup and then never again; speculation is the other thing a program does once at startup and then never again, and the branch predictor is a cache in the same sense — it warms up and then it is just there.
One limit, and it is the limit of the whole course so far. No mispredict penalty was observed, and this concept therefore cannot say what one costs. It can say the predictor learns patterns repeating with period 1 through 65536, and that on this machine a predicted branch is free to within the noise floor. It cannot say whether that is because the predictor is good or because the cost is hidden, and the next concept is entirely about that question and about the hardware counter that would answer it. A course that measured five mechanisms and wrote down the sixth it could not measure is more useful than one that quotes a mispredict cost from a datasheet, because the reader who needs the number knows exactly which machine to go and get it on.