A record of stretches, not pairs

The questions a sort asks twice found that selection sort already holds the answer to 19,561 of its 32,640 comparisons on 256 random keys, and that a record of past answers can skip them. The record measured where it would run priced the obvious record, a table of every pair, in cache misses. At 1,024 keys it missed nearly twice for every comparison it saved. A record the size of a pass’s minima found why only a small part of the table mattered. Indexed by the ordered pair, the questions a pass repeats live almost entirely in the rows of the current minima. A ring of those rows — twelve rows, 3 KB, the least recently used given up — caught 99.1% of the table’s skipped comparisons at 1,024 keys.

Its closing section pointed out that a row is still the wrong shape. A row records a minimum’s answers against every other key as scattered bits, but the questions a pass asks again are more specific. A minimum that recurs is compared, in the next pass, against the same keys the previous pass compared it with — the keys scanned while it was the current minimum. Those lie in one contiguous stretch of the scan. A record could store, for each link of the chain of minima, only the stretch of positions it covered, and answer every question inside that stretch without a bit a pair. That is a record of a handful of intervals rather than a handful of rows. The section predicted it would catch nearly as much as the ring. It would fail where the pass’s swap moved a key into the middle of a stretch, and the question was how often that happens.

The chain of one pass #

A pass of selection sort scans the unsorted part of the array keeping the smallest key seen so far. Each time a scanned key is smaller, the current minimum is replaced. The sequence of minima a pass holds is its chain. Each link covers a stretch: every position scanned while it was current. That stretch ends at the position of the key that beat it, the one comparison in the stretch that came out the other way.

In the next pass the same keys are scanned in the same order, except for the two positions the swap moved, and the current minimum passes through many of the same keys. When the current minimum sits at a position that was a link of the previous chain, and the position being scanned lies inside that link’s stretch, the answer is already known. The scanned key is larger, since it was scanned while that minimum stood — or, at the stretch’s last position, smaller, since that key beat it. The record answers, and the sort acts on the answer exactly as it would on a comparison.

The record keeps three words a link: the minimum’s position and the two ends of its stretch. A link’s stretch is the evidence, so the record has to know when the evidence has gone stale. That happens when a swap has moved a key into or out of either position since the pass that recorded it. Each pass swaps two positions, and the record checks both before it answers. The sort also checks every answer the record gives against the keys themselves, and checks that the record never answers a question that was not asked before. Neither check fires on any input on this page. Both are live: a version of the record that does not ask whether a swap has moved a position answers, in the second pass, a question about a key it never compared, and comparing that answer with the keys exposes it. That is the failure the section predicted, caught by the keys themselves rather than by a count that looks slightly too good.

The comparison that ends a stretch #

The stretch as the section proposed it held the keys scanned while a minimum was current — the keys that lost to it. That leaves out one comparison in every link: the one where a scanned key won and the minimum changed. It is as much a recorded answer as the others, and it is the one that tells the next pass where the chain turns. Kept, it costs nothing, since the stretch’s end is already stored; it is the key at the end.

The difference it makes depends on the input. Without the key that beat each minimum, the chain answers 97.9% of the table’s skips on random keys at 1,024; with it, 99.3%. On reversed keys the difference is total. Every key scanned there beats the minimum before it, so every stretch is empty of losers and consists of its end alone. Without the endpoint the chain answers none of the 261,632 repeated questions, and with it 99.8%. On organ-pipe keys the endpoint takes the chain from 29.4% to 78.9%. The proposal’s picture of a stretch as the keys a minimum survived was right for random keys, where a minimum survives many keys for each one that beats it. The endpoint is what makes it right for the inputs where minima fall at every step.

As much as a ring, from a few dozen words #

At 1,024 keys the previous pass’s chain answers 99.3% of the comparisons the full table would, and the ring of twelve rows 99.1%. The chain is short of the ring at small sizes — 2.1 points at 128 keys — and ahead of it from 512 keys, and its share keeps rising, to 99.8% at 4,096. The prediction said the chain would catch nearly as much as the ring. At every size from 512 keys up it catches more.

