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

The thread: A branch is a cost

A processor executing a comparison does not wait to learn the answer; it guesses. A comparison whose outcome is predictable is nearly free and one that is a coin flip is not, and the two are the same comparison to every other counter here.
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 What the machine does

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.

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

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.

 010010³10⁴interval extensions—48.1%68.5%69.8%errors allowed · share removed belowno pruningpruned on D4,000 characters · m = 1669.8% removed at k = 3 What a bound is

The branch that cannot reach an answer

Seventy-two rank operations over the pattern remove 27,906 of the 39,957 interval extensions a bounded-error index walk performs — 70% of the tree, at a budget of three. The share grows with the budget, which is what a pruning has to do to be worth its cost.

 atgaattcatgagtgacaag00000111111112222222errorsthe pattern, left to right · D belowleast errors neededD, the bound4 symbols · m = 2090 ranks · 2 resets The data that is not a number

The errors the rest of the pattern needs

Read the pattern left to right in an index of the reversed text and count the points where the interval empties. That count is a lower bound on the errors any alignment of the prefix must contain, it costs 72 rank operations, and it removes 70% of a search tree.

 atgaattcatgagtgacaag00000111111112222222errorsthe pattern, left to right · D belowleast errors neededD, the bound4 symbols · m = 2090 ranks · 2 resets What is taught wrongly

The pruning that loses an occurrence

Two versions of the same lower-bound pruning, each one character away from correct. Both return only real occurrences, both return fewer of them, and no check that asks whether the answers are right can tell either from the truth.

All threads