What it costs to consult two bits a pair

The runs too short to drop settled what the two-ended selection sort should keep about adjacent order. The sort scans for the smallest and the largest key left and swaps them to the ends, and a pass repaid by the scans after it gave it one pass first: compare every key with the next and record which of each neighbouring pair is larger. A question about positions $i < j$ is then answered without a comparison whenever every pair from $i$ to $j - 1$ points the same way, because the keys are monotone across the stretch. The earlier page found that every run the pass leaves earns its place, even runs of two keys, and that the whole record fits in two bits a neighbouring pair — 64 words at 1,024 keys, a thirty-second of a list of runs at three words a run.

It counted both records as free to read, and its closing section said they are not equally cheap. A run list answers a question about $i$ and $j$ by finding the run that holds $i$, a binary search over its runs, and comparing that run’s end with $j$. A record of two bits a pair answers it by reading the pairs from $i$ to $j - 1$, sixteen to a 32-bit word, and checking they all point one way; it learns it cannot answer at the first pair that breaks the run. The proposal predicted that on random keys the bits read under two words a question and stay cheaper than the list at every size, that on sorted runs of sixteen keys or more the list wins, since there a question about two distant positions inside one run costs the bits a word for every sixteen keys between them, and asked whether the sort could choose between them from the run count the pass already finds.

Charging every question #

The sort is the earlier pages’ exactly: the two-ended selection sort with its pass between neighbours and its two chains of past minima and maxima, the chains consulted first, then the record of adjacent order. Every question the record is asked — whether it answers or not — is charged both ways. The bits are charged the words from the one holding the pair at $i$ to the one holding the last pair examined, which is the pair at $j - 1$ when the record answers and the first pair that breaks the run when it does not. The list is charged the probes of a binary search over the runs it holds at that moment, $\lceil \log_2(R + 1) \rceil$ for $R$ runs, plus one comparison when a run holds $i$. The sort and its answers are unchanged by the charging, and every answer is still checked against the keys.

The inputs are the earlier pages’ runs of a fixed length: a shuffle of the keys cut into pieces of $L$ keys, each piece sorted, so the input is $n/L$ ascending runs whose values interleave at random. Runs of four keys are close to random input — a random permutation’s ascending runs average two keys — and runs of $n$ keys are a sorted array.

The bits are cheap, and the list is not #

On runs of four keys the record of two bits a pair reads 1.09 words a question at 1,024 keys, and a binary search of the run list takes 8.80 steps; the list becomes the cheaper record only on runs of 512 keys, not sixteen. On runs of sixteen the bits read 1.14 words and the list takes 7.07 steps. The first prediction holds comfortably. The second misses by a factor of thirty-two.

The bits stay near one word because most questions are about two positions the record cannot connect, and it finds that out at once. The sort’s scans ask about the current minimum and every key after it, and on any input but a long run, the pairs leaving the minimum’s position turn within a few places. A turn inside the first word ends the read. The proposal’s picture — a word for every sixteen keys between the two positions — is right only for questions the record answers, and on runs of sixteen keys the record answers fewer than one question in fifty.

The list’s cost runs the other way. Its search depends on how many runs it holds, not on what is asked, and on short runs it holds many: 503 at most on runs of four keys, so every question costs nine probes whatever its answer. The list gets cheaper as runs lengthen because there are fewer of them, and the bits get dearer because the questions they answer span more words. They cross where a run is long enough that a typical answered question reads more words than the list’s search has probes, which at 1,024 keys is between 256 and 512 keys a run.

The pass makes the list dear #

On runs of four keys the bit record reads about one word a question at every size, 1.06, 1.09 and 1.07; the run list’s search grows with the runs it holds, and the pass is what makes them many — 10.78 steps at 4,096 keys with the pass, 5.33 without. Without the pass the sort learns adjacent order only when its scans happen to compare neighbours, and it never holds more than about two dozen runs. The pass orders every neighbouring pair at once and the list then holds every run of the input: half a run per key at four keys a run.

That is the earlier page’s finding about memory, repeated for time. The pass repays three quarters of its comparisons by leaving a record of 674 runs on random keys, and the runs too short to drop found that all of them earn their place. Kept as a list, every doubling of them costs every search one more probe. Kept as bits, they cost nothing more than the pairs they are made of. The representation that holds the pass’s record in a thirty-second of the memory is also the one whose reading does not grow with it.

Distance does not matter #

A question about two neighbours costs the bits one word, and a question about two positions 128 or more apart costs 1.10. Three quarters of all questions are about positions 64 or more apart, so the proposal’s worry — that a scan asks mostly about the current extreme and a key far from it, and the bits might pay for the distance — was right about the questions and wrong about the price. A far question costs the bits a long read only if the record can answer it, and on these inputs it almost never can: the pairs leaving the minimum’s position turn within its word.

The list’s cost rises a little with distance, 7.48 to 9.22 steps, most likely for a reason that has nothing to do with distance itself. Far questions are asked early in the sort, when the scan spans the whole array, and early in the sort the record holds the most runs; by the time the scans are short and their questions near, the swaps have broken runs and the record holds fewer. The plate does not separate the two.

Cheap reading is still reading #

Asked every question, the record costs more to read than it saves: on runs of four keys the bits spend 201 word reads for every comparison the record removes at 1,024 keys, and 764 at 4,096. The list, at the same inputs, spends 1,620 and 7,670 probes. Only on long runs does the price come down — 18.3 words a saved comparison on runs of 256 keys at 1,024 — and only a sorted array, where the list’s search over one run is two probes and every question is answered, brings it to 2.0.

