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

The thread: The unit of cost is not one

Every count on this site charges one for an array access, and every real machine charges for a block. The same 65,536 accesses cost 1,024 transfers in one order and 65,536 in another, with nothing about the algorithm's work changed — which is the widest gap any two counters here have shown.
block transfersIn order, 0 to n−11,0241.0× a scan · 64.0 elements per transferEvery B-th element (B = 64)65,53664.0× a scan · 1.0 elements per transferUniformly at random61,40760.0× a scan · 1.1 elements per transfera scan of this array is 1,024 transfersB = 64, M = 4,096 (M/B = 64)64× between the cheapest order and the dearest When it does not fit

One access, eight kilobytes

Every count on this site charges one for an array access. A machine charges for a block. The same 65,536 accesses cost 1,024 transfers in one order and 65,536 in another, with nothing about the algorithm's work changed — a factor of 64, which is exactly the number of elements in a block, and which no counter here could see until now.

 048162432characters every key sharesoperations072,581145,162Character comparisonsRadix sort, characters readElement comparisonsone unit = one character comparisonelement comparisons constant at 3,955 The data that is not a number

The comparison that is not one comparison

Sorting 512 keys costs 3,955 comparisons whatever the keys are, and between 7,849 and 134,409 character examinations depending only on how much those keys have in common. The first number is the one every bound so far is stated in. The second is the one the machine pays, it grows without limit, and nothing here has ever counted it.

 10³10⁴10010³n (elements)block transfersM = 256 · fan-in 7M = 1024 · fan-in 31B = 32, M as labelled4 passes against 3 When it does not fit

Sorting what will not fit

Merge sort's Θ(n log n) is a statement about comparisons and says nothing about a file larger than memory. Counted in transfers the answer is (n/B)·log_{M/B}(n/B), and the base of that logarithm is the number of blocks that fit in memory — so doubling the memory does not halve the work, it moves a staircase. The measured cost jumps by 32,768 transfers at one step and by nothing for the next four.

 1010010B (elements per block)block transfers per searchtuned for B = 64Sorted arrayB-tree tuned for B = 64van Emde Boas — told nothingM = 16,384, B as drawnone layout, 7 block sizes, no parameter When it does not fit

The layout that is told nothing

A B-tree is built around a block size somebody looked up. The van Emde Boas layout is given neither the block size nor the memory size, and across seven block sizes spanning a factor of 64 it tracks the best structure that was told them. An algorithm with no parameters making a claim at every level of the hierarchy at once is a strange thing to be able to measure, and this is what it costs.

 one read per text character24816326495alphabet size, m = 8characters read ÷ text length0.01.12.2Naive scanKnuth–Morris–PrattBoyer–Moore–Horspoolone unit = one character comparison · n = 20,000, m = 8Horspool's best here: 0.132 per character The data that is not a number

The text that answers without reading it

Boyer–Moore–Horspool finds every occurrence of an eight-character pattern in a twenty-thousand-character text while examining 2,985 characters. Not 2,985 comparisons of eight characters each — 2,985 characters, 0.149 per character of text. It is a correct algorithm returning a complete answer about a text it has mostly not looked at, and the reason it can is a property of the alphabet rather than of the algorithm.

 acgtacgtseen ->0313303113033130a gap of k characters costs 2krows: expected · columns: seen · unit: bitslinear gaps When the algorithm is a table

A cost that is not one

The same eighty-one cells, filled by the same recurrence, return 6, 10, 10 and 15 — in edits, in cost, in bits and in bits again. Only the first is a count of anything, two of them are equal by arithmetic coincidence, and the alignment each one chooses is different.

 elements of block written per key insertedB-tree, in place49.3Log-structured, T = 23.0 · 16× less than the treeLog-structured, T = 42.0 · 25× less than the treeLog-structured, T = 81.0 · 49× less than the treeLog-structured, T = 161.0 · 49× less than the treeB = 64, M = 4,096 (M/B = 64)25× between the two structures at T = 4 When it does not fit

The writes nobody counted

Sixteen thousand keys inserted into a B-tree write 49.3 elements' worth of blocks for every key stored. The same keys into a log-structured store write 2.0. Every operation counter reports the two as the same work — the same insertions, the same comparisons, the same number of updates — and the factor of 24 decides which structure a storage engine is built from.

 Sorted array (binary search)2 blocksLevel order4 blocksvan Emde Boas2 blocksmemory address, left to right · alternating outlines are blocksB = 8, M = 64 (M/B = 8)4 blocks against 2, for the same 6 comparisons What the machine does

