The record that forgets on purpose

The price of remembering an answer gave each sort two records of what it had already learned and priced both. A table of the pairs asked removes every repeated question and costs two bits a pair, which is $n^2$ bits — sixteen to thirty-two times the size of the array it is sorting. The full transitive closure removes more questions and costs so much upkeep that it breaks even only past 425 word operations a comparison at 256 elements, and past 1,659 at twice that.

It ended by naming the structure between them. A table of every pair is a record with no forgetting in it; the obvious smaller thing is a record that forgets, of a fixed size that does not grow with $n$, holding the questions asked recently. It would catch repeats asked lately and miss ones asked long ago.

That structure is built here, and the interesting part is not whether it works. It is which property of the sort decides how well it works, because the obvious answer is wrong.

The cache #

The record is a direct-mapped cache of $E$ entries. A comparison of two values packs them into one key, smallest first, so that asking about $(a, b)$ and $(b, a)$ is one question — which is what the table of pairs does by writing both of its cells. The key is hashed to a slot. If that slot holds the same key the answer is already known; otherwise the comparison is made and the key is written there, evicting whatever was in it.

A lookup is one read. A miss is a read and a write. Those are counted in the same currency as everything else here, so the record’s price stays comparable with the table’s.

Its state is $E$ entries of $2\lceil \log_2 n \rceil$ bits — sixteen bits a pair at 256 elements, against the table’s two bits a pair over $n^2$ pairs. A thousand-entry cache is 16,384 bits where the table is 131,072.

The eviction is the whole difference from the table, and it is worth being precise about what is thrown away. The table of pairs never forgets, so its hit rate is exactly the repeat rate and its state is whatever $n^2$ happens to be. The cache forgets whatever it is told to forget by the hash, which is not the oldest entry and not the least useful one — it is whichever key last landed on that slot. A direct-mapped cache has no replacement policy at all, and that is a design decision rather than an omission: the alternative costs a comparison of tags on every lookup, and this record’s whole case is that a lookup is cheap.

One detail of the hash is load-bearing and was wrong first. Taking (key × C) mod E with $E$ a power of two keeps only the low bits of the product, and the low bits of a product depend only on the low bits of its operands. With the pair packed as $\text{lo}\cdot n + \text{hi}$ and $E = n$, the slot came out as a function of hi alone. Every pair selection sort asks inside one pass has a different hi, so nothing ever collided: a 256-entry direct-mapped cache behaved as a perfect 256-way associative one and reported catching 98.0% of the repeats where the correct hash catches 62.7%. Shifting the product right instead of masking it fixes it. The figure was drawn, the number was plausible, and the structure being measured was not the structure described — which is the failure the habit of checking the mechanism rather than the result exists to catch, arriving through arithmetic rather than through a picture.

How long a sort waits #

The cache catches a repeat only if nothing has evicted it. So the first thing to measure is how long each sort waits before asking a question again, in comparisons. That quantity is a property of the algorithm and nothing here had measured it, because the table of pairs catches a repeat whatever its gap — which is exactly why it costs $n^2$.

The two quadratic sorts have a distinctive shape: almost nothing within half a pass, nearly everything within a pass. Their curves are flat and then vertical. Selection sort’s repeated question is the one it asks the next time round, and the next time round is $n$ comparisons away — so the gaps pile up just under $n$ and hardly any fall under $n/2$.

Read as a design rule that says a cache of about $n$ entries should catch nearly all of them. It does not, and the reason it does not is the whole of this page.

What a fixed cache actually catches #

A cache of 256 entries — one slot for every pair the sort asks about in a pass — catches 63% of selection sort’s repeats, not 98%. Four times that many entries are needed for 91%, and sixteen times for 98%.

The model that predicts it has one line in it. Between a question and its repeat the sort makes some number of comparisons; a fraction of those miss the cache and write to it; each write lands on any particular slot with probability $1/E$. So a question survives with probability

$$\left(1 - \frac{1}{E}\right)^{m},$$

where $m$ is the number of writes in the gap. Averaging that over the measured gap distribution, at the measured write rate, gives 62.5% where the measurement gives 62.7%, 89.9% against 91.1%, 97.1% against 98.3%. Across both sorts and seven cache sizes the largest disagreement is 2.6 percentage points.

Nothing in that model knows anything about sorting. It does not know which pairs are asked, or in what order, or that the sort has passes. It knows the gap distribution and the write rate and it accounts for everything. The cache’s limit is not how far apart the repeats are; it is how much traffic passes through the cache in between, and a direct-mapped table of $E$ slots receiving $m$ writes has already lost most of what it held once $m$ reaches $E$.