Keeping more than one pass adds nothing. With the chains of the last two or four passes kept, the record answers exactly the same comparisons as with one. Every question a random-key selection sort repeats that any chain could answer, the previous pass’s chain answers. A question asked two passes ago about a key and a minimum is asked again in the pass between whenever the evidence for it is still valid, so the latest chain already holds it.

A record the size of a harmonic number #

At 1,024 keys the chain is 312 bytes, a tenth of the ring and an eight-hundredth of the table. From 128 keys to 4,096 it grows from 216 bytes to 408, following the number of minima a pass meets. On random keys a pass meets about the harmonic number of the keys it scans, $H_m \approx \ln m + 0.58$, and the chain keeps a little more than one pass’s worth. It averages 5.5 links a pass at 1,024 keys and holds 13 at its longest. The ring’s rows are $n$ bits each, so twelve of them grow with $n$, and the table grows with $n^2$.

A record of 312 bytes fits in five cache lines, and it is read on every comparison. The earlier page priced its records in misses because the table and even the ring were large enough to be evicted by the array they sat beside. The chain is not: it is smaller than the stack frame of most sorts. What it costs is a lookup a comparison, the current minimum’s position in a small map. That is work of the same kind as the comparison it replaces, and for keys that are cheap to compare it is no saving at all. A record is worth keeping when a comparison is dear: long strings, or keys compared through a function a caller supplies.

Why the chain is the length it is #

The chain’s length can be predicted before the sort runs. A pass scans the $m$ keys not yet placed, and the current minimum changes at every key smaller than all before it. In a random order of $m$ keys the expected number of such left-to-right minima is the harmonic number $H_m = 1 + 1/2 + \dots + 1/m$. The chain keeps every link but the last, since the last is the pass’s minimum and is placed. So its expected length in a pass is $H_m - 1$. Averaged over the passes of a sort of 1,024 keys that is 5.52 links, and the measured mean is 5.48. At 128 keys the prediction is 3.50 and the measurement 3.31; at 4,096, 6.90 and 7.09. The small differences come from the unsorted part not being a fresh random order after each swap. They are within 6% at every size, and nothing in the record’s size is left unexplained.

That also says what the record costs to keep, which is the other half of its price. The chain is rebuilt every pass: three words written for each link, 16,815 words over the whole sort at 1,024 keys. The table instead writes one bit for each of the roughly 265,000 questions it records, each bit a read and a write of a word somewhere in 256 KB. The record that forgets on purpose found a cache of pairs that caught 91% of the table’s skips in an eighth of its bits, by forgetting on a schedule of its own. The chain forgets on the sort’s schedule instead. Every pass discards the old chain and writes the new one, and nothing it discards could have been used again.

The counts are exact, like every count on this collection. Counting instead of timing set that rule for the site, and a record is where it earns its keep. A timing of a record whose lookups cost about what a comparison costs would measure the machine. The count of questions answered measures the record.

What the chain misses #

The failure the section predicted — a key moved by the swap into a stretch — costs 0.04% of the table’s skips at 1,024 keys. It is rare for a structural reason. The swap at the end of a pass puts the first key of the pass where the pass’s minimum was. That position ends the final link’s stretch, and the final link is the minimum, which is placed and never asked about again. So the moved key usually lands where no kept stretch reaches. It breaks a stretch only when a later pass’s current minimum reaches back past that position, which becomes rarer as the array grows.

