A register dropped by what it already knew

A run end kept in a register priced the last expensive part of a sorting record. The two-ended selection sort scans the keys it has not yet placed for both the smallest and the largest, swaps them to the two ends, and repeats. After a pass that compares every key with its neighbour, it keeps a record of adjacent order — two bits a pair saying whether the key at a position is smaller or larger than the one after it — and answers any question about two positions it can from the record, since a run of pairs that all point the same way is a stretch of the array in order. What it costs to consult two bits a pair found that reading the record on every question costs about a word a question on short runs, and a filter that reads the word it saves that on short runs the record is asked 184 questions for every comparison it saves.

Every question starts from one of the sort’s two current extremes, so the essay kept, beside each, the end of the run of known order starting there: a register, filled by one scan of the record to the run’s first break and dropped when any pair inside the run, or the break itself, changes. On 1,024 keys in runs of four it cut the reading to a forty-fifth, 0.024 words a question, and stopped the price of a saved comparison growing with the input. On long runs it failed. On a sorted array of 1,024 keys the registers read 53.5 words a question, two and a half times the plain record’s 22.1, because they were refilled at nearly every question and each refill scanned a run hundreds of pairs long.

Its closing section blamed the swaps. Each scan swaps its extremes to the ends of the unsorted part; the record forgets the pairs around both swapped positions; a register whose run passes through either is dropped and refilled by scanning the whole run again. But a swap does not destroy what the record knew beyond the swapped position. A run from $i$ to $k$ that loses its pair at $p$ becomes two runs, and the second, from $p + 1$ to $k$, is still known in full. The proposal kept that second part as a register in its own right, in the dropped one’s place, and predicted that on the sorted array the reading would fall from 53.5 words a question to under the plain record’s 22.1, with nothing changed on short runs. It named one way to fail: the new extreme after a swap is usually not inside a run the register kept, so the kept part might never be asked about before it was broken again.

Two repairs to one register #

The sort, the inputs and the charges are the earlier essay’s: 256, 1,024 and 4,096 keys, cut into sorted runs of 4 keys up to the whole array, a pass between neighbours first, the previous scan’s chains of minima and maxima consulted before the record, and every question to the record charged at the 32-bit words it reads — sixteen pairs to a word. A register that holds the answer reads no word.

The survivor rule is the proposal’s. When a pair strictly inside a register’s run changes, the register’s start moves to the pair after the change and its end stays; when the break itself changes, the register is dropped, since the run may now be longer than it says. A second rule was added once the first had been measured, to test the failure the proposal named rather than to repair it: a register may answer a question from any position inside its run, not only from its start, since the run from there ends where the register’s does. Each register’s answer is checked against the record at every question, so neither rule can buy reading with a wrong answer.

Under one per cent #

Keeping the part of a register’s run beyond a break changes the reading by under 1% at every run length: on 1,024 sorted keys the registers read 53.54 words a question, with survivors 53.42, and answering from anywhere inside a run 53.42 — all far above the plain record’s 22.13. On runs of four nothing moves at all, 0.024 words a question with or without survivors, as the proposal expected. On runs of 64 the registers read 0.097 and the survivors 0.096; on runs of 512, 5.37 and 5.35. The two repairs land on the same line, and the line is the registers’ own.

So the prediction failed by more than a factor of two on the input it was made for, and the failure mode the proposal named — the kept part never asked — was half of it. Answering from inside a run was the test of that half: if the problem were that questions start in the middle of kept runs rather than at their starts, letting a register answer from the middle would have caught them. It catches 1,022 more questions out of 264,190 and saves an eighth of a word.

Kept and never asked #

Survivors are kept and almost never asked: on 1,024 sorted keys a register’s far part is kept 523,775 times and a question is put to one 1,022 times, about two a scan; on runs of four, 675 kept and 78 asked. The number of survivors kept grows with run length as the proposal expected, since a long run has many pairs inside it to be changed. The questions put to them do not grow at all in proportion. On the sorted array the sort asks 264,190 questions of the record, and a survivor answers 1,022 of them, two in each of its 512 scans.

