What the machine does
The count is not the time
Why the textbook operation count and the running time diverge, what a stated cache model can and cannot establish, and how carrying two independent counts changes the ranking of the same algorithms.
The cliff where the data stops fitting
The working-set curve measured, why the transition from hitting to missing is a cliff rather than a slope, what it means for an algorithm whose cost per element does not change with n, and the two kinds of miss that behave differently.
Where an algorithm looks
The access-trace picture for each sorting algorithm, what its shape says about locality, why the recursive algorithms narrow and the heap-based one does not, and what a measure of sequentiality can and cannot capture.
Where insertion sort actually wins
The insertion-sort cutoff every standard library implements, measured in two counts at once — the comparison count never crosses and the total read-and-write count does, between twelve and sixteen elements.
The branch the machine guesses
A modelled two-bit branch predictor as the fifth counter, why it re-ranks the algorithms four other counters had already ranked, and what a predictable comparison actually is.
A search with no branch to miss
Branchless binary search measured against the ordinary one, why its mispredictions do not grow with n, and the overflow bug that lived in every published binary search for twenty years.
Two searches, one comparison count
The same tree in three memory layouts, with the comparison count held identical, so that the entire difference in cost is the arrangement — the clearest case yet of two counters ranking the same work differently.
A column computed in machine words
Myers's bit-parallel edit distance, why the unit has to change before the result can be stated, and the crossover where doing more elementary work stops paying.
Rank is the only thing it does
What a rank query actually costs — the two-level directory and its block-length trade, the wavelet tree that turns an alphabet rank into a handful of bit ranks, and the text's entropy appearing as an operation count.
Select is not rank backwards
Constant-time select over a bit vector — why its directory has two cases, what the bound is measured in, and the density at which the structure that costs nothing wins.
A function with r pieces
Why the function that turns one occurrence into all of them is piecewise linear with as many pieces as the transform has runs, and what checking that costs.
The table that fits inside a block
Where constant time comes from in a succinct range minimum — the ±1 property, the block length that makes an exponential table small, and what a query actually touches.
A lookup that stops caring how wide an entry is
A cuckoo table's entries held inline in the bucket against the same table with a line of one-byte tags in front, counted in distinct cache lines a lookup reads, swept over entry width, bucket size, tag width and load — with the accidental tag matches counted rather than assumed.
The count that was already there
Why a compound wavelet-tree walk costs exactly what a plain rank costs, measured on an operation counter, and the other places the same identity was available and unused.
A node costs two ranks
The arithmetic identity that halves an interval-enumeration descent, why no check on its output can catch its absence, and what an operation count has to claim instead.
Twenty bits apart
Where Elias–Fano and a block-classed bit vector cross, why they behave oppositely across the density dial, and what decides between them at the crossing.
What a character costs on four machines
Four regular-expression machines measured per character on one text, and the two currencies a matcher's cost is paid in.
The order with the best depth
An edit-distance table filled in three orders on a row-major array, with every read replayed through a cache model. The anti-diagonal order has the smallest depth and the worst locality, row order the reverse, and a cache large enough to hold an anti-diagonal's rows erases the difference.
Two probes are two misses
Linear probing, chaining and cuckoo hashing measured in entries read and in cache misses per lookup, across loads. Cuckoo reads the fewest entries at every load it can be built and misses more often than linear probing at every one of them, while a cache that holds the whole table reverses the picture for chaining alone.
The bucket that fits a line
Cuckoo hashing with buckets of two, four and eight slots, measured against linear probing and plain cuckoo hashing in entries read, cache misses per lookup, the most lines any one lookup touches, and misses for keys the table does not hold. Aligned buckets bound every lookup to two lines and miss less than linear probing at every load from 0.3 to 0.95; keys the table does not hold cost them a flat 1.87 misses, which linear probing beats until a load between 0.75 and 0.85.
The table stored the way it is filled
An edit-distance table stored by rows and by anti-diagonals, filled in row, column and anti-diagonal order, with every read replayed through caches of 2 to 1,024 lines. The diagonal layout gives the anti-diagonal order a streaming miss rate at its own depth, three streams to row order's two, and needs one more cache line than row order to reach it.
Eight cells at once
An edit-distance table's anti-diagonals computed several cells at a time, counted in distinct cache lines per step and per cell on three layouts, swept over the step's width and the table's size — with the step's own resident set measured as the limit on how wide a step is worth making.
A tag that answers more than yes
A cuckoo table's tag array, cut three ways out of a 32-bit hash and kept sorted: the tag comparisons an absent and a stored key's lookup makes, the entries each cut causes to be read, how many of a bucket's keys a tag can tell apart at each width, and what a sorted bucket costs to maintain as the bucket grows.
Entries found by the rank of their tag
A bucketed cuckoo table with sorted one-byte tags, its entries kept either in fixed slots or packed by tag rank behind a pointer per group of buckets: the bytes held per key across load, the bytes an insertion moves including cuckoo kicks, the entry width below which a pointer a bucket costs more than the empty slots save, and what a larger group buys against what it costs to insert.
The slack an insertion can reach
Packed layouts of a bucketed cuckoo table of 16,384 slots with 32-byte entries, reallocation charged: slack at the end of each group's region, slack divided among the buckets with the region rewritten when a bucket's run fills, and slack divided among the buckets with the nearest free entry borrowed — bytes moved an insertion against the spare kept, the share that is copying, bytes moved against load, bytes held against bytes moved for every group size and amount of slack, and bytes moved against group size.
Spare where a bucket can use it
The packed cuckoo table of 2^16 slots in buckets of eight, 32-byte entries packed by tag rank in regions of sixteen buckets with the nearest free slot borrowed, its spare divided at each redistribution evenly, by each bucket's insertions since the last one, or by the entries each bucket can still take: bytes moved an insertion against the load, how full the buckets are, where each rule's spare sits, the bytes of the kick chains, and bytes moved at the highest load against the amount of spare.
The keys a capped chain leaves behind
A packed cuckoo table of 2¹⁴ slots in buckets of eight, 32-byte entries packed by tag rank in regions of sixteen buckets with sixteen spare entries divided by room left, filled to 95% load with each key's kick chain capped at 0 to 8 kicks and the key still displaced put in an overflow, either in the free slot nearest its region's end or in a separate block a region: the bytes an insertion moves against load, the kicks the cap removes, where the bytes go, every cap for both places, and the overflow entries a failed lookup must compare.
The lookups a filter turns away
A packed cuckoo table of 2¹⁴ slots in regions of sixteen buckets, filled to 95% load with each kick chain capped at two and the stopped keys kept in a separate block a region, with a Bloom filter over each region's overflow keys asked by 16,384 absent keys: the share of failed lookups that reach a block against the filter's bits, the blocks a lookup reads because it asks two regions, double hashing against a mix for every probe, filters sized to the overflow against a fixed filter a region, the stopped keys filed under their first bucket, and the failed and successful lookups an insertion at which the cap breaks even.
The block already open
A cuckoo table of 16,384 entries in buckets of eight, regions of sixteen buckets, a kick chain capped at two and stopped keys filed under their first bucket's region, filled to 85%, 90% or 95% and churned through 131,072 deletions each followed by an insertion: the share of keys in overflow through the churn with keys left in place, moved home at every deletion, and moved home only when their block is read or written anyway; blocks read and written and keys homed for each pair; the settled share at three loads; blocks touched against successful lookups a deletion; and kicks and stops an insertion.
Room the chains could not reach
A cuckoo table of 16,384 entries in buckets of eight, regions of sixteen buckets, a kick chain capped at two and stopped keys filed under their first bucket's region, with 0, 1, 2, 4, 8 or 16 of each region's 128 entries kept back for stopped keys at the same memory, filled to 85%, 90% or 95% and churned through 131,072 deletions each followed by an insertion: the share of keys in overflow blocks through the churn; the split of keys outside their buckets between reserve and block; kicks and stops an insertion under three homing policies; the blocks' share under each policy; the shares at three loads; and overflow blocks touched against successful lookups.