Miss rate — where it appears
Named by 9 essays across 4 fields — each of them below, with the objects they name alongside it.
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.
The count somebody chose
Six quantities can now be measured for every sort. Ranking the ten algorithms by each of them and comparing the orders, comparisons and peak space disagree about 91% of all pairs, and memory traffic and modelled misses disagree about 7%. There is no ranking of sorting algorithms; there are six, and choosing between them is a statement about the data rather than about the algorithms.
A list and a block of memory
The same traversal, over the same graph, examining the same edges in the same order, laid out two ways. Twelve thousand two hundred and eighty-eight edge slots either way; 11,812 modelled cache misses against 3,258. This is the site's largest gap between two counts of one run, and it exists because one of the layouts is a pointer chase and the other is a sweep.
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.
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.
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 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.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
CacheLocalityMemory layoutAccess patternWorking setEvaluation orderTrade offChained hashingCompulsory missCuckoo hashingDepthDynamic programming