A search with no branch to miss

Binary search is the algorithm everyone can write from memory and nearly everyone writes wrongly. This essay is about two of the ways, and they are unrelated except that both are invisible to every check that matters.

The first is that its central comparison is, by design, the most unpredictable branch it is possible to write. The second is that the standard way of computing the midpoint overflows, and did so in published code for two decades.

The most unpredictable branch there is #

A binary search halves the remaining range at every step. That is what makes it logarithmic and it is also exactly what makes it unpredictable: halving the possibilities is the definition of a comparison that yields one full bit of information, and a comparison that yields one full bit is one whose outcome could not have been guessed.

Measured on 2,000 searches for uniformly random targets in a sorted array of 4,096 elements, the ordinary binary search performs 24,002 comparisons and mispredicts 14,021 branches — 58% of the comparison branches, close to the theoretical worst.

It is not exactly 50% per comparison, and the reason is worth a sentence. The first two or three levels of a search on a uniform target distribution are genuinely 50/50; the last few are not, because the search’s remaining range interacts with where in the array the target sits, and there is a small bias the predictor picks up. But the bulk of the misses is the bulk of the comparisons, and the count grows with $\log_2 n$: 9,976 mispredictions at n = 256 and 17,993 at n = 65,536.

Roughly one mispredicted branch per level, per search, at every size. For a search that costs sixteen comparisons at n = 65,536, that is sixteen pipeline flushes for sixteen comparisons — the branch cost dominating the work by an order of magnitude.

Feeding an index instead of a jump #

The alternative is to keep the comparison and remove the jump.

Instead of testing the middle element and choosing a half, compute the half’s width, take the comparison’s result as a zero or one, and add it to the base. The base moves by half the width or by nothing, decided arithmetically. There is no conditional jump on the data at all: on a real processor the comparison becomes a cmov or a masked add, which has a fixed cost and nothing to guess.

The loop then runs a fixed number of times — exactly $\lceil \log_2 n \rceil$ — whatever the target is, so the one branch that remains, the loop bound, is perfectly predictable after the first pass.

Two things in that table are worth stating separately.

The branchless version does more comparisons at every size, by 2,000 across 2,000 searches — exactly one extra per search. The ordinary search can stop early when it hits the target exactly; the branchless one cannot, because stopping early is a branch. It always runs the full $\lceil \log_2 n \rceil$ steps and then checks once at the end.

Its mispredictions are 2,001 at every size. Not approximately flat — identically 2,001, from n = 256 to n = 65,536, a range of 256×. One per search, which is the loop exit, plus one for the cold predictor at the very start. The branch count grows with $\log_2 n$ and the miss count does not move at all.

So: 6% more comparisons, and 89% fewer mispredictions at n = 65,536. Under the four counters this site had a phase ago, the branchless binary search is strictly worse, and it is what every serious search implementation does.

What this does not measure #

This site counts operations and models two hardware behaviours. It does not produce times, and the branchless search’s actual advantage is a claim about times.

What can be said precisely is the trade: two thousand extra comparisons against sixteen thousand fewer pipeline flushes. Whether that is a gain depends on the ratio of a mispredicted branch’s cost to a comparison’s, which is a property of the processor — roughly fifteen to twenty cycles against one, on hardware of the last decade, which makes the trade overwhelming. On a processor with a short pipeline and no speculation, the branchless version is simply slower, and on the machines binary search was first written for that was the case.

The right conclusion is not that branchless is better. It is that the ranking depends on a hardware parameter, and that this is a genuinely different situation from the ones this site usually measures, where the comparison count is a property of the algorithm and the input and nothing else.

There is one more thing the model cannot see and it cuts the other way. The branchless search’s memory access is unpredictable to the prefetcher in the same way the branchy one’s is — both jump around the array — but the branchless one cannot overlap its next load with a speculatively-executed continuation, because there is no speculation to do. In practice implementations answer this with explicit prefetching of both possible next positions, which is more work again. The essay’s honest summary is that this is a technique whose justification lives almost entirely in quantities this site does not have.

Where the extra comparison comes from, exactly #

The 2,000-comparison difference is worth pinning down, because it is not overhead in the usual sense — it is a lost optimisation, and which one is instructive.

The ordinary binary search does three things per step: compare, test for equality, test for direction. When the target is present, it can return the moment the equality test succeeds, which on a uniform random target happens after about $\log_2 n - 1$ steps on average rather than the full $\lceil \log_2 n \rceil$.