That is the number that gives the mechanism away. Half a million changes inside registers’ runs, on a sorted array, is two changes for every question the sort asks. A sorted array is the input on which the sort has least to change: the smallest key is already at the left end, the largest at the right, and the scan that finds them has no reason to move anything. Something on that input is changing pairs inside runs at twice the rate the sort asks questions, and it cannot be the swaps.

No swap on a sorted array #

What drops a register is rarely a swap: on 1,024 sorted keys none of the 264,190 drops is at a swap, because a sorted array makes none, and 263,167 are a pair relearned at the value the record already held; from runs of 32 keys up, relearning is most of the drops. The drops were counted by why the pair under the register was touched. A swap forgets the pairs on either side of both positions it moves. A comparison between neighbours writes its answer into their pair, which is how the record learns; if the pair was unknown or held the other direction, that is learning or a change. If it already held the same direction, nothing about the record is different afterwards — but the rule the registers were given, drop when a pair inside the run is written, does not ask what was written.

On runs of four the three causes are of one size: 1,008 drops at a swap, 2,067 learned or changed, 1,063 relearned. There the registers already held, 98% of questions answered from one. As runs lengthen, the swaps stay at about two a scan, which is all a scan has, and the relearning grows with the runs: 6,850 drops on runs of 64, 30,932 on runs of 256, 263,167 on the sorted array. The earlier essay’s account was wrong about the cause on exactly the inputs where the registers failed. The swaps break registers at the rate of two a scan everywhere; it is the relearning that grows with the run, and so it is the relearning that made a refill scan a long run at almost every question.

The previous scan, written back #

The relearning is the previous scan’s answers written back: on 1,024 sorted keys 99% of the drops by a pair relearned as it was come from a neighbour’s question answered by the chains the previous scan left, 1% from the record’s own answers, and none from a comparison made. On a sorted array each scan’s largest-so-far moves one position at every step, since every key is larger than everything before it, and the question “is the key here larger than the largest so far?” is a question about two neighbours at every step. Two swaps a pass, and the stretches hold gave the sort chains of the previous scan’s minima and maxima, and they answer that question first, as a repeat. Their answer is about neighbours, so it is written into the record — at the value the record already held.

The writing is right. It is what keeps the record current when a pair has been forgotten and is learned again from a chain, and it costs nothing in comparisons. What was wrong was the register’s rule for when it is stale. The register watched for writes, and a write that changes nothing looks to it the same as one that breaks its run. On short runs the chains rarely answer neighbour questions — 155 of the relearning drops on runs of four come from them — and the rule cost little. On long runs nearly every step of every scan rewrites a pair inside the run a register holds, the register is dropped, and the next question from that extreme refills it by scanning the run to its end.

Linear in n #

On sorted arrays the registers read 13.54, 53.54 and 213.54 words a question at 256, 1,024 and 4,096 keys — about n ÷ 19, between two and two and a half times the plain record — and refill a register at every question; survivors move none of those numbers by more than a quarter of a word. A refill scans the run from the extreme to its end. On a sorted array nothing is ever out of order, so that run is everything from the extreme to the last key, including the keys already placed at the right — about three quarters of the array on average over the scans, at sixteen pairs a word, which gives the n ÷ 19. The plain record reads only to the position the question asks about, well under half as far, and so on the same input reads less than the registers: it never scans past what it needs.

That is why a structure meant to save reading read more than the thing it replaced. A register is a promise to read a long stretch once and answer from it many times. If it is dropped after every answer, it reads the long stretch every time and answers once, and its scan is longer than the question’s. The register’s whole value depends on its lifetime, and its lifetime was being set by a rule that could not tell a change from a confirmation.

Why short runs never showed it #

