A run end kept in a register

A filter that reads the word it saves found the floor under a record’s price. The two-ended selection sort keeps, after a pass between neighbours, a record of two bits a neighbouring pair saying which way each pair points, and a question about positions $i < j$ is answered without a comparison when every pair from $i$ to $j - 1$ points one way. On 1,024 keys in sorted runs of four, the sort asks its record 184 questions for every comparison the record saves, and any record read at least once a question pays at least that many reads a saving. The plain record read 1.094 words a question and so 201 a saving; a filter bit beside each pair, read in the same word, turned away two thirds of the questions and brought the price only to 185.

Its closing section looked at where the questions come from. The sort scans the keys still unsorted for the smallest and the largest, so every question it asks starts from its current minimum or its current maximum, positions it already holds in registers, and it asks hundreds of questions from each before either changes. What the record can say about all of those questions is one number: how far the run starting at the extreme reaches. A question about $j$ is answerable exactly when $j$ lies inside that run. A sort could find the run’s end once, by reading the record from the extreme to the run’s first break, keep it in a register, and answer every later question from that extreme with one comparison of $j$ against the register, reading nothing. The register is stale, and must be refilled, when the extreme moves or when a pair inside its run, or the break that ends it, changes.

The prediction was that on runs of four keys the reads would fall from about one word a question to about one word for every change of extreme, that the price a saved comparison would fall from 185 to under ten at 1,024 keys and stop growing with the input, and it named the risk: on long runs each pass’s two swaps break the run the register holds, and every break forces a rescan of the whole run.

All three hold.

Two registers beside the two extremes #

The sort, its pass, its chains of past minima and maxima, the inputs and the record of two bits a pair are the earlier essays’, and the charging changes nothing about the sort or its answers. Two registers are added, one for each of the last two positions questions were asked from, which in practice are the current minimum and maximum. A question from a position with a valid register reads no word of the record. A question from any other position fills a register: it reads the record from that position to the first pair that breaks the run, a word for every sixteen pairs it crosses, keeps the run’s last pair in the register, and evicts the older of the two.

A register is dropped whenever the record changes inside the run it describes or at the pair just past its end, because then the run may have grown or broken. That happens when a scan compares two neighbours and records their order, and when the swaps at the end of a scan move a key and the record forgets the two pairs around it. Every time a question finds a register valid, the run end it holds is checked against a fresh scan of the record, and it has matched on every question of every input.

A forty-fifth of the reading #

On 1,024 keys in runs of four, the two registers read 0.024 words a question, against 1.094 for the record read on every question: a forty-fifth. On runs of sixteen keys they read 0.028 against 1.141, and on runs of 64 keys 0.097 against 1.90. Ninety-eight per cent of the sort’s questions on short runs are asked from a position whose register is valid, and read nothing.

The registers read more than the plain record only on a sorted array at this size, and nearly as much on runs of 512 keys, 5.37 words against 5.85. That is the failure the closing section named, and it is confined to the inputs where the run list is cheaper than either.

A price that stops growing #

With the registers the record spends 4.50 word reads for every comparison it saves on 1,024 keys in runs of four, against 201 without them, and 4.39 at 4,096 keys against 764. The price without registers grows fourfold with each fourfold growth of the input; with them it does not grow at all, 4.11, 4.50 and 4.39 at the three sizes. On runs of sixteen keys it is 1.62 to 1.67 at every size and on runs of 64 keys 1.45 to 2.00.

That puts the record below the line it had never come near. 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 operations. Read on every question, the record of adjacent order was fifteen to two hundred and forty times above that on short runs. With the registers it is under it on every input with runs of sixteen keys or more, and within a factor of one and a half of it on runs of four.

Both of the record’s costs at once #

The plain record had two ways of spending words, and the earlier essays found each in turn. A question it cannot answer costs the word holding its first pair, and on short runs that is nearly every question; the filter attacked that cost and found it was a floor. A question it can answer costs a word for every sixteen positions between $i$ and $j$, and on long runs that is the dominant cost, 1.90 words a question on runs of 64 keys at 1,024 keys, when the record answers only one question in sixteen. The registers remove both at once. A question from a valid register reads nothing whether it is answerable or not, and however far $j$ is from $i$, because the register already holds how far the run reaches and the answer is one comparison with it.

On runs of 64 keys that turns 1.90 words a question into 0.097, a twentieth, and on runs of 128 keys 2.77 into 0.29. The scan across an answer is still paid, but once a fill instead of once a question, and the sort asks a few hundred questions from each fill on these inputs.

None of this costs the record any memory, unlike the ring of a pass’s minima or a cache of compared pairs that forgets on purpose. The record is still 64 words of two bits a pair at 1,024 keys. The registers are four machine words beside the two positions the sort already keeps, and they hold nothing the record does not hold; they hold it in the one place the sort reads for nothing.

Why the price stops #

A register is filled about twelve times a scan of the sort on runs of four keys, at every size from 256 keys to 4,096, and the record saves about three comparisons a scan. Both numbers are flat in $n$. That is why the price stops growing: the questions grow with $n$, a scan asks about every key it passes, but the registers make the questions free, and what costs reads is filling them, which happens a fixed number of times a scan.