Two searches, one comparison count

Three arrangements of the same binary search tree over the same million keys, walking the same path, making the same twenty comparisons. One costs 15 block transfers, one costs 13, and one costs 3. Nothing about the algorithm differs between them — only where the nodes were put — and no counter this site had before this phase could tell them apart.

 1100ε — the exponent the fanout is B toelements written per key33445679ε = 1 — the B-tree ·fanout 256 · 3transfers a queryε = 0.5 · fanout 16 · 5a querythe number above eachpoint is what a querycostsB = 256, M = 16,384 (M/B = 64)131,072 random keys When it does not fit

One dial between two structures

A B-tree writes 226 elements of block for every key stored and a log-structured store writes two. They are presented as rival designs. They are one design at two settings of an exponent that nothing in either description mentions, and every setting between them is available.

 1010010³10⁴B — elements to the blockblock transfersthey cross near B = 4one element at a timesorted by destination, 2passesM = 4,096, B as drawnthe lower bound is the smaller of the two, and it is proved rather than measured When it does not fit

Permuting is the harder problem here

Rearranging 65,536 elements into a stated order costs 63,601 transfers one at a time and 4,096 by sorting them into place. In the model every other field on this site uses, the first is the cheap method and beats the second by a factor of eight. The two models disagree about which problem is easy, and they disagree by about the same factor in opposite directions.

 4 bytes32 bytes128 bytes512 bytesrecord:QuicksortMerge sortShellsortHeapsortInsertion sortSelection sortBubble sortQuicksortShellsortMerge sortHeapsortSelection sortInsertion sortBubble sortQuicksortShellsortMerge sortSelection sortHeapsortInsertion sortBubble sortSelection sortQuicksortShellsortMerge sortHeapsortInsertion sortBubble sort1234567n = 512, random input, key 8 bytesa read or a write moves the record; a comparison touches the key Counting

The exchange rate nobody wrote down

Three earlier essays have said in passing that the ranking would change if the elements were large records. None of them computed it. Computed, selection sort goes from second-worst of seven at four bytes a record to best of seven at five hundred and twelve — and the crossover against each rival is a division that takes one line.

 1,00010,00010³bits of select supportpositions inspected, worst casebinary search, no extra bits: 510L=8L=256L=8L=256one position per L onesdense and sparse6,554 ones in 65,536 positions · sub-blocks of 8worst cases, every k What the machine does

Select is not rank backwards

Rank counts the ones before a position and select finds the position of the k-th one, and only the first has an obvious structure. The constant-time answer costs 1.56 bits per one, is bounded in a unit the machine does not charge for, and on a vector with one bit in fifty it inspects more positions than the binary search it replaced.

 11010010³10⁴1010010³rows matching the queryblock transfersn/B rows — where the arithmetic says they meetindex, rows scatteredindex, file in key orderread the whole fileB = 64, M = 4,096 (M/B = 64)plus 3 transfers to descend the index When it does not fit

The index that is not worth reading

An index turns a query over 65,536 rows from 1,024 transfers into four. At a thousand matching rows it costs 654 and still wins; at sixteen thousand it costs 1,027 and has lost. Where it turns is decided by the block size — a number the query does not contain, the schema does not mention, and nobody writing either has seen.

 1×10×10³10⁴the key side, as a multiple of memoryblock transfersblock nested looppartitioned hash joinsort–merge joinB = 64, M = 512 (M/B = 8)the other relation: 16,384 rows When it does not fit

Two ways to join, and the ratio that decides

The same join costs 260 transfers one way and 1,040 the other; at eight times the memory the same two costs are 2,880 and 1,280, the other way round. Neither number is a property of how large the tables are. The quantity that decides is how the smaller of them compares to memory, and a rule of thumb phrased in rows is a rule about somebody's machine.

 fades a lazy table computed382,976fades an eager table would compute3,830,256fade multiplications (log scale)11,968 evictions, each comparing all 32 counters at one instant32 counters · half-life 4 s · bursty10× fewer What the libraries do

The fading nobody computes

