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.