The file is one draw too

A library merge sort handed a file that is sorted except for a late tenth sorts the tail a buffer at a time into pieces, and then has a choice: send each piece into the long sorted head, merge the pieces in pairwise rounds first and send the larger groups, or merge all the way down to one group. The head each piece will meet built a rule that prices every one of those choices before making any, from two tables measured once on synthetic inputs, and every number of rounds, priced found it within about 6% everywhere but the first round.

A table with one draw in each cell found why. The crossing table — what a sorted run of a given length costs to cross a head whose top $A$ keys it interleaves with — held one synthetic run in each cell, and a run of exactly twice the buffer crosses with a coefficient of variation of 0.21. With every cell the mean of sixteen draws, the first round came within 6% at every buffer, for the reach the strand had used throughout: a late tenth whose keys reach a fifth of the way into the head.

Two errors survived. Across five reaches and three buffers, the first round at a buffer of a 128th was still priced 14.7% high with the tail reaching 0.4 of the way in and 17.1% with it reaching 0.7. And with the tail reaching only a tenth of the way in, at a 1,024th, the last two rounds were priced 6% and 12% high whichever table was read, so the rule chose five rounds where six were cheapest. Since averaging had not moved them, the essay called them systematic and located them: groups crossing a head that was not the head a random run would face.

Its closing section proposed one more index for the table. The table is indexed by a run’s length and by $A$, and it assumes the run’s keys are spread at random through the band of head keys they meet. Measure how a group’s keys actually sit in that band — the share of them in the band’s upper half — and calibrate on synthetic runs drawn with that spread. It predicted the errors at a 128th would fall under 6% and the partway miss would be corrected. It named the way it could fail: if the spread is not the variable.

The spread there is to index #

Before building a table with another index, it is worth measuring whether the file’s groups have anything for it to index.

They sit at a half. A group’s band is the head keys above its smallest key, the keys of the groups that crossed before it and are now part of the head, and its own keys; the share of its keys at or above the band’s median is 49.9% on average for the seven groups at a 128th with the tail reaching 0.4, and 50.7% with it reaching 0.7. The two control settings read 49.9% and 49.8%. Across all 73 groups in the four settings the extremes are 41% and 59%, and those are the small groups at a 1,024th, whose share moves in steps of a sixty-fourth; the groups at a 128th all sit between 47% and 54%.

That is what the file’s construction says they should do. The tail’s keys are drawn at random from the top reach of the key range, so a piece of consecutive tail positions is a random subset, a merged pair of pieces is a random subset, and the head keys between them are the complement. Nothing in a late tail arranges a group’s keys against the head. A spread index would read a half for every group the rule prices, and a table indexed by a half is the table it already has.

So the proposal fails at its premise, and its prediction cannot be tested as stated: there is no table to build that differs from the one in use. The error that survived needs another explanation.

One file, drawn again #

Every estimate in the strand was checked against one file per reach: 65,536 keys, a sorted head, a late tenth drawn once. A table with one draw in each cell found that one synthetic draw of a run of twice the buffer varies by a fifth. A file is also a draw. At a 128th its first round produces seven groups, six of them runs of twice the buffer — exactly the length where a draw varies most.

Drawn eight times, the same file gives a first-round error anywhere from −7.4% to +23.5%. With the tail reaching 0.4 the eight files range from +2.6% to +23.5% and average +12.9%; the strand’s file read +14.7%, near the middle. With it reaching 0.7 they range from −7.4% to +17.1% and average +6.4%; the strand’s file, at +17.1%, is the highest of the eight. And with it reaching 0.2, the reach the strand had used throughout and where the first round looked solved, they range from −1.2% to +17.3% and average +4.9%: the strand’s file read −0.7%, which is the low end.

Two things follow, and they pull in different directions. The 17.1% at a reach of 0.7 was largely one file’s luck, and the “solved” first round at 0.2 was too, the other way. But the averages are not zero. At every reach the eight files’ mean error is positive — five to thirteen per cent high — and that is not a property of any one file. Something in the pricing overcharges a first round at a 128th on average, and it is not the arrangement of the groups.

