Machine — the series
-
The count is not the time
An operation count is exact, machine-independent, and not a running time. The gap between them is mostly memory, and it is large enough to reorder the rankings. A second count is kept alongside it — modelled cache misses from the same runs — and the two are required to disagree, because if they agreed the second one would carry no information.
-
The cliff where the data stops fitting
Below the cache's capacity, almost every access hits. A factor of eight above it, almost every access misses. The transition is not gradual and it is not a property of any algorithm — it is a property of how much data there is, and an algorithm's complexity class says nothing about which side of it a program is working on.
-
Where an algorithm looks
Plotted as index against time, every array access an algorithm makes becomes a picture that no count contains. Merge sort's is a set of sweeps. Heapsort's is a spray. Quicksort's is a narrowing triangle. These shapes decide how fast the algorithms run and they are entirely absent from the analysis that says all three are Θ(n log n).
-
Where insertion sort actually wins
Every production sorting routine falls back to insertion sort on small subarrays, and the usual explanation is that below some threshold it does fewer comparisons. Measured, it does not — not at sixteen elements, not at eight, not at four. The crossover is real and it is entirely in memory traffic, which is a distinction the usual telling loses.
-
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.
-
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.
-
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.
-
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.
-
The order with the best depth
An edit-distance table can be filled row by row, column by column, or one anti-diagonal at a time, and the anti-diagonal order is the one that needs the fewest rounds — 513 against 65,793 on two strings of 256 characters, because every cell on an anti-diagonal is independent of the others. Stored the usual way, row by row, it also misses the cache on 31.1% of its reads, where row order misses 6.3%. The order that is best for parallel work is worst for the memory it runs on.
-
Two probes are two misses
Cuckoo hashing's lookup reads at most two slots, and at a load of 0.45 it reads 1.27 on average where linear probing reads 1.39. Replayed through a cache, it misses 1.18 times a lookup where linear probing misses 0.98. The table that wins the count the analysis uses loses the count the machine charges, because two slots in unrelated places are two cache lines, and a run of adjacent slots is usually one.
-
The table stored the way it is filled
Store an edit-distance table by anti-diagonals instead of by rows, and the anti-diagonal fill keeps its 513 rounds while its cache misses fall from 31.1% of reads to 8.7%. It does not fall to row order's 6.3%, and the gap is not noise — on caches of four and eight lines the two rates are 9.4% and 6.3%, exactly three to two, because a cell reads from two earlier diagonals and only one earlier row. The same layout turns row order into the order that strides, at 28.3%. How a table is stored and the order it is filled in are one decision, and its price is the number of earlier fronts the recurrence reads.
-
The bucket that fits a line
Make each of a cuckoo table's two candidates a bucket of eight slots laid out on one cache line, and no lookup ever touches more than two lines, the table builds past a load of 0.95, and at that load it misses 1.21 times a lookup where linear probing misses 1.79. The prediction that it would lose to linear probing at low loads was wrong — it misses less at every load measured, 0.94 against 0.96 at 0.3 — because a key it holds almost never lives in its second bucket. The guarantee belongs to the alignment, not the bucket; eight slots on lines of four put a lookup on four lines.
-
A lookup that stops caring how wide an entry is
Buckets of eight entries aligned to a cache line read 1.20 lines a lookup when an entry is eight bytes and 19.25 when it is 128, because the bound was arithmetic about alignment and the arithmetic stops holding. Keeping one byte of each key's hash in a separate array and the entries in a parallel one reads 2.21 lines at every width from four bytes to sixty-four — and for a key the table does not hold, 2.05 against 31.98.
-
Eight cells at once
The anti-diagonal fill order exists because its cells do not depend on one another, and every table filled here has been walked one cell at a time anyway. Computed eight at a time, a step touches 5.71 cache lines on the layout that stores the table by diagonals and 10.87 on the one that stores it by rows — and per cell the first keeps falling to 0.42 while the second stops at 1.27. The prediction that a diagonal step would touch three or four lines was wrong, and line-aligning each diagonal only takes it to 4.94.
-
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.
-
Entries found by the rank of their tag
A bucket whose tags are kept sorted is an index: the position a tag is found at is its rank, and a rank can address an entry. Drop the fixed slots and pack each bucket's entries in tag order, and a cuckoo table of 32-byte records holds 36.1 bytes a key at half load where slots hold 66.1, and 34.3 against 36.7 at 0.9. Every insertion pays for it by moving the entries after its rank: 99 bytes against 36 at half load, 586 against 105 at 0.9. The prediction that packing would lose above 70% load was about the wrong quantity.
-
The slack an insertion can reach
A cuckoo table whose entries are packed by tag rank holds half the bytes of a slotted one at half load, and pays by shifting entries on every insertion. It was proposed to keep a few spare entries at the end of each group's region. Charged the copies a full region costs, that slack helps only with the copies: at groups of 16 buckets an insertion still moves over a thousand bytes, against 36 for slots. The same slack divided among the buckets, with an insertion borrowing the nearest free entry, moves 347 — and the group size, which multiplied every earlier cost, stops mattering.
-
Spare where a bucket can use it
A cuckoo table packed by tag rank keeps a few spare entries in each region of sixteen buckets, and every time a region runs out it divides its spare among the buckets again. Divided evenly, most of the spare ends up in buckets that are already full, which never grow — they kick. Divided in proportion to where insertions have been landing, as proposed, more of it does, and an insertion at 90% load moves 1,159 bytes against 1,005. Divided by the room each bucket has left, only 3% of it is stranded, and at 95% load an insertion moves 10 to 17% less than with an even division. None of the three comes near the half-load figure, because all of the growth from half load to 90% is the cuckoo kicks' own cost.
-
The keys a capped chain leaves behind
At 95% load five sixths of the bytes a packed cuckoo table moves on an insertion are its kick chain, and the chain is mostly tail: capping it at two kicks removes 72% of the kicks. The proposal was to put the key still displaced into an overflow held in its region's spare, and it predicted that the bytes moved would halve. They fall by 13%. A key placed in the spare costs 1,819 bytes to insert, six kicks' worth, because the free slot nearest the region's end is far away and every entry between moves. The same cap with the overflow in a separate block halves the bytes as predicted, for a byte a key and an overflow that every failed lookup has to read.
-
The lookups a filter turns away
A capped cuckoo table keeps its stopped keys in an overflow block a region, and at 95% load every lookup for an absent key reads those blocks — 1.93 of them, because a key could have been stopped in either of its buckets' regions. A Bloom filter over each region's overflow at eight bits a key was predicted to let about 2% of those lookups through. It lets 2.07% through, and the prediction was right for two wrong reasons that cancel. Filing every stopped key under its first bucket halves the rest, and then the lookups the filter cannot help, the 3.9% of keys that really live in the overflow, are what is left to pay.
-
The block already open
A cuckoo table that caps its kick chain at two keeps the keys it stopped in an overflow block a region, and with a filter in front of each block a successful lookup's cost is set by the share of keys living there: 3.7% after one fill to 95%. Under deletions and insertions in equal numbers it was predicted to climb without limit unless every deletion moved a stopped key home. It does not climb without limit; it settles, at 9.2%. Homing at every deletion holds it at 4.0%, as predicted — by reading a block on 98% of deletions, and by sending a quarter of the insertions that follow to the overflow, because a key moved home takes the slot the next key needed. Moving keys home only when their block is already open for another reason holds the overflow at 4.9% for 0.07 blocks a pair more than leaving keys alone, and costs less than leaving keys where they stopped from one and a half successful lookups a deletion.
-
Room the chains could not reach
A cuckoo table that caps its kick chain at two, churned at 95% load, keeps 9.2% of its keys outside their buckets while 13.8% of its entries stand empty. Keeping a few entries in each region aside for the keys the cap stops, at the same memory, was predicted to remove most of the overflow for a tenth of a kick an insertion. It removes none of it: the share outside the buckets stays at 9.2% with up to eight entries kept back, because a key is stopped by the pair of buckets its chain visits, never by a region short of room. What the reserve changes is where the stopped keys sit, and that is worth having. Read with the region's header, four entries a region take the overflow blocks from 9.2% of keys to 6.1% when keys stay and from 4.9% to 2.3% when keys go home with an open block, for no kick anyone can measure — until the reserve takes room the chains were using, at sixteen entries when keys stay and at eight when they go home.