Locality — where it appears
Named by 21 essays across 5 fields — each of them below, with the objects they name alongside it.
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.
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. This site carries a second count — modelled cache misses from the same runs — and asserts that the two 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).
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.
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.
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.
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.
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 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.
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 bound a block can and cannot have
Knuth's condition turns an interval table's cubic fill into a quadratic one by bounding each cell's best split between its two neighbours'. A blocked fill cannot use it a cell at a time, and the two cells that bound a block lie outside the block — one to its left, one below it. The schedule has finished both for ten per cent of the blocks, the bound then removes eleven per cent of the splits, and it removes half a per cent of the cache misses, because the splits it skips are the ones already in the cache.
Positions confined to one line
A Bloom filter lookup reads 5.55 cache lines because its six positions are scattered across the whole filter. Confining them to a 512-bit block makes it exactly one, and costs 7% more false positives at eight bits a key. At sixteen bits a key the same block costs 91%, and the two-value trick that is free across a whole filter costs another 135% inside one — because a block is a small filter, and small filters are where the penalty lives.
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.
Two blocks and the chances they add
Send each key to the emptier of two 512-bit blocks and the busiest block of a filter at sixteen bits a key holds 38 keys instead of 55. The false-positive rate does not move: 0.100% against 0.095%. At eight bits a key it doubles. A lookup cannot tell which block a key went to, so it has to ask both, and asking twice is two chances to be wrong. The repair that tames a hash table's worst bucket buys a filter nothing that a block twice as wide does not.
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.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
CacheMemory layoutAccess patternMiss rateWorking setCost modelBlock transferDesign parameterDynamic programmingEdit distanceEvaluation orderExternal-memory model