Twelve thousand arrivals into thirty-two decayed counters cost 382,976 fade multiplications. An implementation that aged every counter on every tick would have cost 3,830,256, and the ratio is exactly the mean gap between arrivals — not a coincidence, and the reason the family is deployable.

 patterns of 225%60 selectspatterns of 441%94 selectspatterns of 863%118 selectspatterns of 1682%117 selectsEnglish-like · 8 copies of 512share of steps needing no lookup40 patterns a row The index that replaces the text

The occurrence carried through the search

Backward search returns how many and not where, and every index on this site pays for the second question separately. Carrying one occurrence along with the interval costs a lookup on 75% of the steps for a two-character pattern and on 18% of them for a sixteen-character one, and it is what makes a run-boundary sampling usable at all.

 01234567801234567891724303539424410182531364043111926323741122027333813212834142229152316one unit = one subproblem given a valueeach number is a storage offset, of 45 slots When the algorithm is a table

A triangle stored in a square

An interval table has a cell for every range of keys and nothing below its diagonal, and it can be stored as a square array, as packed rows, or as packed diagonals — the last matching the order it is filled in. On sixty-four keys, with every read replayed through a small cache, the square misses 39.7% of its reads, packed rows 38.8%, and packed diagonals 78.4%. Storing a table in the order it is written is storing it in the order it is not read.

 read from the start40,000 readsa ring of 4,096 keys and 4,096 stamps184,320 bitsread from the end4,096 reads792 counters, no stamps50,688 bitsitems readsame answer: 1×700, 2×341, 3×224…W = 4,096 · φ = 0.02 · stationary Zipf9.8× fewer reads, same answer The floors

The pass that runs the other way

Exact heavy hitters over the last 4,096 of 40,000 arrivals cost 40,000 reads and a ring of 4,096 keys and stamps read forwards, and 4,096 reads with no stamps read backwards. Every lower bound in the sliding-window model is a bound about an access pattern, and the word doing the work never appears in the statement.

 1,00010,000110occurrences12481632characters in the collection · copies aboveall occurrencessecondaryprimarypattern "ss is un" · z = 1561 primary · 31 secondary The data that is not a number

The occurrences that cross a boundary

One pattern, thirty-two copies of a text, thirty-two occurrences. The search finds one of them and produces the other thirty-one by arithmetic, and the count it finds is the same one at two copies, at eight and at thirty-two — the searching does not grow when the answer does.

 0000200121200the parenthesis sequencethe minimum excess of each block of 213 blocks · lookup table 72 bits, sharedblock 2 · 24 parentheses13 blocks What the machine does

The table that fits inside a block

A block of six parentheses has sixty-four possible shapes and twenty-eight questions can be asked about each, so all 1,792 answers fit in a table of 9,408 bits — computed once, shared by every structure of that block length, and never counted in any of their sizes.

 10⁵10⁶10⁷10³10⁴inversions in the permutationblock transfers to carry it outsort by destination, 1,536w 8w 32w 128w 512w 2048w 819216 swaps64 swaps256 swaps1024 swapsshuffled inside windowsa few pairs swapped farn = 16,384, B = 64, M = 512 (M/B = 8)inversions do not order the cost When it does not fit

The permutation that moves almost nothing

Two ways to scramble sixteen thousand elements. Shuffling them inside windows of five hundred and twelve puts two million pairs out of order and costs 3,095 block transfers to carry out. Swapping a thousand pairs across the whole array puts seven million out of order and costs 1,189. Inversions are the textbook measure of disorder, and on a disk they rank these two backwards.

 cache misses per split point consideredsquare array, by length1.1063,128,465 missestwo copies, by rows0.212598,455 missessquare array, split scans0.095268,386 missesfully associative · 32 lines × 8 elements · LRU256 keys, 32,896 cells When the algorithm is a table

The split scan cut into blocks

Every way of filling an interval table one cell at a time stops at about one cache miss per split point considered once the table outgrows the cache — 1.01 at 128 keys, whether the cells go by length, by rows, or in a recursive tiling. Cut each cell's scan into blocks instead, and apply a block of split points to a block of cells whose inputs are all in hand, recursively at every scale, and the same 357,760 split points cost 0.094 misses each. The fill is told nothing about the cache, blocks of one and of four do equally well, and it needs no extra memory, where storing the table twice gets to 0.151 by doubling it.

 k = 0k = 1k = 2k = 3k = 4k = 5k = 6q = 223211917151311q = 3221916131074q = 4211713951-3q = 520151050-5-10q = 6191371-5-11-17q = 81791-7-15-23-31a shaded cell is a threshold of zero or less: every window proposedt = m + 1 − q(k+1) · m = 2411 collapsed cells The data that is not a number

