A table with one draw in each cell

Every number of rounds, priced is the latest step in a strand about one practical decision inside the sort the library ships. Given a file that is sorted except for a late tenth, the library’s merge sort, working with a buffer of fixed size, sorts the tail a buffer’s worth at a time into pieces, and then either sends each piece into the long sorted head, merges the pieces in pairwise rounds first and sends the larger groups, or merges all the way to one group. The head each piece will meet built a rule that prices those choices before making any of them, from two tables measured once on synthetic inputs: what a round of merging random pieces costs, and what a sorted run of a given length costs to cross a head whose top $A$ keys it interleaves with.

The rule priced every number of rounds within about 6% of its measured cost — except one. The first round was priced 15.3% low at a buffer of a 256th, 14.7% high at a 1,024th and 25.1% low at a 4,096th. The rule survived it, because one round was never close to the cheapest, but an estimate that is wrong by a quarter in a direction that changes from one buffer to the next is not one a rule should be built on.

That essay’s explanation was that the first round is where the table’s assumption is least true. A group after one round is two pieces merged into a run of twice the buffer, the first size too long to be merged inside the buffer, so it crosses the head by rotation, the dearest and most variable move the library merge makes. Its closing section proposed calibrating exactly that: a second table made of two sorted pieces of a buffer each, merged into a run of twice the buffer, crossing a head at each $A$. It predicted the first round’s error would fall under 6%. And it named the alternative: that the error was about where the file’s groups sit relative to the head, which no synthetic table can know.

Which half of the first round is wrong #

A round’s price has two parts: the round’s own merging, priced from a measured merge of random pieces, and the resulting groups’ crossing of the head, priced from the crossing table. Before building any new table it is worth knowing which part carries the error.

The round’s own merge is priced to within a thousandth of a move a key at all three buffers: 0.149 priced against 0.149 measured at a 256th, 0.147 against 0.147 at a 1,024th, 0.139 against 0.140 at a 4,096th. The whole of the error is the crossing. At a 4,096th the groups’ crossing is priced at 48.9 moves a key and measured at 65.4, of which 37.2 is rotation; at a 1,024th it is priced at 21.0 and measured at 18.2.

So the question is entirely about the crossing table, and about how it prices a run of twice the buffer.

The pair table, built as proposed #

The proposal’s table draws, for each $A$, the keys a run will hold and the head it will cross; sorts two pieces of a buffer each; merges them with the library merge into one run; and then counts the moves of that run crossing the head. Only the crossing is counted, since the pair’s own merge is the round’s cost and already priced exactly.

Priced from the pair table, the first round’s error at the three smallest buffers is −4.5%, −24.1% and −21.8%. At a 256th it improved; at a 1,024th it went from 14.7% high to 24.1% low; at a 4,096th it barely moved. The prediction fails, and not by a small amount.

The reason is visible in what the pair table’s run is. Two sorted pieces of random keys, merged, are a sorted run of twice the buffer of random keys — exactly the object the published table already draws when it prices a run of that length. A merge does not leave a mark on the keys it merged. The pair table could only ever differ from the published one by being another draw of the same random experiment, and that is what it is: a different seed, a different answer, an error of the same size in a different direction.

That points at the explanation neither the essay nor its proposal considered. Every cell of the published table is one synthetic run. If one run’s crossing varies a lot from draw to draw, the table’s cells are wrong by about that much, in directions that change from cell to cell, and an estimate read from them inherits it.

How much one draw varies #

It varies a great deal, and at exactly the run length the first round produces. A run of one buffer crosses the head with a coefficient of variation of 0.00 to 0.03 across sixteen draws: it fits in the buffer, the merge is a sequence of shifts, and its cost is close to a function of $A$. A run of twice the buffer varies with a coefficient of 0.20 to 0.22. A run of four buffers is at 0.08 to 0.11, eight at 0.04 to 0.05, and thirty-two at 0.01.

The worst buffer shows what that does to a price. At a 4,096th the published table’s cells for a run of two buffers, at $A$ of one, eight and sixty-four times the run’s length, hold 0.98, 1.18 and 0.74 of their own sixteen-draw means. A price read by interpolating between cells like those can land anywhere in a band a fifth either side of the truth, and the first round’s price there landed a quarter low. Nothing systematic was being priced in that cell; a few unlucky draws were, and the rule read them as the cost of a pair.

The shape is what the library merge’s own mechanism predicts. A run longer than the buffer cannot be merged by shifting through the buffer, so the merge splits the work and rotates blocks of keys into place, and each rotation’s length depends on where the run’s keys happen to fall among the head’s. A run of exactly two buffers is cut into the fewest pieces, so its cost is decided by one or two rotations whose lengths are whatever the draw made them. A run of thirty-two buffers is cut into many, and many rotations average out. The variance is not a property of pairs. It is a property of runs that have only just become too long for the buffer.

At a buffer of a 1,024th the sixteen draws of a run of two buffers crossing its head range from 0.75 to 1.33 times their mean, and the published table’s draw at that cell is 0.89. Runs of one buffer stay within 0.96 to 1.02, and runs of eight within 0.95 to 1.13. A table holding one draw from a spread of 0.75 to 1.33 is a table that is right to about a fifth, and that is the size of error the first round showed.

Nothing about the file was involved. The alternative the proposal named — that the groups’ position relative to the head was being mispriced — would have needed an error that averaging synthetic runs could not remove. Averaging removes it.

A table of means #

With every cell the mean of sixteen draws, the first round is priced −0.2%, −4.5% and +1.6% off at the three smallest buffers, and every number of rounds at every buffer is within 5.6% of its measured cost, against 25.1% for the published table. The first round is no longer the outlier; the largest remaining error is no rounds at all at a 4,096th, −5.6%, where 410 pieces of sixteen keys each are priced one at a time and a small bias in the smallest runs’ cells adds up.