This is the measurement that matters, and the proposal did not ask for it. A record is consulted on every question, because a sort cannot know which questions it can answer without asking. On runs of four keys it answers about one question in two hundred: at 1,024 keys it is asked 264,639 questions, answers 1,438 of them, and so saves 1,438 of the 264,639 comparisons the sort would otherwise make. One word read a question is a small price for each question and a large price for each answer.

The price falls as runs lengthen because answers become common, and the two records fall at different rates. At 1,024 keys the bits spend 66 words a saved comparison on runs of sixteen keys, 31 on runs of 64 and 18 on runs of 256; the list spends 411, 93 and 21. On a sorted array the order reverses: there the record answers 263,167 questions out of 264,190 and the bits must read every word between the two positions to do it, 22.2 words an answer, while the list’s one run makes each answer two probes. So the cheap record for the questions a random input asks is the dear one for the questions a sorted input asks, and the price a comparison must have before either pays spans three orders of magnitude across inputs that differ only in their run length.

The price of remembering an answer priced the plain selection sort’s table of compared pairs the same way, word operations against comparisons removed, and found it paid for itself once a comparison cost more than 3.1 word operations, at every size measured. That table removed half the sort’s comparisons, so its reading was spread over many answers. The run record removes a two-hundredth of this sort’s comparisons on random keys, so its reading is spread over almost none, and the price rises with size because the questions grow as the square of $n$ and the answers only in proportion to it: 385, 1,438 and 5,976 at the three sizes.

Memory and reading, counted together #

Every record this sort has kept has been priced twice on these pages, once in memory and once in work, and the two prices have usually pointed opposite ways. A run answers what nobody asked introduced the record of adjacent order because a run of a thousand keys could be held as one entry where the chains needed a link a key. The record measured where it would run found the plain sort’s table of compared pairs cheap in word operations and ruinous in cache misses, nearly two misses for every comparison it removed, because of where its entries sat. A record the size of a pass’s minima then kept twelve rows of that table and lost almost nothing.

Here the two prices point the same way. At 1,024 keys on runs of four the bits hold 64 words and read 1.09 of them a question; the list holds up to 503 runs at three words each, 1,509 words, and reads 8.8 of them a question, scattered across the whole structure by the binary search. The record that is smaller is also the one that reads less, and reads it from the word holding the question’s first position, which the scan has usually just touched. On these inputs there is no trade between the representations to make below runs of 512 keys: the bits win both ways.

The trade that remains is the one the price plate drew, between consulting and not consulting, and memory does not enter it. The record could be a single word and the price per saved comparison would be the same, because the price is set by how often the record is asked and how rarely it can answer.

Choosing after the pass #

The pass already counts the runs, so a sort can choose its record after the pass: using the list once the mean run reaches 512 keys — the crossing found at 1,024 keys, applied at 4,096 — costs the cheaper record on every input. Either record alone costs up to 43 or 10 times as much on some input. The crossing measured at a quarter of the size was the crossing at this size too, which is what makes a threshold read off one size worth applying at another: at both sizes the list wins once fewer than about one run in five hundred keys remains.

The same count answers the larger question. The pass finds $R$ runs among $n$ keys, and the plate before says how much reading a saved comparison costs at that mean run length. A sort that knows what its comparisons cost — a word operation for an integer, a string comparison for strings — can decide after the pass not only which record to keep but whether to consult one at all. With integer keys and random input, the answer is not to: every question asked of the record costs about what the comparison it might save costs, and it saves one in two hundred. With long runs, or with comparisons that cost a hundred word operations, it is to consult and to keep the list. A request that reads the input first chose a buffer from what one pass had seen; here one pass chooses a record and decides whether to read it, from the count it makes anyway.

What these inputs leave out #

One shape of input. Every input is ascending runs of equal length whose values interleave at random. Runs of mixed lengths, or descending runs, would put long and short runs in one array; the list’s search cost would follow their number and the bits’ cost the share of questions asked inside long ones.

Reads, not time. A word read and a probe of the search are both counted as one. The bits’ words are adjacent in memory, sixteen pairs to a word and many words to a cache line, and the list’s probes jump about a structure of three words a run; on a real machine the bits’ reads are cheaper than the count says and the list’s dearer.

One sort. Every number is the two-ended selection sort, whose scans ask about one extreme and every key after it. A sort whose questions are mostly about neighbours, as an insertion sort’s are, would ask the record questions it can answer far more often, and its price per saved comparison would fall with them.

Still open: a record consulted only where it can answer #

The record’s price is high because it is asked everything and answers almost nothing. But the record can say, before any word is read, where it has nothing to offer: a position whose pair to its right is unknown, or whose run ends at that position, cannot be the start of an answer. A sort could keep beside the record one bit a position, set when the pair at that position is known and the next one points the same way, and consult the record only when that bit is set at the question’s first position — a filter in front of the record, read from the same word.

That bit is a third of the record’s two bits a pair, and it is read in the same word, so it costs no extra read; what it saves is every question whose first position has no run to its right. The measurement that follows gives the sort that filter, and counts the questions it lets through, the words read, and the comparisons saved, on the same inputs. The prediction is that on runs of four keys the filter turns away about three quarters of the questions, since a run of four has a pair pointing the same way after only half its positions and the scans’ current extreme is usually at a turn, and that the price per saved comparison falls by about that factor, to under sixty words at 1,024 keys. It could fail on the extreme itself. The scans ask about the current minimum and every key after it, and if the minimum sits mid-run more often than a random position does, the filter will let through as many questions as before and save nothing. The question is whether a record can learn where it is useful from its own shape, or whether the questions a selection sort asks are, by their nature, about the places where order has just been broken.