That is a different quantity from the one the gap plate measures, and the two are easy to confuse because both are counted in comparisons. A gap of 182 comparisons is short by the standard of the run — half a per cent of it — and it is long by the standard of a 256-entry cache, which turns over completely in 256 writes. The cliff where the data stops fitting found the same distinction for a machine cache: what decides the hit rate is the working set against the capacity, not the distance between accesses in time.

The bill #

The useful point is the ringed one. A cache of 1,024 pairs reaches nine tenths of the repeats on an eighth of the table’s state, at a break-even of 3.53 operations a comparison against the table’s 3.12. Thirteen per cent more expensive per comparison, and eight times smaller.

Past that the curve goes flat in both directions at once, which is the signature of a structure that has stopped buying anything. Between 1,024 and 4,096 entries the state quadruples, the catch rises from 91% to 98%, and the break-even falls from 3.53 to 3.19 — a tenth of an operation for four times the memory. A system choosing a size on this evidence chooses 1,024 and stops.

The comparison that matters is against the table rather than against the closure. The closure at this size needs a comparison to cost 425 word operations before it pays, which the price of remembering an answer measured and which rules it out for anything short of a comparison that touches a disk. The table of pairs is genuinely cheap per comparison and expensive in state; the cache is the same price per comparison and eight times cheaper in state. The question these pages have been asking since the questions a sort asks twice — is a record worth carrying at all? — is not changed by this page. What is changed is the state it costs to carry one.

Which sorts have anything to cache #

The cache is only interesting where there is something to catch, and the gap plate has already said that the four sorts fall into three kinds rather than one.

The quadratic sorts repeat about half of their questions, sixteen thousand of thirty-two thousand, and their repeats are a pass apart. They are what a cache is for, and everything above is measured on them.

Insertion and merge sort repeat none at all. The questions a sort asks twice established that, and it is the reason bubble sort with a table of pairs makes exactly insertion sort’s count: bubble sort plus a perfect record is insertion sort. For these two the cache is pure overhead — a lookup on every comparison and never a hit — and its break-even price is infinite, which is the right answer rather than a missing one.

Heapsort and quicksort repeat a few hundred, and they are the interesting failures. Heapsort’s 195 repeats are spread across the whole run, so a cache large enough to hold them is a cache the size of the table; quicksort’s 286 are adjacent, so a cache of sixty-four entries would catch nearly all of them — and 286 comparisons out of 2,357 is not worth a lookup on each of the other two thousand. One has the wrong distances and the other has the wrong volume, and neither can be fixed by choosing a size.

That leaves the cache a structure for exactly the algorithms that nobody runs, which would be a fair objection if the point were to speed up selection sort. It is not. One run, four counts, four answers is the page that set the convention these pages work in: the quadratic sorts are the ones whose behaviour is legible, and a structure whose cost model can be stated exactly on them is a structure whose cost model can be trusted elsewhere.

And whether there is anything to catch is the input’s decision #

Everything above is random input. Changing it does not change the cache’s numbers by a few per cent; on two of the six combinations it removes the question entirely.

Selection sort on sorted input repeats not one of its 32,640 questions. Its running minimum is the first remaining element and is never replaced, so each pass asks about a different first element and no pair recurs. The table of pairs removes nothing, the closure removes nothing, and a cache of any size catches nothing — three records, three lookups a comparison, and no hits.

Bubble sort on reversed input repeats none of its 32,640 either, for the mirror-image reason: every comparison swaps, so the pair asked next is never one asked before.

On reversed input selection sort goes the other way — 16,256 repeats, 99.2% of them within a pass, and a 1,024-entry cache catches 95.2% of them at 3.22 operations a comparison, slightly better than on random input. So the same algorithm, the same $n$ and the same record span the whole range from “catches nothing at all” to “catches nineteen in twenty”, entirely on the arrangement of the input.

This is not a caveat on the measurement. It is the same finding one level up, and it is what the collision model already says: the cache’s catch rate is a function of the gap distribution and the write rate, and both of those are properties of a run rather than of an algorithm. An input that changes which questions get asked changes both. Where an algorithm looks drew the same point as a picture — the shape of an access pattern is not in the complexity class — and a record that exploits repeated questions is a structure that lives entirely inside that shape.

Where the cache would actually be used #

None of these break-even prices is met by an integer comparison, and that has been true since the record was first priced. A comparison of two machine words is one instruction and no record of any kind pays at three operations a comparison, let alone at 425.