The q-grams an error cannot destroy

A pattern of twenty-four characters holds twenty-one four-grams. Two errors can destroy at most eight of them, so any occurrence with two errors still shares thirteen — and a filter that keeps only the windows sharing thirteen proposes 104 of 3,977 and computes 16,744 table cells instead of 96,000.

 10010³10⁴errors allowed, kacts0123index walkthe whole table3,000 characters · m = 20 · 4 symbolsno crossing in range The index that replaces the text

The search that spends a budget

A backward search narrows one interval per pattern character. Give it a budget of three errors and it narrows 39,943 of them instead, finds every occurrence the whole table finds, and reads not one character of the text — 177,046 index ranks against 60,000 table cells and zero characters examined.

 ε = 0.0515 → 29 (1.93×)ε = 0.0238 → 73 (1.92×)ε = 0.0177 → 136 (1.77×)ε = 0.005152 → 270 (1.78×)ε = 0.002397 → 674 (1.70×)reportedoccupied at the peak20,000 arrivals · lognormalpeak = resident + period, to 14% The other axis

The tuples a summary does not report

A Greenwald–Khanna summary at ε = 0.01 answers `tuples` with seventy-seven. Watched through the run it holds a hundred and thirty-six. The gap is the compression period, it is 1.70 to 1.93 times across every tolerance measured, and it is the number a deployment has to allocate.

 1,00010,00010phrases followed12481632characters in the collection · copies aboveworst depthmean depthEnglish-like · z = 156median 18 · 90th 31 The other axis

The character that costs a chain

The index over thirty-two copies is 8,892 bits and does not grow. Producing one character of the text it indexes costs 17.89 phrase-follows on average and 38 in the worst case, against 2.38 and 7 at one copy — the size stopped growing and the price of reading it did not.

 1010010³documents in the answeroperations inside the structureevery occurrencerange minimumone descent17 to 324 rows5.14 to 1.94 per document The floors

Work that falls as the answer grows

Output-sensitive usually means the cost rises with the answer instead of with the input. A descent over a document array costs five operations per document at an answer of seven and two at an answer of thirty-two, because the paths to many leaves share their tops.

 0100200300102030distinct symbols in the intervalbit-vector ranksthe loop: 320the descentsigma = 32 throughout32x down to 5.16x The floors

Proportional to the answer, not the alphabet

At a fixed alphabet of thirty-two, a loop costs three hundred and twenty ranks whether one symbol is present or all of them. The descent costs ten and sixty-two. The experiment has to move the answer without moving the alphabet, and the obvious sweep moves both.

 1101001,00010,00010⁵10⁶k, the elements the caller readscomparisonssort all, read kbuild a heap, pop kselect k, sort thoseincremental quicksortkeep the best k while scanningknockout tournamentdashed: the floorlabels at k = 1,00065,536 random distinct keysevery answer checked Counting

The count of the part that was read

Handing back the smallest ten of 65,536 keys in order costs 965,656 comparisons by sorting them and 65,670 by a knockout tournament, against a floor of 65,526. Read to the last element, the same tournament makes exactly merge sort's 965,656 — it is merge sort, charged one element at a time. A sort's count has no term for how much of its answer anyone reads, and the two floors that do have one cannot simply be added.

 10010³10⁴10⁵10⁶⌊1/2ε⌋ = 50151025501002005001,000tuples, and tuples examinedcompression period, in updatestuples examinedpeak tuplesresident tuplesworst rank errorε = 0.01 · 20,000 arrivalspeak 10× · work 72× · answer 1.21× One pass, and no room

The period that is not a promise

Greenwald–Khanna's ε appears twice — once as the rank tolerance the structure promises, and once as ⌊1/2ε⌋, the number of updates between compressions. Unhook the second from the first and sweep it across a thousand-fold range. The tuples held move by 10%, the worst rank error by 21%, the peak by ten times and the housekeeping by seventy.

All threads