Comparisons against modelled branch mispredictions, n = 2,048

Comparisons against modelled branch mispredictions, n = 2,048

One point per algorithm, both axes logarithmic, 2-bit counters, no history. If the comparison count decided the branch behaviour the points would lie on a line. Merge sort mispredicts 52.1% of its branches and Insertion 0.2% — a comparison whose outcome the machine can guess is nearly free and one that is a coin flip is not, and nothing else on this site can tell them apart. Insertion and Merge sort and Quicksort, first and Quicksort, random and Shellsort and Merge + cutoff and Timsort and pdqsort move three or more places between the two rankings. A mispredict count is a modelled quantity, not a time.

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

4 essays call branch-ranking. 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.