The branch the machine guesses

This site counts four things. Comparisons, because that is what a textbook analysis counts. Cache misses, because the count is not the time and memory is why. Auxiliary space, because an in-place sort and an out-of-place one with identical comparison counts are different algorithms. Random bits, because two reservoir samplers with identical output can spend a hundred and fifty times different amounts of entropy.

Each of those was added because there was something real that none of the existing counters could see. Here is the fifth, and the thing it can see is this:

Insertion sort at n = 8,192 on random input performs 16,881,018 comparisons and mispredicts 8,199 branches. Merge sort performs 96,140 comparisons and mispredicts 49,494.

One hundred and seventy-six times the comparisons, one sixth the mispredictions. There is no counter on this site before this phase that can distinguish those two quantities, and the difference between them is a large part of why a processor built in the last thirty years behaves the way it does.

What a processor does with a comparison #

A comparison in isolation is arithmetic and it is cheap. What is expensive is what usually follows it: a conditional jump.

A modern processor is a pipeline, fifteen or twenty stages deep, with several instructions in flight at once. When it reaches a conditional jump it does not know which way to go until the comparison it depends on has resolved, which may be several cycles away. Waiting would empty the pipeline.

So it does not wait. It guesses, fetches down the guessed path, and executes speculatively. If the guess was right, nothing was lost. If it was wrong, everything fetched since the guess is discarded and the pipeline refills — fifteen to twenty cycles thrown away, which is roughly the cost of ten arithmetic operations or a small fraction of a cache miss.

The consequence is that a comparison whose outcome is predictable is nearly free, and a comparison whose outcome is a coin flip is not. They are the same comparison to Counted.cmp, and they are the same comparison in every textbook analysis of every algorithm.

The model #

lib/branch.js is a table of two-bit saturating counters, direct-mapped by branch site. Each counter runs from 0 to 3; it predicts taken at 2 or 3 and not taken at 0 or 1; a taken branch moves it up and a not-taken branch moves it down, both saturating. The table starts at 1 — weakly not-taken — which is the conventional cold state and is why a branch’s first execution is charged a miss.

It runs online rather than over a recorded trace, unlike the cache model. A cache model must see the whole access sequence before it can say anything about reuse; a branch predictor’s state is updated by each outcome as it resolves, so an online model is the accurate one and it costs no memory at all.

A comparison is not a branch, and the algorithm has to say which it performed. if (a[i] < a[j]) swap(i, j) is a branch on a comparison; a[i] = min(x, y) is the same comparison with no branch at all. Nothing about the comparison distinguishes them; only the code around it does. So cmp does not record anything and the algorithms declare their control flow explicitly.

What the model is honest about #

The model is deliberately simple and a real processor is not. TAGE predictors, perceptron predictors, loop predictors, tens of kilobytes of tables — a real branch unit would predict some of the sequences below considerably better than this does.

The direction of that error matters and every essay using this counter states it. The model is pessimistic about clever patterns and exact about coin flips. A branch whose outcome is genuinely 50/50 and independent of its own history cannot be predicted by anything, so the ~50% miss rate reported for it is not a modelling artefact — it is the floor, and no predictor passes it.

Every argument built on this counter is built on that side of it. When an essay here says a merge’s inner test is unpredictable, it is relying on the floor rather than on the model’s limitations.

Three rows of that table are worth stopping on.

The loop of eight, at 12.5% with two bits and 25.0% with one. This is the classic argument for the second bit and the measurement reproduces it exactly. A loop’s closing branch is taken every iteration but the last. A one-bit predictor mispredicts twice per pass — once on the exit, and once on the first iteration of the next pass, because the exit flipped it. A two-bit counter absorbs the exit without changing its prediction and mispredicts once. Exactly half, and 1.99× measured.

The alternating branch, at 100%. It is taken exactly half the time, which the memoryless floor reads as 50% unpredictable. It is in fact perfectly predictable — by anything with one bit of memory — and a bimodal counter is not merely bad at it but worse than guessing: the counter is dragged up and down and always predicts the previous outcome, which is always wrong. Give the predictor two bits of global history and it drops to 0.1%.

That row is the reason the floor in the table is labelled memoryless. Unpredictability is a relation between a sequence and a predictor, not a property of the sequence, and the only sequences for which it is a property are the ones with no structure at all.

The check that made it worth adding #

Before any figure quoted this counter it had to be shown to be measuring something the first counter does not.

