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

Branchless — where it appears

Code computing a result arithmetically where a conditional would have stood, doing more work in exchange for giving the processor nothing to guess. It performs the same or more work by every count this collection makes and can still finish sooner, which is what makes the branch a resource of its own.

Named by 5 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 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 —sitting—kitten111111101111110-1111110-1-111110-1-1-11110-1-1-10110-1-1-10-11one unit = one subproblem given a value-1, 0, 1 — 3 values, 2 bits each

A column computed in machine words

Adjacent cells of a distance table differ by at most one, so a whole column is two bits per cell — and thirty-two of them fit in one register. Fifteen word operations per character replace three cell evaluations per cell, and below a pattern of fifteen characters the trade is a loss.

machine · Machine 0102030comparisons on one orderingfloor 16Insertion sort7 to 28 · mean 19.28Merge sort12 to 17 · mean 15.73Heapsort21 to 29 · mean 25.81First-element quicksort13 to 28 · mean 16.92Median-of-three quicksort25 to 29 · mean 26.30Batcher's network19 on all 40,32040,320 orders of 8, enumeratedfloor ⌈log₂ 8!⌉ = 16

The sort whose count has no distribution

Batcher's network makes nineteen comparisons on every one of the 40,320 orderings of eight elements — sorted, reversed, adversarial or random — because it decides which pairs to compare before it sees any of them. That is two above merge sort's worst case and four below heapsort's best. At 65,536 elements the same refusal to adapt costs 4.07 times merge sort's worst case, and it buys three things no adaptive sort has, one of which is a proof of correctness that takes 65,536 inputs instead of twenty trillion.

counting · Count a second hash, unordered0.054 entries read on an absent key14.435.79 storedthe bits below the bucket, unordered0.059 entries read on an absent key14.435.79 storedthe bits below the bucket, sorted0.057 entries read on an absent key8.975.21 storedthe bucket's own bits, sorted5.743 entries read on an absent key11.275.80 storedtag comparisons an absent key's lookup makes8,192 slots · buckets of 8 · 8-bit tags38% fewer

A tag that answers more than yes

A byte of hash in front of each entry has one bit of output per slot: this tag matches or it does not. Cut it from an ordered field instead and a bucket's tags can be kept sorted, so a lookup stops at the first tag above its own — 8.97 comparisons for an absent key instead of 14.43, for 3.55 tag-byte shifts an insertion. The obvious ordered field is the trap. Take the tag from the bucket index's own bits and every key in a bucket shares them: 5.74 entry reads on an absent key instead of 0.054, a hundred and seven times more.

machine · Machine

Named alongside it

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

CacheComparison countCost modelLocalityMeasured countMispredictionPipelineTimsortBinary searchBit-parallelBranch predictionCarry propagation

All concepts