A record switched off by its runs

The two-ended selection sort finds the smallest and largest of the unsorted part on every scan, and a run of essays has taught it to remember. Its record holds two bits for every neighbouring pair — unknown, or known in one direction — and a question whose two keys lie at the ends of a stretch of pairs all pointing one way can be answered from the record instead of by a comparison. What it costs to consult two bits a pair priced the reading. A run end kept in a register kept, beside each of the sort’s two extremes, where the run of known order from it ends, so most questions read one word instead of a stretch of the record. A register dropped by what it already knew found that the registers were dropped mostly by confirmations, writes that left a pair’s value unchanged.

A register kept through a confirmation kept them through those writes, and the reading collapsed: 0.347 words a question on a sorted array of 1,024 keys, a 154th of what it had been, flat in $n$. The registers became the cheapest way of consulting the record at every run length. The price of a comparison saved — word reads spent for each comparison the record makes unnecessary — then fell steadily with run length, from 3.97 at runs of four to 0.35 at runs of 1,024.

Which left one place where the record cannot pay. On runs of four it saves 1,438 comparisons on 1,024 keys and the registers read 5,703 words to do it, about four words for each; if a word read costs less than a quarter of a comparison the record still pays, and if it costs more the sort would be better off asking every question by comparing. That essay’s closing section proposed letting the sort decide. The pass between neighbours, which the sort makes before its first scan, already counts the runs. A sort could read the mean run length off it, $n$ over the runs found, and keep the record only when that mean is at least some threshold. The prediction was that at an exchange rate of three word reads a comparison the cheapest threshold would be a mean of six keys, switching off the record on runs of four and keeping it from runs of eight. The risk named was uneven runs: a mean of four can hide a few long runs, where the record saves most of what it saves.

Two sorts of every input #

Each input is sorted twice. Once as the earlier essay sorted it — the pass, the chains, the record kept and consulted through quiet registers — counting comparisons and the words the registers read. Once with no record at all, the pass and the chains only, counting comparisons. The difference in comparisons is what the record saves; the words are what it costs. A sort’s cost at an exchange rate of $\rho$ word reads a comparison is its comparisons times $\rho$, plus its word reads if the record is kept.

The inputs are 1,024 keys in even runs of 2, 4, 8, 16, 32, 64 and 256 — the earlier essays’ inputs — and five uneven ones that the earlier essays did not measure: half the keys in runs of one length and half in runs of another, the pieces in a random order, each piece sorted. Runs of two and 64, of four and 256, of two and 512, of eight and 128, and of four and 32. The switch sees only the pass’s count of runs, and takes the record or leaves it.

The price of a saving, by run length #

On 1,024 keys in even runs, the record reads 5.20, 3.97, 2.28, 1.24, 0.74, 0.46 and 0.25 words for every comparison it saves at runs of 2, 4, 8, 16, 32, 64 and 256: at three word reads a comparison it pays from runs of eight up and not at four, and at one read a comparison only from 32. The plate is the earlier essay’s last curve, extended down to runs of two, with the rates drawn across it. Below a line the record pays at that rate; above it, the sort would do better to compare. At three reads a comparison the crossing falls between four and eight, which is where the proposal put its threshold of six.

The curve is steep at the short end for a reason worth stating. The registers’ reading hardly changes with run length — between 5,700 and 5,800 words on every input from runs of two to runs of sixteen — because the questions are the sort’s and the registers answer each in a word or so. What changes is how many of those questions the record can answer: on runs of two almost none, on runs of 256 most. The price is a fixed cost divided by a saving that grows with the runs.

What a mean can see #

At three word reads a comparison, inputs with half their keys in long runs read a mean of 4.90 and 4.41 keys off the pass — below the threshold of six — while the record saves them 67,387 and 7,683 comparisons’ worth, where even runs of four, at a mean of 4.05, lose 463. The named risk is the case, and by a wide margin. An input of 512 keys in runs of two and 512 in a run of 512 has 257 pieces, 256 of them short, and the pass, which cannot see a boundary between two pieces that happen to join, finds 209 runs: a mean under five. the record saves it 73,871 comparisons, nearly all in the long half, for 19,453 word reads. A switch that reads the mean sees runs of five and turns the record off.

The mean is the wrong statistic for a reason the plate makes visible. The record’s value on a run grows faster than the run’s length — a run of $L$ keys lets the sort answer questions spanning up to $L$ pairs, and a long run is consulted by many scans — while the mean counts every run once whatever its length. Two hundred and fifty-six short runs outvote one long one in the mean, and in the record’s ledger the one long run is worth all of them many times over.

Every threshold #

At three word reads a comparison the cheapest threshold on even runs is a mean of six, as predicted, and it is worth 0.3% of a sort at most; with the uneven inputs added, every threshold from six up costs as much as 30.9% on one of them, and the cheapest is three. The prediction holds exactly where it was made, and what it buys there is almost nothing. The record on runs of four costs 463 comparisons’ worth that the switch at six saves — against a sort of 264,000 comparisons, three in two thousand. The proposal had expected runs of four to “gain about a fifth of their cost back”, and a fifth is right only of the record’s own reading; of the sort, the record was never more than a few thousandths either way on short runs.

The asymmetry is the plate’s real content. A threshold set too low keeps the record where it does not pay, and on these inputs that costs at most 0.3%, because a record that does not pay still saves most of what it reads. A threshold set too high switches the record off where it pays, and that costs up to 31%, because a record that pays on long runs saves comparisons by the tens of thousands. A switch with a cost like that should err low, and over every input measured it does: the best threshold is three, which turns the record off only for runs of two.