A register is filled when the extreme it describes moves, or when the record changes inside its run. The extreme of a random stretch moves about $\ln n$ times a scan, which grows, but slowly: from 256 to 4,096 keys $\ln n$ rises by half, and twelve fills a scan rise by about a thirtieth. So most fills are not moves of the extreme. By elimination they are changes inside a register’s run: a scan’s comparison of two neighbours that extends or breaks the short run next to an extreme, which happens at a rate set by the runs’ length, not by $n$. The registers do not record which kind of event refilled them, so that split is inferred rather than counted. Each fill reads about one word, since a run of four keys rarely crosses a word boundary, so the reading a scan costs about twelve words, and the savings a scan are three comparisons. The ratio is four, at every size.

The prediction said the reads would fall to about one word for every change of extreme, and that the extremes change about as often as the record saves a comparison. The first is right if a change of extreme is read as any change to what a register describes; the second is off by a factor of four, which is the price that results.

Where the registers stop holding #

On a sorted array of 1,024 keys no question is ever asked from a valid register, and the registers read 53.5 words a question against the plain record’s 22.1. The closing section’s named failure is exact. A sorted array is one run, every scan’s swaps at its two ends break that run, the break forgets the pairs around the swapped keys, and the next question from the new extreme refills a register by scanning the whole remaining run, $n/2$ positions on average, sixteen to a word. The plain record reads only as far as each question’s $j$.

The decline is gradual. At 1,024 keys the share of questions from a valid register is 96% on runs of 64 keys, 88% on runs of 256 and 74% on runs of 512; at 4,096 keys it stays above 90% up to runs of 1,024. A register fails when its run is long enough that a pass is likely to break it, and that depends on how long a run is relative to the part of the array still unsorted. Long runs at a large size are as safe as short runs at a small one, and the reverse holds too: at 256 keys the decline starts earlier, with 83% of questions from a valid register on runs of 64 keys and 70% on runs of 128, and on a sorted array of 256 keys the registers read 13.5 words a question against the plain record’s 6.1.

The cheapest record at every run length #

On 1,024 keys the registers are the cheapest way to consult the record on every input with runs shorter than 512 keys, and the run list on runs of 512 keys and a sorted array; a sort that picks between them pays at most 4.51 reads a question on any input measured. The plain record of two bits a pair, which what it costs to consult two bits a pair found the cheaper of its two candidates on every input short of runs of 512 keys, is never the cheapest of the three. The pass that finds the runs already counts them, and that essay showed the count is enough to choose between the bits and the list; the same count chooses between the registers and the list, at the same crossing, between runs of 256 and 512 keys at this size.

The three records hold the same information about adjacent order, and each pays for it differently. The list pays a search proportional to the logarithm of how many runs there are, the bits pay the distance from $i$ to the answer, and the registers pay for changes: a fill each time the extreme moves or its run is disturbed. On short runs, where changes are cheap and the questions are many, the registers win by forty-five times. On one long run that every pass breaks, changes are expensive, and the list’s two probes win.

What the prediction got right #

The closing section predicted that on runs of four keys the reading would fall to about one word for every change of extreme. It falls to 0.024 words a question at 1,024 keys, about twelve fills a scan of one word each. It predicted the price a saved comparison would fall from 185 to under ten at 1,024 keys and stop growing with $n$. It falls to 4.50, and it is 4.11, 4.50 and 4.39 at the three sizes. It named the failure on long runs, that each pass’s swaps break the register’s run and force a rescan of all of it, and on a sorted array that failure costs the registers two and a half times the plain record’s reading.

The question it asked was whether the cost of consulting a record belongs to the questions or to the moments when what the record knows about the question’s first position changes. On these inputs it belongs to the changes. The questions grow as $n^2$ and are free; the changes grow as $n$ and are what the reading costs.

What the counts assume #

Registers are free. A register holds a position and a run end, two machine words beside the extremes the sort already keeps, and reading it is charged nothing. On a real machine it is a comparison with a value already in a register, about the cost of the loop’s own bound check, and that is what the essay charges.

Words, not time. As on the earlier pages, a word read is one unit whether it is in cache or not, and nothing was timed.

Two registers. One for each extreme, the older evicted when a question comes from a third position. Questions from a third position are rare in this sort, since every question starts from a current extreme, and a sort with more registers would mostly keep runs nobody asks about again; no other number was run.

Runs of one length. The inputs are sorted runs of a fixed length with interleaved values. Inputs with a mix of long and short runs would sit between the curves here, since each register’s cost depends only on the run its extreme starts.

Still open: a register that survives the swap #

The registers fail on long runs for one reason: each scan’s swaps put the extremes at the two ends of the unsorted part, the record forgets the pairs around both swapped positions, and a register whose run passed through either position is dropped and refilled by a scan of the whole run. But a swap does not destroy what the record knew about the run beyond the swapped position. A run from $i$ to $k$ that loses its pair at position $p$ becomes two runs, one from $i$ to $p - 1$ and one from $p + 1$ to $k$, and the second is still known in full.

The measurement that follows keeps, when a swap breaks a register’s run, the part of the run on the far side of the break as a register in its own right, rather than dropping it, and charges the sort’s reads on the same inputs. The prediction is that on a sorted array the registers’ reading falls from 53.5 words a question at 1,024 keys to under the plain record’s 22.1, since each scan then rescans only the stretch near the swapped ends, and that nothing changes on short runs, where registers are almost never broken by a swap. It could fail on the extremes themselves. The new minimum after a swap is usually not inside a run the register kept, so the kept part may never be asked about before it is broken again. The question is whether a record can keep what a swap did not destroy cheaply enough to be worth keeping, or whether the run a register holds is only useful for as long as its extreme stays put.