The branchless version cannot do that. An early return is a data-dependent jump — the exact thing being removed — so it runs the loop to completion and performs one final comparison at the end to decide whether the element it landed on is the target.

So the extra work is exactly one comparison per search, and the price of never being able to stop early. That is a small price at $n = 65{,}536$, where the search takes sixteen steps and one extra is 6%. It is a much larger price at $n = 4$, where it is 50%, which is one reason the technique appears in libraries only for large arrays and never inside the small-array paths.

It is also why the branchless version’s comparison count is a clean multiple of the search count and the branchy one’s is not. Look at the table: 18,000, 24,000, 28,000, 34,000 — every one of them is $2{,}000 \times (\lceil \log_2 n \rceil + 1)$ exactly. The branchless search’s cost does not depend on the data at all, which is the same property that makes it constant-time in the cryptographic sense, and which is a third reason to want it that has nothing to do with speed.

That last point deserves its own sentence. A search whose duration depends on where the target sits leaks where the target sits. In a context where the array holds secrets — a key table, a password database — the timing of an ordinary binary search is an oracle, and the branchless one is not. Neither this site’s counters nor its cache model measures that, but the mechanism is the same one this essay is about: removing the data-dependent branch removes the data-dependent behaviour, and speed is only the most commonly cited consequence.

The extra comparison is one only at the powers of two #

“Exactly one extra per search” is what the two power-of-two rows of that table say, and the two rows between them say something more interesting. The differences are 1,985, 3,286, 2,709 and 2,000 — per search, 0.99, 1.64, 1.35 and 1.00 — so the overhead is not a constant, it is a sawtooth, and the shape has a closed form.

The branchless side is exact by construction: $\lceil\log_2 n\rceil + 1$ comparisons, every search, no data dependence. The branchy side is the one that varies, and the measured means are 8.01, 10.36, 12.65 and 16.00 against $\log_2 n$ of 8.00, 10.29, 12.57 and 16.00. An ordinary binary search over a uniform target costs $\log_2 n$ comparisons on average — the unrounded logarithm — because the range it halves is $n$ rather than the next power of two above it, and a path that reaches a range of one early simply stops.

Subtracting gives the overhead:

$$\lceil\log_2 n\rceil + 1 - \log_2 n \;=\; 1 + \left(\lceil\log_2 n\rceil - \log_2 n\right)$$

which is 1.71, 1.43, 1.00 and 1.00 at the four sizes against 1.64, 1.35, 0.99 and 1.00 measured. The residual is the small bias mentioned earlier — the last level’s outcome is not quite a coin flip — and it is under a tenth of a comparison.

So the cost of never stopping early is one comparison at a power of two and up to two just below one, and it is worst immediately above a power of two, where the branchless loop has just gained a step that the data does not need. Relative to the search, that is at most $2/\log_2 n$: 12% at $n = 65{,}536$ rather than the 6% the power-of-two row suggests, 18% at a thousand, and 50% at four — which is the number the essay already gives for the small-array case, arriving here as the endpoint of a curve rather than as a separate observation.

Two things follow.

A benchmark of this technique that sweeps only powers of two measures the best case at every point, and powers of two are exactly what a sweep of array sizes usually contains. The sawtooth is invisible to it, and the reported overhead is the bottom of the tooth throughout. That is a sampling artefact of the same kind expected is not average is about, sitting in the choice of sizes rather than in the choice of inputs.

And the libraries’ habit of using the branchless path only above some size is better justified than a flat 6% would make it. The crossover has to be placed against the worst point of the sawtooth rather than its mean, because an array’s length is not something the caller chose to be convenient — which is the same reasoning that puts insertion sort’s cutoff where it is, one field over, and for once the two constants are decided by the same kind of arithmetic.

The other way binary search is written wrongly #

Now the second defect, which is unrelated, older, and much more famous.

The midpoint of lo and hi is written (lo + hi) / 2. In signed 32-bit arithmetic, lo + hi overflows once it passes $2^{31}$, and the result is negative, and the array access is out of bounds.

Jon Bentley’s Programming Pearls carried it. Java’s Arrays.binarySearch carried it until 2006, when Joshua Bloch wrote it up under the title Nearly All Binary Searches and Mergesorts Are Broken. It requires an array of more than about a billion elements, which in 1986 was unreachable and by 2006 was not.