Where three operations is cheap is a comparison that is not one instruction. The comparison that is not one comparison measured string comparison as a function of the shared prefix, and a pair of keys sharing a long prefix costs tens of character reads. At that price a record is straightforwardly worth carrying, and the question becomes which one — at which point the state matters, because the table of pairs at a million keys is $10^{12}$ bits and does not exist, while a cache of a few thousand entries is a few kilobytes at any $n$ at all.

That is the property the cache has and the table does not: its size is a decision rather than a consequence. The table’s state is fixed by $n$, so it is affordable at 256 elements and impossible at a million. The cache’s state is chosen, and what it buys at a chosen size is predicted by the collision model above from two measurable properties of the sort — the gap distribution and the write rate. A system can compute what a given budget will catch before spending it.

What the model also says is that the answer scales badly in the direction that matters. The gaps grow with $n$ for the quadratic sorts, because a pass is $n$ comparisons long, so holding the catch rate fixed means growing $E$ in proportion to $n$ — and a cache proportional to $n$ is not the fixed-size structure this page set out to build. It is a smaller constant on the same curve: $16n$ bits against the table’s $2n^2$, which at a million keys is two megabytes against two hundred and fifty gigabytes.

What is settled and what is not #

Settled, on 256 random elements, counted exactly: a direct-mapped cache of 1,024 pairs catches 91.1% of selection sort’s 15,835 repeated questions and 92.4% of bubble sort’s 16,033, holding 16,384 bits against the table of pairs’ 131,072. Its break-even price is 3.53 word operations a comparison against the table’s 3.12, and the curve is flat past that size — 4,096 entries buy 98.3% at 3.19.

Settled, across two sorts and seven cache sizes spanning a factor of 64: a model containing nothing but collisions, $(1 - 1/E)^m$ averaged over the measured gaps at the measured write rate, predicts the catch share to within 2.6 percentage points everywhere.

Settled, by measurement: 98.2% of selection sort’s repeats and 99.4% of bubble sort’s come within $n$ comparisons, and 24.6% and 39.5% within $n/2$. Heapsort repeats 195 questions and quicksort 286, against the quadratic sorts’ sixteen thousand.

Settled, on ordered input: selection sort on sorted input and bubble sort on reversed input each make 32,640 comparisons and repeat none of them, so no record of any kind removes anything. Selection sort on reversed input repeats 16,256, and a 1,024-entry cache catches 95.2% of them at 3.22 operations a comparison.

Not settled:

Associativity. The cache here is direct-mapped, which is the simplest thing and the worst of its family. A two-way or four-way set-associative cache of the same total size would lose less to collisions, and the model above says exactly how much is on the table: the gap between what the cache catches and what the table catches is entirely collisions, so at 1,024 entries there is nine per cent to recover and no more.

A replacement policy. A direct-mapped cache has no policy — the new key goes where its hash says. Least-recently-used within a set would help most where the gaps are widest, which is heapsort, which is also where there is almost nothing to catch.

Other sizes and other inputs. Everything here is 256 random elements. The gap distributions should scale with $n$ for the quadratic sorts and the catch share at a fixed $E$ should therefore fall, but that is an argument rather than a measurement.

The machine. The whole point of a fixed small record is that it could sit in a first-level cache while the array being sorted does not. Nothing here models that: the record’s cost is counted in word operations, the same currency as the table’s, and a structure that fits in a real cache and one that does not are priced identically. The count is not the time is the page that says why that is a limitation, and closing it needs the miss model rather than the counter.

Still open: the cache that is measured where it would run #

Every price on this page is in word operations, and the reason the cache is interesting is that it is small enough to sit in a machine cache while the array is not. Those two facts are not connected by anything here, and connecting them changes the comparison rather than refining it: a 16,384-bit record is two kilobytes and lives in the first level, while a 131,072-bit table is sixteen kilobytes and probably does not.

The measurement that follows replays each record’s own accesses through the cache model the machine essays use, rather than charging them at one operation each: the lookups, the writes, and the array reads the sort makes in between, all against a stated line size and capacity. It reports the modelled misses of the sort with each record beside its comparison count, which is the two-quantity plate the machine essays are built on.

The prediction is that the ranking reverses at some size. The table of pairs removes the same comparisons and touches a structure sixteen times larger, scattered by construction, so its own misses should grow with $n^2$ while the cache’s stay flat — and the point where the table’s misses cost more than the comparisons it saves is a crossing nothing on this page can see, because in word operations the table is strictly the better record at every size measured.