Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Misprediction — where it appears

A branch the processor guessed wrong, costing more than the work it avoided, which is why branchless code exists and looks wasteful by every other count. It costs more than the work it avoided, which is why branchless code exists and looks wasteful by every other count this collection makes.

Named by 3 essays across 2 fields — each of them below, with the objects they name alongside it.

10⁵10⁶10⁴10⁵comparisonsmispredictions (modelled)Insertion 0%Selection 1%Bubble 29%Merge sort 52%Heapsort 27%Quicksort, first 24%Quicksort, median-3 39%Quicksort, random 27%Shellsort 51%Merge + cutoff 40%Timsort 41%Introsort 32%pdqsort 43%Dual-pivot 37%2-bit counters, no historysquares are the sorts that ship

The branch the machine guesses

Insertion sort does 176 times as many comparisons as Timsort at n = 8,192 and mispredicts a sixth as many branches. Merge sort's inner test is a coin flip and misses 51.5% of the time; selection sort's misses 0.6%. A processor does not wait to learn the answer to a comparison — it guesses, and throws away the work when it guessed wrong — and this is the fifth quantity this site counts.

machine · Machine 1010010⁵minruncomparisonsshipped: 32randomnearly sortedTimsort, n = 8,192comparisons; rings mark the measured minimum

The threshold somebody chose

A minrun of 32. An insertion cutoff of 16. A gallop threshold of 7. A depth limit of twice the logarithm. Four numbers, in four real source files, none of which appears in any complexity analysis — and each of which decides more about what these algorithms do than the analysis does. Swept, they turn out not to be optima, and finding out what they are instead is the point.

practice · Count 10³10⁴10⁴array length ntotal over 2,000 searchesbranchy, comparisonsbranchless, comparisonsbranchy, mispredictsbranchless, mispredicts2-bit counters, no historysolid: comparisons · dashed: mispredicts

A search with no branch to miss

A binary search does about log₂ n comparisons and every one of them is a coin flip, so it mispredicts once per level. Writing it so the comparison feeds an index instead of a jump costs two thousand extra comparisons over two thousand searches and takes the mispredictions from 17,993 to 2,001 — flat in n, at every size. Under the counters this site had a phase ago, that is a strictly worse algorithm.

machine · Machine

Named alongside it

The objects these essays reach for when they reach for this one.

TimsortBranchlessComparison countPipelineBinary searchBranch predictionCacheConditional moveCutoffDepth limitGallopingHeap

All concepts