The same rule ran on runs of four, and there the registers were the success the earlier essay reported. Two things spared them. A short run holds few pairs, so a refill is one word: even dropped after every answer, a register on runs of four would read about as much as the plain record. And a short run is rarely rewritten by a chain, because on random runs the running maximum moves only when a new largest key appears, which in a run of four keys interleaved with others happens a few times a scan, not at every step. The runs too short to drop found that a record keeps even the runs of two keys, since they cost almost nothing; the same arithmetic makes a careless forgetting rule almost free on them.

So the defect was invisible on the inputs where the registers mattered most and enormous on the inputs where they were already losing, and those inputs failed for a reason that looked like the obvious one. The record that forgets on purpose and a record the size of a pass’s minima each found that what a record keeps is decided less by what it learns than by what makes it forget, and in both the forgetting was a rule someone chose. Here it was a rule nobody chose: a side effect of writing every answer about neighbours into the record, which is the right thing for the record and the wrong signal for anything that caches what the record says.

What the proposal’s account got wrong #

The proposal’s account of the failure was plausible and was not checked: swaps break runs, long runs are broken, so long runs fail. Every step was true of some input. Swaps do break registers, about two a scan on every input that is not already sorted. Long runs were the inputs that failed. But the account did not hold on the input the prediction was made for, because a sorted array has no swaps at all, and a measurement that had counted drops by cause would have said so before the repair was designed. The price of remembering an answer made a related point about records in general: what a record remembers is cheap to state, and what it costs to keep is decided by when it forgets.

The rule that forgot was written as “drop when a pair in the run changes” and implemented as “drop when a pair in the run is written”. Those are the same rule wherever the record only learns new things, which is what it does in the pass between neighbours and in the scans of a random input. They diverge exactly where the chains of a record of stretches, not pairs answer neighbour questions the record already holds, which is on long runs. The registers’ own consistency check, run at every hit, could never catch it: it asks whether a register that answers holds the right run end, and a register dropped too early never answers.

What the counts assume #

One sort. The drops are this sort’s: two extremes, chains consulted first, answers about neighbours written into the record. A sort that did not write chain answers back would not relearn, and would also not repair pairs a swap had forgotten.

Words as the cost. Reading is charged in 32-bit words of the record, as in the earlier essays; a refill and a question are charged the same way. A machine on which a long sequential scan is much cheaper per word than scattered reads would make the refills cheaper, and the conclusion about cause would not change.

Three sizes and one seed. The inputs are one shuffle per size, cut into sorted runs. The causes are measured, not modelled, and their proportions at each run length are close across the three sizes, but they are one sample of each.

Neither repair was the wrong idea in general. Survivors and answers from inside a run each answered something, a few hundred to a thousand questions. On a sort whose extremes do land inside kept runs — a sort that swaps more, on inputs that scatter its extremes — they might be worth their bookkeeping. On this sort and these inputs, a register’s far part is almost never where the next question starts.

Still open: a register that is not dropped by a confirmation #

The repair the counts point at is smaller than either of the two measured. A comparison or a chain’s answer that writes a pair at the value the record already holds changes nothing a register depends on, and a register could be kept through it: drop a register only when a pair under it becomes unknown or changes direction, and treat a write of the same value as no write at all.

The measurement that follows gives the registers that rule, alone and with survivors, on the same inputs at all three sizes, and charges the same reads, and then asks what the cheapest record is at each run length. The prediction is that on the sorted array the reading falls from 53.5 words a question to well under a word, since its 263,167 relearning drops become none and its registers are then refilled only when a scan ends, and that the price of a saved comparison falls with run length instead of rising, which would leave the registers cheapest at every run length and the run list’s search with no input on which to win. It could fail on the swaps, which still drop about two registers a scan everywhere, and on the pairs learned for the first time, which on short runs are twice as common as the swaps. If those were what kept the registers expensive, the sorted array would improve and nothing else would. The question is whether a record’s cost on long runs was ever about what changed in it, or only about how it noticed.