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

Pipeline — where it appears

The processor's overlapping of instruction stages, which makes a mispredicted branch cost the work already begun on the wrong path. It makes a mispredicted branch cost the work already begun on the wrong path, which is a cost no count of executed instructions can see.

Named by 2 essays across one field — 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 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.

BranchlessMispredictionTimsortBinary searchBranch predictionCacheComparison countConditional moveHeapInteger overflowMidpointPivot

All concepts