The fix is lo + (hi - lo) / 2, which computes the same value and never forms the large sum. It is one character longer.

That is the whole of why this defect had the lifetime it did. The code was correct on every machine and every input anybody had, and it became incorrect without being edited — the arrays got bigger. A bound that depends on a machine’s word size is a bound that expires, and a check written against the sizes of the day cannot see it coming.

This is unreachable in JavaScript, where every number is a double and integer overflow does not happen at these magnitudes. So the figure above is a stated model rather than a run, in exactly the way this site’s stackLimit is a stated model of a stack exhaustion the build machine cannot reproduce. A figure here may show a modelled failure; it may not show a real one it cannot reproduce, and the difference is printed on the figure.

The check has two sides, and the second one is the interesting one. Below the boundary the two formulas must agree exactly, at every size — otherwise the “safe” version is not computing a midpoint. Above it, the naive one must be wrong at every size. The first version of that assertion tested for a negative result and passed the wrong rows: once the sum passes $2^{32}$ it wraps a second time and lands back in the positive range, still wrong, and a check looking for negatives would have called those correct.

The flatness is the claim, and a flat line is the easiest kind of claim to draw once and never check. Three more sweeps, at different ranges and different query counts.

Fewer searches over a longer range is the other corner of the same rectangle, and it is the one where a per-search constant would be easiest to mistake for something growing.

And more searches again, so that the count being flat in $n$ is separated from the count being proportional to the number of searches, which is what it actually is.

Why both defects survived #

The two have nothing in common technically and everything in common as failures.

Neither is visible in the output. The branchy binary search returns the right answer; it is just slower than it needs to be by a factor nobody can see without a hardware counter. The overflowing midpoint returns the right answer for every array anyone had, for twenty years.

Neither is visible in the complexity class. Both versions of the search are $\Theta(\log n)$ in comparisons. The overflow does not change the class either; it changes the set of inputs on which the algorithm is defined.

Both are visible immediately once the right quantity is counted. The branch counter took one phase to build and shows the first at a glance. The overflow needs no counter at all, only somebody asking what happens at the top of the range — which is the question that took twenty years.

That third point is the one this collection keeps arriving at. The probe formula nobody checks found a closed form that everybody sizes hash tables with and nobody tests. The invariant that was wrong for seven years found a property everybody relies on and nobody proved. The common ingredient is not difficulty. It is that the thing was never asked.

The search inside everything else #

A standalone binary search is not where most binary searching happens. It happens inside other algorithms, and this phase has added several that do it.

Timsort’s run extension is a binary insertion sort, which means one binary search per element short of minrun. At $n = 8{,}192$ with minrun at 32, that is up to 31 searches per run across 256 runs — several thousand binary searches, every one of them carrying the coin flip this essay is about. Galloping is exponential probing followed by a binary search, so every gallop carries it too. Dual-pivot quicksort’s five-element pivot selection is a small sorting network, and each of its comparisons is a branch on data.

None of those can be made branchless by the technique above, and the reason is the one the last figure’s caption gives: they are not choosing an index, they are choosing what to do next.

The exception is illuminating. pdqsort’s real implementation partitions by computing, for each of a block of elements, whether it belongs on the left — storing the offsets of the ones that do into a small buffer, with no branch — and then performing the swaps from the buffer. The comparison still happens, and its result becomes a stored offset rather than a jump. It is the same trick as the branchless search, applied to a merge-like decision, and it costs a buffer, a second pass and about eighty lines. That is the price of flattening a branch that chooses an action rather than a value, and it is why the technique is rare.

Timsort on sorted input mispredicts two branches in the entire sort of 8,192 elements. Two: the cold counter warming up, and the run scan discovering the end of the array. Every one of its 8,191 comparisons goes the same way, and the predictor learns that after the first one.

That is the cleanest possible statement of what this counter measures. The same algorithm, the same instrument, the same number of comparisons to within a factor of twelve — and 55,777 mispredictions on one input and 2 on another.

Which leaves the closing observation, and it is the reason this technique has not spread further than it has. Branchless works when the branch chooses a value; it does not work when the branch chooses what to do next. A binary search’s branch chooses an index and can be flattened. A merge’s branch chooses which of two pointers to advance and which element to write, and flattening it means doing both and discarding one — which is what pdqsort’s block partition actually does, at the cost of a buffer and a great deal of complexity, for exactly this reason.