The larger loss is questions the previous pass did not ask: 0.65% at 1,024 keys. When the first key of a pass leaves for the sorted part, the next pass’s minimum over the first stretch of the scan is a different key, often one that was a minimum further back. Its comparisons were last asked in an older pass, and the swaps since have moved keys through those positions, so no older chain could answer them either. Keeping four passes’ chains recovers none of them. Both losses shrink as the array grows, which is why the chain’s share rises with $n$ while the ring’s, fixed at twelve rows, does not. The questions last asked before the previous pass fall from 3.86% of the table’s skips at 128 keys to 0.21% at 4,096, a little less than halving each time the array doubles. The questions the swap breaks fall faster, from 0.84% to 0.01%. The repeats themselves grow as $n^2$, while the places a chain can go wrong grow with the passes, one first stretch and one swap a pass, so the share of repeats that land there shrinks.

Where the chain grows long #

The chain’s smallness is a property of random input, and the other orderings show the limit. On reversed keys the chain answers 99.8% of the table’s skips, but holds 1,023 links, 24 KB: every key scanned in the first pass beats the one before it, so every position is a link. On organ-pipe keys it holds 256 links and answers 78.9%. Almost none of the fifth it misses is the swap’s doing, 228 of 38,804 questions; the rest were last asked before the previous pass, the loss that is 0.65% on random keys and here a fifth. On sorted keys selection sort never repeats a question, so there is nothing for any record to catch. The spread a merge sort does not have found quicksort’s comparison count varying three hundred times more than merge sort’s from one random input to another. The chain’s size varies far more with the input’s order, from 13 links to 1,023. It is set by how often the minimum changes, and an adversary controls that completely.

A ring of rows has a size fixed in advance and should have the opposite weakness. On reversed input every scanned key becomes a new minimum with no row, so its twelve rows would be replaced at every step, and it should catch little of what the chain catches there; that was not measured. The two records would then suit different inputs, and the one that suits random input is the one that is small.

Where these numbers stop applying #

Selection sort only. The chain is a record of one algorithm’s structure: a scan that keeps a running minimum. Heapsort’s sifts, insertion sort’s shifts and quicksort’s partitions repeat questions in other patterns, if at all, and each would need its own shape of record. The price of remembering an answer found the table paying for itself once a comparison costs more than about three word operations; the chain changes that price by making the record small, not by making the questions fewer.

Answers are checked, not trusted. Every answer the chain gives is compared with the keys, and every question it answers is checked against the full table of asked questions. The checks cost the same work as the sort without the record, so the counts here say what the record would save, measured by a sort that did not rely on it.

One shuffle at each size. Every random-key number is one shuffled input at each size. At 1,024 keys, eight other shuffles give shares from 99.28% to 99.35% and longest chains from 13 to 17 links, so the size of the record varies more than what it catches. The ring was measured on one shuffle at each size, so the comparison at 512 and 1,024 keys, where the two differ by 0.2 to 0.4 points, is a comparison of single runs.

Words of eight bytes. A link is three positions, each small enough for four bytes at these sizes. Packed, the chain at 1,024 keys would be under 160 bytes.

Still open: the chain for a sort that makes the same scan twice #

Selection sort is the one sort whose passes rescan almost the same keys in almost the same order, and that is why a record of one pass answers the next. Other scans are rescanned too. Bidirectional selection sort finds the minimum and the maximum in the same scan and places both, so each pass narrows the range from both ends and keeps two chains’ worth of structure. Two pivots and what they cost found dual-pivot quicksort doing fewer comparisons and nearly twice the swaps; a sort that swaps twice a pass is the case this record is most exposed to.

The measurement that follows gives bidirectional selection sort a record of both chains, the minima and the maxima of the previous pass, and asks what share of its repeated questions they answer and how large they grow. The prediction is that each chain behaves as the single chain here does, answering nearly all of its own side’s repeats in a harmonic number of links. The two swaps a pass makes should break more stretches than one swap does, since each lands where the other chain may reach. The measured quantity that says whether the idea generalises is that break rate: at 0.04% for one swap, a record of stretches is sound, and if two swaps drive it into whole per cent, the stretch is a structure only a one-sided scan keeps intact.