A register kept through a confirmation

A register dropped by what it already knew found why a cache had cost more than the thing it cached. The two-ended selection sort keeps a record of adjacent order, two bits a neighbouring pair, and answers questions from it when the pairs between two positions all point one way. A run end kept in a register put beside each of the sort’s two extremes a register holding where the run of known order starting there ends, so a question from an extreme could be answered without reading the record. On short runs that cut the reading to a forty-fifth. On a sorted array of 1,024 keys it raised it to 53.5 words a question, against 22.1 for reading the record plainly.

The cause was not the one first proposed. The sort’s swaps were blamed, and a sorted array makes no swaps. Of the 264,190 times a register was dropped on that array, 263,167 were a pair rewritten at the value the record already held: on sorted keys the scan’s largest-so-far moves one place at every step, so “is this key larger than the largest so far?” is a question about two neighbours every time, the chains the previous scan left answer it, and the answer is written into the record. The register’s rule dropped it on any write to a pair inside its run, and the next question refilled it by scanning hundreds of pairs.

That essay’s closing section proposed the smaller repair the counts pointed to: drop a register only when a pair under it is forgotten or changes direction, and treat a write at the same value as no write. It predicted that the sorted array’s reading would fall to well under a word a question; that the price of a saved comparison would fall with run length instead of rising, leaving the registers cheapest at every run length and the run list’s search with nothing to win; and named the failure, that the swaps and the pairs learned for the first time might be what kept the registers expensive on runs, in which case only the sorted array would improve.

The rule, and what it still drops on #

The sort, the inputs and the charges are those of the two earlier essays: 256, 1,024 and 4,096 keys cut into sorted runs of 4 keys to the whole array, a pass between neighbours first, the previous scan’s chains consulted before the record, and every question charged at the 32-bit words it reads, sixteen pairs to a word. A question answered from a register reads nothing; a refill scans the record from the extreme to the run’s first break.

Under the new rule a register is still dropped in three cases: a swap forgets a pair under it, a comparison learns a pair under it that was unknown, or a comparison or a chain’s answer turns a pair under it round. It is no longer dropped when a pair under it is written at the value it already held. Each register’s answer is still checked against the record at every question it answers, so the rule cannot buy reading with a stale run end: a register kept through a confirmation that had actually become wrong would fail the check at its next use. None does, at any size or run length.

A hundred and fifty-fourth #

Kept when a pair is rewritten at the value it held, the registers read 0.347 words a question on 1,024 sorted keys where they read 53.54, a 154th, and never more than 0.347 at any run length — under the plain record and under the run list’s search at every input. The sorted array was the prediction’s input and it moved by more than the prediction asked: well under a word, it said, and the reading fell two orders of magnitude below that word. But the run lengths in between moved too, which is the part the prediction left uncertain. On runs of 256 the registers read 1.14 words a question and now read 0.058; on runs of 512, 5.37 and now 0.093. On runs of 64 the fall is from 0.097 to 0.029, and even on runs of four, where the registers already held almost everywhere, from 0.024 to 0.022.

So the failure the proposal named did not happen. The swaps and the first-time learning still drop registers, but they drop them at a rate that does not grow with the run, and a refill after such a drop is no longer followed at once by another. Keeping registers past a break in their run, the earlier essay’s survivors, adds nothing on top of the new rule: the two together read exactly what the new rule reads alone, at every run length and size.

The reading stops growing with n #

Kept through a confirmation, the registers read 0.357, 0.347 and 0.345 words a question on sorted arrays of 256, 1,024 and 4,096 keys, where they read 13.54, 53.54 and 213.54: the reading stops growing with n on every input, and on runs it falls as n grows. On the sorted array the reading is flat because both the refills and the questions grow at the same rate. Each scan now refills its registers six times, whatever the size, and each refill still scans a run as long as before — but the scan asks about as many questions as the run is long, so the refills amortise to a third of a word a question at every size.

On runs the reading falls with n because the refills a scan stay near eleven while the questions a scan grow with the unsorted part. At 4,096 keys in runs of 64 a scan asks about 2,000 questions and refills eleven times, each refill reading a word or two. What it costs to consult two bits a pair began with a record that read about a word a question at every size; with registers that are not dropped by confirmations it reads under a hundredth of a word on 4,096 keys from runs of four to runs of 64, and the reading per question shrinks as the input grows.

A price that falls with the run #

Kept through a confirmation, the registers’ price of a saved comparison falls as runs lengthen — on 1,024 keys from 3.97 word reads at runs of four to 0.35 on the sorted array, where it was 53.75 — and the dearest saving is now the short run’s: 3.61, 3.97 and 3.88 at 256, 1,024 and 4,096 keys. That is the second half of the prediction, and it holds. The registers as they were drew a valley: cheapest per saving at runs of sixteen to 64, and dearer on either side, because on long runs every confirmation sent a register back to rescan. With the new rule the valley’s right side is gone. On long runs the record saves most — 263,167 comparisons on the sorted array of 1,024 keys, where a run of all the keys answers nearly every question — and the registers now read least per saving there too.

What is left is the left side of the valley — the side a filter that reads the word it saves found had a floor under it, because on short runs the record is asked many questions for every comparison it saves. On runs of four the record saves 1,438 comparisons on 1,024 keys and the registers read about 5,700 words to save them, nearly four words a saving at every size. The price of remembering an answer found that a table of the pairs a selection sort had already compared pays for itself once a comparison costs more than about three word reads. The registers now clear that line by a factor of nine on sorted keys, and on runs of eight they cost 2.2 to 2.3 a saving, under it. On runs of four they are still over it, at 3.6 to 4.0.

What a scan still refills #