The cache model needed the same test and for the same reason: a model that correlates perfectly with the comparison count is a second name for the comparison count, and drawing it beside the first would be drawing the first twice. assertTheTwoCountsAreIndependent has guarded that since the machine field was built.

The branch model’s version is assertTheFifthCountIsNotTheFirst, and it is deliberately blunt. Two traces of exactly 4,096 branches: one always taken, one a fair coin. The always-taken trace mispredicts once — the cold counter warming up. The coin trace mispredicts 2,067. If those two numbers were ever close, the counter would be reporting branch count rather than branch behaviour, and nothing on this site should quote it.

It has a two-sided partner, because a model that always reported 50% would satisfy the coin half. assertTheModelCanBeRight requires a branch taken all but once in five thousand to miss under 1% — so the pair cannot both be satisfied by a constant, and neither can be satisfied by a model that has stopped updating.

Two more assertions pin the model’s shape rather than its usefulness. assertTwoBitsBeatOne requires the saturating counter to roughly halve a loop’s mispredictions against a one-bit predictor, which is the property the second bit exists for. assertACoinFlipSitsAtItsFloor requires a fair coin to land within six points of min(p, 1−p) — in both directions, so the model may not accidentally predict a coin and may not be worse than chance on one either.

The ranking, inverted #

Reading down the miss-rate column explains each entry, and the explanations are all the same shape.

Insertion sort’s inner loop, 0.05%. The test is keep shifting while this element is greater than the one being inserted. On random data an element travels about half the sorted prefix — many iterations, all of them continuing — and then stops once. The branch is taken almost always and the predictor learns it immediately. Sixteen million comparisons, eight thousand surprises.

Selection sort’s, 0.6%. The test is is this a new minimum. After the first few elements of a scan, a new minimum is rare, and rarer the further the scan goes. The predictor settles on “no” and is right nearly every time.

Merge sort’s, 51.5%. The test is which side’s head is smaller. On two runs of random data with the same distribution, that is a fair coin at every step, and it is the definitional worst case. Merge sort’s comparison count is close to the information-theoretic floor and every single one of its comparisons is maximally uninformative to a predictor — which is not a coincidence, because a comparison that carries a full bit of information is exactly a comparison whose outcome could not have been guessed.

That last observation is the one worth carrying out of this essay. The floor under every comparison sort shows that sorting needs $\log_2 n!$ comparisons because each comparison yields at most one bit. An algorithm that achieves the floor is an algorithm whose every comparison yields a full bit, and a comparison yielding a full bit is a comparison the machine cannot predict. Efficiency in comparisons and predictability are not merely different; they are in tension, and the tension is exact.

Bubble sort’s, 28.3%, is the interesting middle. Its inner test is are these two adjacent elements out of order, which on random data is a coin flip early and becomes increasingly one-sided as the array approaches order. The rate is the average over a run that starts unpredictable and ends predictable.

Where the branches are, inside one algorithm #

The counter reports per branch site as well as in total, which locates the cost rather than summing it, and Timsort is the algorithm with enough distinct sites for that to be interesting.

Timsort at n = 8,192 on random input makes 134,256 branches against 95,772 comparisons — the only algorithm here where the two numbers differ substantially, because its run scan, its binary insertion, its merge and its merge policy are four different tests in four different loops.

The merge’s which side wins test is the coin flip, and it dominates: it is most of the branches and most of the misses. The run scan’s is this still ascending test on random data is a coin flip too, but there are only $n$ of them. The binary-insertion search’s test is a coin flip by construction, as every binary search’s is. And the merge policy’s test runs 255 times in the whole sort and is essentially always predictable, because the answer is almost always “yes, merge”.

Four sites, three of them coin flips and one of them free, and the free one is the one that decides the algorithm’s structure. That is a general pattern rather than a fact about Timsort: the branches that carry an algorithm’s policy are rare and predictable, and the branches that carry its work are frequent and not.

Which is exactly why the technique in the next essay works at all. If the expensive branches were the ones making decisions, there would be nothing to do about them. They are the ones comparing data, and a comparison’s result can be turned into an arithmetic value instead of a jump.

There is a ceiling on mispredictions, and it is the sorting floor halved #

The tension named above — a comparison that yields a full bit is a comparison that cannot be guessed — is exact enough to give a bound, and the bound turns out to explain both ends of the table at once.

For a deterministic comparison sort on a uniformly random input, the sequence of comparison outcomes determines the permutation. So the total entropy of that sequence is exactly $\log_2 n!$ — the same quantity the sorting floor is about — however many comparisons the algorithm makes and however it makes them.