The rule’s choices do not change. At every one of the seven buffers it picks the same number of rounds from the mean table as from the published one, and both are the cheapest measured: none from a 16th to a 128th, all from a 256th down. That half of the proposal’s prediction held exactly, for the reason it gave: the first round was never close to the cheapest, so pricing it better changes no choice.

The size of what remains is about what sixteen draws should leave. A cell whose single draw varies with a coefficient of 0.21 has a mean of sixteen draws that varies with about a quarter of that, 0.05, and the worst error left anywhere in the plate is 5.6%. The table is now as good as its sample size, and the sample size is now the thing to choose: halving the remaining error would take sixty-four draws a cell, and the cells where a draw barely varies — runs of one buffer, runs of sixteen or more — would gain nothing from any of them.

A sixteenfold table costs sixteen times as much to build, once. The table is measured on synthetic inputs before any file is sorted, so the cost is paid at calibration and not per sort; the rule reads the same number of cells either way.

Across reaches #

The main input’s late tail reaches a fifth of the way into the head’s keys. The earlier essay also ran four other reaches, and the one partway optimum it found was at the shortest.

From the published table the first round is within 6% in only 2 of the 15 settings; from the mean table, in 13. The errors that survive the averaging are systematic. At a buffer of a 128th the first round is priced 17.1% high with the tail reaching 0.7 of the way in and 14.7% high at 0.4. No number of draws changes those, because they are not draws: at that buffer and those reaches the pairs’ actual crossing differs from what a random run of the same length and the same $A$ costs, which is the alternative the proposal named, present after all, but smaller and in fewer places than the first round’s error suggested.

The partway miss survives too. With the tail reaching a tenth of the way in, at a 1,024th, six rounds of seven are cheapest and the rule chooses five from either table, because the last two rounds are priced 6% and 12% high whichever table is read. That error was never noise: it sits in long groups, where one draw varies by a per cent or two, and it is the same systematic mispricing of groups that barely reach into a head, now isolated from the noise that had been lying on top of the first round.

Two errors that looked like one #

The first round had looked like one error with one cause. It was two.

The larger part was noise: a calibration table with one draw a cell, at the one run length where a draw varies by a fifth. It changed sign between buffers because each buffer’s cells were different draws, it was largest at the first round because that is where variance peaks, and it disappears under averaging. The pair table could not touch it, because the pair table is the same random experiment drawn again.

The smaller part is bias: places where the file’s groups cross the head differently from a random run with the same length and the same count of head keys above its smallest. It appears at a buffer of a 128th with the tail reaching far into the head, and at the long final rounds of a tail that barely reaches in. It survives averaging because it is not about the draw but about the arrangement, and a synthetic table indexed by length and $A$ alone does not know the arrangement.

A result the size of its own noise is the general version of the first half: a difference smaller than the spread of the thing being measured is not a difference, and here the spread was hiding inside a calibration rather than inside a result. The earlier essay compared estimates to measurements to the tenth of a per cent and never asked how much its own table would move if it were measured again.

What a calibration table owes #

The habit this strand has followed since the rotation that could be priced is to price a decision from measurements of the operation itself rather than from a model of it. That habit is right, and it carries an obligation the strand had not met: a measured table is an estimate, and its cells need error bars. A cell measured once is one sample of a quantity whose spread the table does not record; where the spread is small — runs that fit the buffer, runs of many buffers — one sample is enough, and where it is a fifth, one sample produces a rule whose estimates are wrong by a fifth for reasons nobody can see in the rule.

The fix measured here is crude: the same number of draws in every cell. A table could spend its draws where the spread is, many at twice the buffer and one at thirty-two times, and reach the same accuracy for a fraction of the cost. Pieces that fit the buffer and the moves no stable sort can skip both found that the library merge’s costs turn on a few structural thresholds; the variance plate says the same about its predictability, which changes abruptly at the threshold where a run stops fitting.

What was not measured #

The bias’s cause. The systematic errors at a 128th and at the long final rounds are located and sized, not explained. Both involve groups whose keys’ positions among the head’s are far from what a random run would have: at long reaches the tail’s later groups face a head already enlarged by earlier groups, and at short reaches the final groups are long against a narrow band of head keys.

Other file lengths. Every number is for a file of 65,536 keys with a late tenth, as in the earlier essays.

Comparisons. Every cost is moves of keys, as the library merge counts them.

A guarantee that depends on an allocation is the reminder that the buffer, which decides where every threshold above falls, is chosen by the library from the memory it is given and not from the input.

Still open: the arrangement a table cannot see #

The bias that survived is in two places, and both are groups crossing a head that is not the head a random run would face: at long reaches, a head enlarged by groups merged before; at short reaches, long groups against a narrow band of head keys. The crossing table is indexed by a run’s length and the count of head keys above its smallest key, and it assumes the run’s keys are spread at random through that band.

The measurement that follows adds one index to the table: how the run’s keys are spread through the band — the share of them in the band’s upper half — measured on the file’s own groups by the same binary searches the rule already makes, and calibrated on synthetic runs drawn with that spread. The prediction is that the systematic errors at a 128th fall from 14.7% and 17.1% to under 6%, and that the partway miss is corrected, since the last two rounds’ groups are the ones whose keys crowd the top of a narrow band. It could fail if the spread is not the variable — if what matters is how the run’s keys clump between individual head keys, which one share cannot describe. The question is whether a cost that depends on arrangement can be priced from one more number about the arrangement, or whether the only faithful calibration of a run is the run.