The record measured where it would run

The record that forgets on purpose gave selection sort a small record of the questions it had asked: a direct-mapped cache of 1,024 pairs, each pair packed smallest first so that asking about $(a, b)$ and $(b, a)$ is one question. It caught nine tenths of the sort’s repeated questions on an eighth of the state of a table of every pair. Priced in word operations, the table was still slightly the better record — a break-even of 3.12 operations a comparison against the cache’s 3.53 — because it catches every repeat.

That page’s closing section said the price was in the wrong currency. The cache is interesting because it is small enough to sit in a machine’s first-level cache, and the table is not: at 1,024 keys it is 256 KB. Nothing in a count of word operations connects those two facts. The section proposed replaying every access the sort and its record make through the cache model the machine essays use, and predicted that the ranking would reverse at some size. It expected the table’s misses to grow with $n^2$ and the cache’s to stay flat, until the table’s misses cost more than the comparisons it saves.

The prediction is right about the table as written, and it reverses early. It is wrong about why, and the difference is worth more than the reversal.

Every access, in order, through one cache #

The replay is exact. The counted harness every sort in these essays runs through records each array index it reads or writes; the record’s own reads and writes are recorded from inside the comparator, in the same stream, so the interleaving is the real one. Every access is a word of eight bytes, the array one word a value. The table is two bits a pair, 32 pairs a word, with row $a$ holding the pairs $(a, \cdot)$. The cache’s entries are a packed pair of indices, two to a word. Each region starts on its own line. The stream then goes through a least-recently-used cache of 64-byte lines at a stated capacity: 64 lines (4 KB), 512 lines (32 KB, a first-level cache) or 4,096 lines (256 KB).

Four records are compared. No record makes every comparison and touches only the array. The cache of 1,024 pairs is the earlier page’s, 4 KB of entries. The table of pairs is the earlier pages’ table exactly as it was specified: a question $(a, b)$ looks up the cell $[a][b]$ and, when the comparison is made, writes $[a][b]$ and $[b][a]$, so that either order of asking finds it. The ordered table holds the same bits and the same answers, but records each question once, at $[\min][\max]$, and looks it up there.

The sort is selection sort on random keys, as on the earlier page. Every run is checked sorted, and the comparisons made and skipped are counted exactly.

A reversal between 256 and 512 keys #

Up to 256 keys all four records cost almost nothing: the table is 16 KB at 256 keys and fits in 32 KB, so after its first touches everything hits. At 512 keys the table as written is 64 KB and does not fit, and its misses jump a hundredfold, from 288 to 32,513. At 1,024 keys they are 477,824 and at 2,048 more than two million.

The cache of 1,024 pairs sits at its compulsory misses throughout: its 4 KB and the array are all it ever touches, so after the first pass everything it needs is resident. So the prediction’s reversal happens, and early. At 512 keys the table skips 62,653 comparisons against the cache’s 49,797, 12,856 more, and pays 32,385 more misses to do it. Wherever a miss costs more than a comparison — which is everywhere a machine has a cache — the table is the worse record from 512 keys on.

But the fourth line does not follow the prediction at all. The ordered table holds exactly the same $n^2$ bits as the table as written, catches exactly the same repeats, and skips exactly the same comparisons. At 1,024 keys it misses 3,079 times, 155 times fewer. Its size is the same; its misses are not. So the table’s size was never what the misses were paying for.

One row a question #

The first pass shows the mechanism. Selection sort walks the unsorted part comparing each key with the smallest found so far. In the harness’s order of operands, a question is (the key being examined, the current minimum). The key being examined is a different key every time, and the minimum changes only when a smaller key turns up — twice in this pass of 32 keys, and about $\ln n$ times in general.

So the table as written looks up and writes cell $[a][b]$ in the row of the key being examined: a new row for every question. Each row is $n$ pairs, 32 words at 1,024 keys, and the pass’s questions land in 1,023 different rows. Every lookup reads a word in a row that was last touched a whole pass ago, and a pass of selection sort at 1,024 keys touches far more than 32 KB. The write at $[b][a]$ lands in the row of the minimum, which stays put, and that half is cheap. The half that costs is the lookup and the first write, and they are the half the earlier pages specified as the record’s primary cell.

The ordered table puts every question in the row of its smaller key, and in selection sort the smaller of (key, minimum) is almost always the minimum. That is what a minimum is. A pass therefore reads and writes a handful of rows — the minimum’s, and the next one when the minimum changes — and walks along them. Its misses are the first touches of the minima’s rows: at most four lines a row at 1,024 keys, and fewer for the later minima, whose questions reach only the keys above them. That bounds them by 4,096, and 3,079 are measured.

The record’s cost in a cache is set by which operand indexes the row, and the choice is invisible in a count of word operations, which charges a lookup the same wherever it lands. It was made without a thought on the earlier pages — “write both cells so either order finds it” — and it turns out to be the whole of the table’s cache bill.

Why a count of operations could not see it #

The earlier pages priced the records carefully, and every price they gave is still correct. The price of remembering an answer charged the table one operation a lookup and one a write, and the questions a sort asks twice counted which questions repeat and when. Neither count has a place for where in memory an operation lands, because a count of operations has no memory in it. A lookup at $[a][b]$ and a lookup at $[b][a]$ are one operation each, and they are the same operation.

What distinguishes them is the one thing a count discards: the order in which addresses are visited. Where an algorithm looks drew that order as a picture for the sorts themselves — merge sort’s sweeps, heapsort’s spray — and showed that the picture decides the cache’s verdict while the count stays the same. A record inherits its sort’s picture and adds its own on top, and the table as written adds a spray to a sort whose own accesses were a sweep. The same table read the other way adds a second sweep.