What a straight line across a doubling costs #

The table is read between its cells. Its cells are at values of $A$ a doubling apart, from an eighth of the run’s length to sixty-four times it, and a group whose $A$ falls between two cells is priced by a straight line between them in $\log A$. That is only right if the cost is a straight line in $\log A$ across each doubling.

It bends. Between eight and sixty-four run lengths the cost of a run of 1,024 keys rises from 22 to 133 moves a run key, and not evenly: from 16 to 32 run lengths it climbs slowly and then steeply, so the straight line between those two cells lies above the curve by 17.5% at 23 run lengths and by 12% at 19. Across the three doublings drawn, the line lies above the curve at five of the nine points between cells.

The first round’s groups at a 128th land exactly there. At a reach of 0.4 their heads are 19 to 63 run lengths deep, most of them inside the doubling where the line overcharges most; at 0.7 they are 38 to 110 deep, where the next doubling bends less; at 0.2, 6 to 31. The ordering of the averages — 0.4 worst, then 0.7 and 0.2 — is consistent with how much of the bend each reach’s groups fall into, though eight files cannot separate the reaches’ averages finely enough to prove it.

Why the cost bends where it does is not measured here. A run longer than the buffer crosses by rotating blocks of keys into place, as the rotation that could be priced set out, and each rotation’s length is the stretch of head keys between where a block belongs and where it sits, so the cost depends on how the merge happens to split the run at each depth of head; a curve built from that need not be straight in any coordinate. What is measured is that it is not straight in $\log A$, and that a grid a doubling apart cannot follow it.

The table read three ways #

Two readings test the explanation. One keeps the table’s means but puts a cell every quarter of a doubling instead of every doubling, with a cell at $A = 0$ below the grid. The other prices each group from the mean of sixteen draws at its own $A$ — no reading between cells at all, which is the most a table of synthetic means could do.

Read at each group’s own $A$, the first round at a 128th averages +0.5%, +4.9% and +2.4% over the eight files at reaches of 0.2, 0.4 and 0.7, against +4.9%, +12.9% and +6.4% from the published grid; at a 256th with the tail reaching 0.4, +1.0% against +6.4%. The finer grid lands close to it: +0.9%, +1.8%, +8.5% and −1.8%. Most of what survived averaging was the reading.

The finer grid and the exact reading disagree with each other by up to six points, in both directions, and that is the size of what is left in the cells themselves. Each cell is the mean of sixteen draws of a quantity that varies by a fifth, so it is uncertain by about 5%, and a group priced between two such cells or at one inherits that. A table with one draw in each cell found sixteen draws brought the table to about 5.6%; a finer grid needs that many draws in every one of four times as many cells to keep the same accuracy, and gains nothing if it has them in fewer.

And the whiskers barely shrink. At a reach of 0.4 the eight files span 21 points from the published grid and 18 read exactly. The spread across files is not the table’s at all.

What one file can be priced to #

A first round at a 128th is seven groups, six of them runs of twice the buffer, each crossing with a cost whose draw-to-draw coefficient of variation is about 0.21. The table can at best price the expected crossing of each. The file pays the crossing its own groups actually happen to have, and the sum of seven independent draws with a coefficient of 0.21 varies by about $0.21/\sqrt{7}$, or 8%. The eight files’ errors read at each group’s own $A$ have a standard deviation of 7.2% at a reach of 0.4. The spread across files is the spread of the file’s own seven draws, to within what eight files can measure.

That changes what the strand’s target meant. Pricing every number of rounds “within 6%” on one file is a statement about the table and about that file together, and at a 128th the file’s own share of the error is about eight points either way. No table indexed by anything about the runs could meet 6% on every file there, because the cost it would have to predict is partly the outcome of the file’s random draw, which the rule cannot see before it pays. A result the size of its own noise is the general form: a measured difference smaller than the spread of the thing measured is not a difference, and here the thing measured was a single file standing for every file of its kind.

