2,000 binary searches, with and without a branch

2,000 binary searches, with and without a branch

Solid lines are comparisons, dashed lines modelled mispredictions, 2-bit counters, no history. At n = 65,536 the branchless search does 34,000 comparisons against 32,000 — more work — and mispredicts 2,001 times against 17,993. Its mispredictions are flat in n to a factor of 1.00 across the sweep, because the comparison feeds an index rather than a jump and the only branch left runs a fixed number of times. Under the counters this site had before this phase, the branchless version is simply worse.

Drawn at 700 × 430, wide on the page. Everything above is what search-branches returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

1 essay calls search-branches. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.