Now take one comparison whose outcome is taken with probability $p$. The best any memoryless predictor can do on it is to always guess the likelier side, missing with probability $\min(p, 1-p)$, and that quantity is at most half the outcome’s entropy $H(p)$, with equality exactly at $p = \tfrac12$. Summing over every comparison in the run:

$$\text{mispredictions} \;\le\; \frac{\log_2 n!}{2}$$

A ceiling that does not mention the algorithm. Every comparison sort on random input, whatever it does and however many comparisons it makes, mispredicts at most that many times — because the information it extracts is fixed and each miss costs at most two bits’ worth of it.

At $n = 8{,}192$ that ceiling is about 47,000. Merge sort measures 49,494, which is essentially at it — the small excess is the two-bit counter being slightly worse than an optimal predictor on a fair coin, which the pattern table above measures at 50.8% against a floor of 49.4%. Insertion sort measures 8,199, which is a sixth of the ceiling.

So the table’s two extremes are one statement: merge sort is at the misprediction ceiling because it is at the comparison floor, and insertion sort is far below it because it is far above the floor. An algorithm that spreads $\log_2 n!$ bits over sixteen million comparisons is extracting a two-hundredth of a bit each, and a comparison carrying a two-hundredth of a bit is one a predictor gets right.

That also settles what the fifth counter is measuring. It is not an independent axis in the way cache misses are: it is the reciprocal of comparison efficiency, bounded above by a quantity every algorithm shares, and the ranking it produces is close to the inverse of the ranking by distance from the floor.

Which leaves two exits and only one of them is new #

The ceiling says an algorithm cannot reduce its mispredictions by being cleverer about which comparisons to make, because the information is fixed. There are exactly two ways under it.

Extract less per comparison. Make more comparisons, each carrying less information, and the misses fall. That is what insertion sort does, and it is why a hybrid’s cutoff moves work onto the predictable algorithm — a fact that the memory argument for the cutoff already suggested and that this counter quantifies.

Stop branching. A comparison whose result becomes an arithmetic value rather than a jump costs nothing to the predictor, because there is nothing to predict. The information is still extracted; it simply does not pass through the branch unit.

The second is not a way of getting under the ceiling — it is a way of leaving the axis the ceiling is about, and it is why the techniques in the next essay do strictly more work by every other counter on this site and are used anyway.

The ranking is a property of the input #

One scatter is one input, and the whole claim is that the two counters disagree — so the cheapest check available is to change the input and watch which algorithm the disagreement lands on.

Reversing the input rather than nearly sorting it moves the offender again, and moves it to an algorithm that was near the bottom of the previous plate.

And the size is the third dial. It is the one that ought to leave a rate alone, and it does.

What this changes #

Three things follow, and the third is what the rest of the field is about.

Comparison counts overstate the gap between quadratic and linearithmic sorts at small sizes. Not by enough to change the conclusion — insertion sort’s 16.9 million comparisons at n = 8,192 are not rescued by predictability — but at n = 64, where insertion sort does about 1,000 comparisons to merge sort’s 300, insertion sort’s are nearly free and merge sort’s are not. That is a large part of why every library’s cutoff is around sixteen rather than around four, and where insertion sort actually wins argued the memory half of the same point without this half.

Three techniques in real libraries stop looking like mistakes. Branchless binary search does more comparisons and more arithmetic than the ordinary one. Sorting networks do more comparisons than insertion sort at every size. pdqsort’s real partition computes offsets into a buffer instead of branching. All three are worse by every counter this site had, and all three are in serious use. A search with no branch to miss measures the first of them.

A counter with no cost model is still a counter. This one, like the cache model, produces a modelled quantity and not a time. What makes it worth having is not that it converts to nanoseconds — it does not — but that it separates two things that were previously one thing, and the separation is large: a factor of 176 in one direction and 6 in the other, between two algorithms this site has been drawing side by side since the foundation.

Heapsort is the closing note, because it is the one algorithm here whose branch behaviour does not change with the input at all: 27.1% on random, 25.6% on sorted, 28.6% on reversed, 26.1% on nearly sorted. Its comparisons are between siblings in a heap, and the heap’s shape is a function of the algorithm’s own history rather than of the data’s order. An algorithm with no adaptive behaviour on the first counter turns out to have none on the fifth either, and that is not a coincidence: both are consequences of an algorithm that never looks at what it has been given.