What is left to read is a handful of refills a scan: kept through a confirmation, the registers on 1,024 keys refill 10.63 times a scan on runs of four and 5.99 on the sorted array, against 1.97 drops a scan at a swap and 4.18 at a pair learned or changed on runs of four. A scan has two extremes, each starts the scan with an empty register, and each fills it at its first question: that is two refills a scan before anything is dropped. Each time the scan’s minimum or maximum moves to a new position, the question starts from a position no register describes, and that is a refill too. The swaps add two drops a scan, one at each end, and the pairs a scan learns for the first time add about four.

On the sorted array the refills are exactly six a scan at every size, since nothing is ever swapped and the extremes never move from the ends of the unsorted part. On runs the count sits between ten and twelve and barely moves with run length, which is why the reading per question kept falling as the questions per scan grew. The refills are now set by the sort’s own structure — two extremes, two swaps, a few new pairs a scan — and not by how much of the record the scan happens to confirm.

Nothing left to choose #

Kept through a confirmation, the registers are the cheapest record at every run length on 1,024 keys — 49 to 73 times under the next-cheapest on runs, and 5.75 times under the run list’s search on the sorted array, the least — and the choice the pass’s run count used to make has nothing left to choose. A run end kept in a register ended on a chooser: read the number of runs off the pass between neighbours, and use the registers on short runs and the run list’s binary search on long ones, since each won on its own side. The plain record never won anywhere the registers or the list did not.

With the new rule the run list’s only input left is the sorted array, and there it reads two probes a question against the registers’ third of a word. The list’s search costs a logarithm of the number of runs, which is small when there are few runs; the registers cost a refill amortised over a scan, which is smaller still when the runs are long. Both structures exist to exploit long runs, and the registers now exploit them better, at the cost of two words of memory beside a record the list does not need at all.

What the registers cost to hold #

The comparison with the run list is a comparison of reading, and the two structures do not hold the same thing. The record of adjacent order is two bits a pair, 64 words on 1,024 keys and 256 on 4,096, and the registers sit beside it: two of them, each a starting position and a run end, four words in all. A run list holds three words a run, its start, its end and its direction, and on a sorted array it is one run, three words, with no record behind it. A record of stretches, not pairs built the list for that reason, and on the input of one long run it remains the smaller structure by a factor of about twenty.

So on the sorted array the registers buy a factor of 5.75 in reading for a factor of about twenty in memory, and on runs of 512 — two runs on 1,024 keys, six words of list — they buy 48 in reading for a record about eleven times the list’s size. Which trade is right depends on how often the record is asked and on what memory costs, and neither number is measured here. What the measurement does settle is that the reading no longer decides it: the registers read least everywhere, so a choice of record is now a choice about memory alone. The runs too short to drop found that the record keeps everything the run list keeps in a thirty-second of its memory on random keys, so across most inputs the registers and the record are both the smaller structure and the cheaper one to read; only on very long runs does the list win back anything, and what it wins back is space.

Why a confirmation looked like a change #

A rule that drops a cache when its source is written is the safe default, and it is what the registers had. It is safe because a write that changes nothing costs one unnecessary refill, and a write that changes something and is missed costs a wrong answer. The trouble was that the cost of the unnecessary refill was never small. A register’s refill reads its run, and a run on a sorted array is most of the array; a write that confirmed a pair at every step of every scan turned a cache meant to read the run once a scan into one that read it at every step.

The repair costs one comparison of two bits, the pair’s old value against its new one, at each write, and nothing else. It needs no change to the record, the sort or the chains. Two swaps a pass, and the stretches hold built the chains whose answers caused the confirmations, and those answers were and remain the right thing to write: they restore pairs that swaps forgot. What changed is that a register now reads the write rather than only noticing it.

What the counts assume #

One sort and one seed per size. The inputs are one shuffle each, cut into sorted runs, at three sizes. The refills a scan are close across sizes and run lengths, which is the evidence that they come from the sort’s structure, but they are one sample of each input.

Words as the cost, and comparisons as a separate one. The price of a saved comparison divides reads by comparisons; whether a saving pays depends on what a comparison costs on the machine and the keys, which the table’s break-even of about three word reads stands for and does not measure.

Two registers. The sort has two extremes and keeps two registers. A sort that asked questions from more positions would need more, and the refills from moved extremes would grow with them.

A check that would catch a wrong register. Every answer from a register is compared with the record’s own answer; the rule could only be wrong by keeping a register through a write that did change its run, and that would fail at the register’s next use. That check is why the rule can be stated as safe rather than measured as usually right.

Still open: a record switched off where it cannot pay #

The registers have made the record cheap to consult everywhere but on the shortest runs, where it saves too little to pay for any reading at all. On runs of four the record saves 1,438 comparisons on 1,024 keys and the registers read nearly four words for each; on runs of eight they read 2.3, under the three or so at which a table of compared pairs breaks even. The pass between neighbours already counts the runs before the first scan, and the earlier chooser used that count to pick between records. It could use it instead to decide whether to consult any record.

The measurement that follows reads the mean run length off the pass, consults the record through the registers only when it is at least a threshold — swept from two keys to sixteen — and otherwise asks every question as a comparison, and charges reads and comparisons together at exchange rates of one to four word reads a comparison. The prediction is that at three word reads a comparison the cheapest threshold is a mean run of six keys, so that runs of four lose their record and gain about a fifth of their cost back, and runs of eight and up keep it. It could fail on inputs whose runs are uneven: a mean of four can hide a few long runs where the record saves most of what it saves, and switching it off by the mean would give those back. The question is whether one number from the pass is enough to decide whether a record is worth reading, or whether the record’s value on an input lives in the runs a mean cannot see.