The threshold by exchange rate #

The cheapest threshold by exchange rate: on even runs 12, 12, 6 and 3 at one to four word reads a comparison, falling as comparisons get dearer; over every input 3, 3, 3 and 3 — the uneven inputs pin it at the bottom, where the record is kept for everything but runs of two. On even runs the threshold moves with the rate as it should: the dearer a comparison, the shorter the runs at which saving one pays for the reading, so the threshold falls from twelve to three. That is the behaviour the proposal described, and if every input were even the switch would be a sound rule.

Over every input the threshold does not move at all. At every rate the uneven inputs with long halves sit below any threshold above three, and switching the record off on them costs more than every even input together could save. The only threshold safe for them is one that never switches the record off on an input that has long runs, and with a mean that means never switching it off unless the runs are nearly all of length two.

Where the uneven inputs stand #

On an input of half runs of two and half of 512, whose pass reads a mean of 4.90, switching the record off costs 30.9%: 73,871 comparisons saved for 19,453 word reads — the long half pays for itself many times over and the mean cannot see it. The plate makes the numbers in the previous plates concrete. Every uneven input is cheaper with the record, by between 1.1% and 31%, including the one whose short half is runs of two, where on its own the record does not pay. The long half makes the decision for the whole input, and it makes it by a margin the short half cannot reverse.

That is a statement about where the record’s value comes from. The runs too short to drop asked which runs a record should keep, on random keys, and found that runs of two answer half of everything the record answers there — on random keys short runs are all there is. Here the question is which inputs a record should be kept for, and on an input that has long runs the answer is set by them: what the record costs is roughly fixed, what it saves is concentrated in the long runs, and a decision made from an average spreads the long runs’ saving over the short ones’ count.

How small the stake on even runs is #

The plates about even runs read at first as a success for the proposal and are, looked at closely, a measure of how far the record has come. A filter that reads the word it saves began from a record that spent 201 word reads for every comparison it saved on short runs, because it was asked everything and could answer almost nothing; at that price a switch that turned the record off on short runs would have saved most of the sort’s reading. Several essays later the registers spend four words for each comparison saved on runs of four. The record no longer has a bad case worth switching off.

That is why the best threshold on even runs is worth three thousandths of a sort. The registers read about 5,700 words on 1,024 keys whatever the runs, against comparisons in the hundreds of thousands, so even on runs of two — where the record saves 1,115 comparisons and reads 5,801 words — keeping it costs under a fifth of a per cent at three reads a comparison. A switch exists to avoid a cost, and on even runs the cost has been engineered nearly away. The comparison that matters is no longer between the record and no record on short runs; it is between a cheap mistake and an expensive one, and the uneven inputs are where the expensive one lives.

The record that forgets on purpose met the same asymmetry in a cache of compared pairs. Forgetting a pair that would have been asked again costs a comparison; remembering one that would not costs a few bits. A record built cheaply enough is worth keeping everywhere, and the work of deciding where not to keep it is only worth doing where it is dear.

What the pass could read instead #

The pass between neighbours sees every run, not only their number. It can count, at no extra comparisons, the keys that lie in runs of at least some length, or record the length of the longest run, or keep a small histogram of run lengths in powers of two. Any of those would see the long half of an uneven input. A record the size of a pass’s minima found the same concentration in a different record, the table of compared pairs: twelve of its 1,024 rows caught 99% of what the whole table saved. A record’s value tends to sit in a small part of it, and a summary that finds that part can be small.

The price of remembering an answer set out the general accounting every record here has been held to — a remembered answer is worth what it saves in comparisons less what it costs in reading, at an exchange rate the machine sets. This essay adds that the accounting has to be done per run, or at least by kind of run, because the per-input average is dominated by the many runs that matter least.

What the sorts do not cover #

One size. 1,024 keys. The earlier essay found the registers’ reading flat in $n$, so the record’s price at a given run length should not move much with size, but the uneven inputs were not run at other sizes.

Two run lengths at most. Every uneven input has two kinds of run. An input with a continuous spread of lengths would test whether a threshold on the keys in long runs needs one length or several.

Even halves. Every uneven input splits its keys half and half. An input with a tenth of its keys in long runs would sit closer to the boundary, and is where a switch reading the long runs’ share would be tested hardest.

Still open: a switch that reads the long runs #

The plates say the record’s value on an input lives in its long runs and a mean cannot see them. The pass can. Let it count, as it goes, the keys that lie in runs of at least some length $L^\ast$, and keep the record when that share is at least a threshold — so that half the keys in runs of 512 keep it whatever the other half looks like, and an even input of runs of four, with no keys in long runs, drops it.

The measurement that follows sets $L^\ast$ at eight and sixteen, sweeps the share from a hundredth to a half, and adds inputs with a tenth and a quarter of their keys in long runs to the ones here, at the same four exchange rates. The prediction is that at three word reads a comparison a switch with $L^\ast = 8$ and a share of a tenth keeps the record on every uneven input and drops it on even runs of two and four, so that its worst cost over every input falls from 0.2% at the mean’s best threshold to under 0.05%, and that it is right at every rate. It could fail on inputs where the long runs are long but few — a single run of 64 among a thousand runs of one — where the share is small and the record still pays. The question is whether one more number from the pass, chosen for what the record is worth rather than for what is easy to count, is enough to decide, or whether the decision belongs to each run rather than to the input.