This is the same kind of finding as the table stored the way it is filled, which moved an edit-distance table’s cache misses by more than a factor of three — 31.1% of reads to 8.7% — by changing only how the table’s cells are laid out in memory. There the choice was between rows and anti-diagonals and the data were the same; here it is between $[a][b]$ and $[\min][\max]$ and the answers are the same. In both, a layout decision that a count of operations cannot express is worth more than the operations the count can see. And in both the decision was made early, in a sentence about correctness — here, that either order of asking must find the answer — long before anyone asked what it would cost, which is the usual way a layout gets chosen.

The same bits at three capacities #

The capacity sweep separates the two ways a record can miss. At 256 KB the whole table fits, and the table as written misses 4,214 times: its first touches of 256 KB plus a little. That is the cost of its size, and it is small. At 32 KB the table as written misses 477,824 times, and the ordered table 3,079. Only a scattered access pattern can do that at a capacity where an orderly one gets by, so that is the cost of its layout.

At 4 KB even the array does not fit — 1,024 keys at eight bytes are 8 KB — and every design misses on every pass. The cache of pairs misses 182,882 times there, more than the ordered table’s 66,257. At that capacity its 4 KB of entries compete with the array for the same lines, and its accesses land on slots chosen by a hash, which is scattered by design. A record small enough to fit is only an advantage if the cache it is meant to fit in is larger than the record plus the data it is recording about. The cliff where the data stops fitting measured that edge for data alone; a record moves it.

What a saved comparison costs #

Put as an exchange rate, the three records are three different kinds of structure.

The cache of pairs is free in misses, at every size measured: its 64 added misses are its own 4 KB being touched once. What it skips is a shrinking share, 30% of the comparisons at 1,024 keys and 16% at 2,048, because a fixed number of entries covers less of a pass as the pass grows. That is the collision arithmetic the earlier page modelled.

The ordered table buys comparisons at about 36 a miss. Against the cache of pairs at 1,024 keys it skips 102,870 more comparisons for 2,887 more misses. Whether that pays depends on what a miss costs in comparisons on a particular machine; a first-level miss that hits in the second level costs perhaps ten or twenty times a comparison, so on most machines the ordered table is worth its misses at this size.

The table as written pays 1.8 misses for every comparison it skips at 1,024 keys. It is never worth having outside a cache large enough to hold it whole, and once a cache is that large there is no reason to have chosen its layout.

So the ranking the earlier page read off a count of word operations — table first, cache a close second — is right for the ordered table and wrong for the table as specified. The prediction said the table would lose to the cache at some size. It does, in the form the earlier pages wrote down. In the form a reader would write if they had seen this plate, it wins at every size measured.

A repair that belongs to the sort #

The ordered layout is not a property of the table. It is a property of the table and selection sort. It works because one operand of every question in a pass is the same key, and the smaller operand is usually that one.

Bubble sort has no such key. Its questions compare adjacent positions, and the values at adjacent positions are unrelated, so the smaller of any pair is a different value every time. The ordered table therefore lands in a new row for every question, exactly as the table as written did for selection sort, and misses 473,025 times at 1,024 keys. The repair that took selection sort from 477,824 to 3,079 leaves bubble sort where it was. The cache of pairs, being scattered by design and small by design, misses 192 times under either sort.

Insertion sort and merge sort show the other limit, the one the record that forgets on purpose found in comparisons: they never ask a question twice. Either record skips nothing for them, and the ordered table’s few thousand misses are its first touches, paid for no saving at all. A record is a bet that a sort will repeat itself, and its layout is a second bet on how.

What was measured and what was not #

One cache model. A fully associative LRU cache of 64-byte lines, which is the model every plate in this collection’s machine essays uses. A real first-level cache is set-associative, and a table whose rows are a power-of-two number of lines apart would conflict in a way this model cannot see. That would make the table as written worse, not better. One access, eight kilobytes is the page on what a block costs.

Misses are counted, not timed. The exchange rate of 36 comparisons a miss for the ordered table is a count of both. Converting it to time needs a machine’s miss penalty and comparison cost, which the count is not the time is about. The table as written loses to the cache of pairs on any machine where a miss costs more than about half a comparison, and the ordered table beats the cache on any machine where a miss costs less than about 36.

Two bits a pair, packed 32 to a word. The table’s size is the earlier page’s, and the cache’s entries are rounded up to 32 bits each where the earlier page’s are $2\lceil \log_2 n \rceil$ — 20 bits at 1,024 keys — so the cache’s 4 KB is an overstatement by about half again, and its misses would be lower still.

Random keys only. On sorted input selection sort’s minimum is always the next key and the ordered table’s rows are visited in order; on reversed input the minimum changes on every question and the ordered table scatters as badly as the table as written. Neither was measured, and the second is the case where the ordered layout’s advantage should vanish.

Still open: the minimum’s row as the whole record #

The ordered table works because selection sort’s questions in a pass share one operand, the current minimum, and the table’s row for that operand holds every answer the pass needs. That suggests throwing away the rest of the table. A record of one row — the answers the sort has had about the current minimum, $n$ bits — would catch the same repeats whenever the minimum a pass ends with is the minimum a later pass starts with. That happens exactly when a pass’s minimum is found and removed, and the next pass’s first minimum is a key the previous pass already compared against.

The measurement that follows gives selection sort a record of one row per recent minimum, a ring of $r$ rows of $n$ bits each, and asks what share of the table’s skipped comparisons each $r$ catches, what it costs in misses, and whether a ring of a few rows beats the cache of pairs on both axes at once. The prediction is that $r$ of about $\ln n$ rows catches most of the repeats, because a pass revisits roughly the minima the previous pass passed through, and that the ring then costs a few kilobytes and misses no more than the cache of pairs does. That would make the best record for selection sort a record of its own structure rather than a table of every pair or a hash of recent ones.