At smaller buffers the problem shrinks without help. At a 1,024th the first round is 52 groups and their sum’s coefficient of variation is about 3%; at a 4,096th, 205 groups. The first round at a 128th is the worst case for exactly the reason it was the worst case for the table: few groups, each at the length where one draw varies most.

The partway case #

The partway miss was the other error that survived, and it was never about draws.

With the tail reaching only a tenth of the way in, the tail’s keys are the top tenth of the key range and every head key lies below every tail key, so a group’s $A$ is only the keys of the groups that crossed before it. After seven rounds the one remaining group has none; after six, one of the two has none and the other a head under twice its length. A run that meets nothing is below the table’s smallest cell, an eighth of the run’s length. The published reading scales that smallest cell down in proportion to $A + t$, which assumes a run crossing nearly no head costs nearly as much per key as one crossing a head an eighth its length. It does not. Measured, the last round’s crossing is 0.09 moves a key; scaled from the smallest cell it was priced at 0.62.

Read at each group’s own $A$, every number of rounds is within 2.8% of its measured cost and the rule chooses six rounds, the cheapest. The finer grid, which carries a cell at $A = 0$, chooses six as well, every round within 2.8%. The miss was a table without a cell where the file’s last groups land — an edge, not an arrangement — and the earlier essay’s conclusion that it “sits in long groups” had the location right and the cause wrong.

What the bias was #

A table with one draw in each cell separated the first round’s error into noise and bias, and the noise half was right. The bias half was three things, none of them the arrangement it was attributed to:

• the reading — a straight line in $\log A$ across a doubling, which overprices the bend that the crossing’s rotations put between 16 and 32 run lengths, positively and systematically, at every reach whose groups land there;
• the edge — no cell below an eighth of the run’s length, so the groups that meet almost no head were priced by an extrapolation that charged them nearly seven times their cost;
• the file — one draw of seven runs of the most variable length, read as if it were the expectation.

The first two are fixable in the table, and the fix is to measure where the cost bends and where the groups land rather than on a grid chosen before either was known. Pieces that fit the buffer and the moves no stable sort can skip both found the library merge’s costs turn on thresholds; the curve here is one more, and a calibration grid has to be dense across it. The third is not fixable in any table, and it bounds what the rule’s estimates can promise on a single file: at a 128th, about eight points.

What was not measured #

Other file lengths and shapes. Every file is 65,536 keys with a late tenth whose keys are a uniform draw from the top reach. A tail whose keys were clustered would give the spread index something to read, and the earlier essay’s arrangement hypothesis a case where it might hold.

The finer grid with more draws. The grid four times finer was filled with sixteen draws a cell, the published table’s budget for a quarter of the cells. Whether sixty-four draws a cell on the finer grid reaches the exact reading’s accuracy everywhere is a calibration cost not measured.

Eight files. The spread across files is estimated from eight, so its standard deviation is itself uncertain by about a quarter.

A guarantee that depends on an allocation is the reminder that the buffer, which decides how many groups the first round makes and so how much of one file’s draw it averages away, is chosen by the library from the memory it is given.

Still open: a choice that knows its error bar #

The rule chooses the number of rounds with the cheapest estimate, and every estimate now has two known sources of error: the table’s cells, about 5% each, and the file’s own draw, about $0.21/\sqrt{g}$ for $g$ groups of the most variable length. Both are computable before the rule acts. A choice between two options whose estimates differ by less than their combined uncertainty is a choice the rule cannot actually make, and a rule that knew that could take the cheaper option to compute, or the one whose cost varies less.

The measurement that follows prices every number of rounds with an uncertainty from those two sources, on forty files — eight draws at each of five reaches — and seven buffers, and counts how often the rule’s choice is not the cheapest measured when the two best options are separated by more than their uncertainty, and how often when they are not. The prediction is that every wrong choice falls inside the uncertainty, and that among those the cost of being wrong is under 3% of the sort. It could fail where the two sources are not independent — where a file’s unlucky draw also lands its groups at the same bend in $A$, so its error and the table’s add rather than averaging. The question is whether a priced choice can say when it is guessing, or whether the only safe rule for a few large groups is the one whose cost does not depend on the draw.