What the libraries do

A choice that knows its error bar

A rule that prices every number of merging rounds for a library merge sort's late tail was given an error bar on every estimate, built from the spread of its calibration table's draws, and run on 280 sorts. It was predicted that every wrong choice would fall inside the bars, and that a wrong choice would cost under 3% of the sort. The second half holds: 30 choices were wrong, the worst cost 2.1%, and the average over all 280 is 0.14%. The first half fails five times, all at one buffer and one reach, where the bars were near zero and the estimates of two options differed by six moves. They were not guesses the rule failed to flag. They were a step in the cost that the table reads as a ramp, and a bar built from draws cannot see an error that every draw shares.

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 decides how many pairwise rounds of merging to run among the pieces before the groups that result cross the long sorted head. Every number of rounds, priced built a rule that prices each of those options from tables measured once on synthetic runs and takes the cheapest. The file is one draw too then found that two kinds of error remain once the table is read well. Each cell of the crossing table is the mean of sixteen draws of a cost that varies from draw to draw, so the cell is uncertain by that spread over four. And the file being sorted is itself a draw: each of its groups crosses the head at whatever cost its own keys happen to produce, and at a buffer of a 128th that alone puts about eight points either way on one file’s first round.

Both are computable before the sort moves a key. The rule already knows each group’s length and how many head keys sit above its smallest key; the same cells that give it a mean can give it the spread of their sixteen draws. That essay’s closing section proposed using them: price every number of rounds with an uncertainty, and ask whether the rule can tell when its choice is a guess. It predicted that every wrong choice would fall inside the uncertainty, and that where the rule did guess wrong it would cost under 3% of the sort. It named the way it could fail: if the two sources of error are not independent, so that one adds to the other instead of averaging.

A bar on every estimate

Each option is priced as the sum of three things: sorting the pieces, which every option pays alike; the rounds of merging, which a table with one draw in each cell found priced to within a thousandth of a move a key; and each group’s crossing of the head, read from the table at a cell every quarter of a doubling of the head keys it meets. Only the last part is uncertain. For each group the table supplies the standard deviation of its sixteen draws at the same cell, read between cells the same way the mean is. The file’s share of the bar is the square root of the sum of the groups’ variances, since each group is one draw; the table’s share is that divided by four, since each cell averages sixteen; and the two are added as independent.

One file, its late tenth reaching 0.7 of the way in, at a buffer of 1/32: the rule chooses 2 rounds, priced at 3.98 moves a key with a bar of ±0.006, but the cheapest measured is 1 round at 3.89, priced 4.33 ±0.61 — 1.15 of their combined bars apart, a choice the bars mark as a guessEvery number of rounds on one file of 65,536 keys whose late tenth reaches 0.7 of the way into the head, buffer 1/32. Each estimate is drawn with a bar of one and two standard deviations, from the spread of the table's sixteen draws at each group's cell, the file's draw and the table's mean together. 0 rounds (4 groups): measured 4.161, estimate 4.167 ± 0.001; 1 rounds (2 groups): measured 3.889, estimate 4.326 ± 0.303; 2 rounds (1 group): measured 3.970, estimate 3.978 ± 0.003. Chosen: 2; cheapest measured: 1.44.505012rounds of merging before the groups cross the headmoves a key, whole sortmeasuredestimate, ±1 and ±2 barsringed: cheapest measuredand the rule's choicereach 0.7 · buffer 1/32 · file 01.15 bars apart
Fig. 1 One file, its late tenth reaching 0.7 of the way into the head, at a buffer of a 32nd: every number of rounds, measured (left) and estimated with bars of one and two standard deviations (right). The rule’s choice and the cheapest measured are ringed.

One sort shows what the bars are for. With the tail reaching 0.7 of the way into the head and a buffer of a 32nd of the file, there are three options. No rounds sends four pieces, each small enough to fit the buffer, into the head; its estimate is 4.167 moves a key against 4.161 measured, and its bar is a thousandth of a move, because a run that fits the buffer crosses by being copied out and merged back without a single rotation, as pieces that fit the buffer found, and that costs nearly the same on every draw. Two rounds sends one group of all the tail’s keys, and its bar is three thousandths. One round sends two groups each twice the buffer, which cross partly by rotation; its estimate is 4.33 with a bar of 0.30, and it is the cheapest of the three at 3.89.

The rule took two rounds, at 3.98, which costs 2.1% more than one round would have. But the bars said it might. The estimate it rejected, one round, sat 1.15 of the two options’ combined bars above the one it chose, so a reader of the bars would have called the choice a coin toss rather than a decision. That is exactly the case the proposal meant: a wrong choice that its own uncertainty predicts.

Which choices were guesses

The measurement runs the rule on eight files drawn independently at each of five reaches — a tenth, a fifth, 0.4, 0.7 and all the way into the head — and seven buffers, from a 16th of the file to a 4,096th: 280 sorts of 65,536 keys, with every number of rounds measured on each. For each sort, the choice’s separation is how far the nearest other option’s estimate stands above it, in units of their combined bars. The nearest is not always the runner-up: in the sort above, the runner-up by estimate was no rounds, separated by 57 bars, while one round, third by estimate, was the true cheapest and the one inside the bars.

280 sorts — eight files at each of five reaches and seven buffers — placed by how far the rule's choice stood from every other option in units of their combined bars: 51 stood within two bars and 25 of those were wrong; 229 stood farther and five were wrong, every one at the table's edge; no wrong choice cost more than 2.1% of the sortFor each sort, the separation between the cheapest estimate and the nearest other option, divided by the square root of the sum of their variances (log scale), against how much more the chosen number of rounds cost than the cheapest measured, as a share of the sort. Right choices sit on the zero line. Close (within 2 bars): 51 sorts, 25 wrong, worst 2.1%. Separated: 229 sorts, 5 wrong (reach 0.1, buffer 1/16, file 0, 2.72 bars, 1.99%; reach 0.1, buffer 1/16, file 3, 2.72 bars, 1.85%; reach 0.1, buffer 1/16, file 4, 2.01 bars, 1.47%; reach 0.1, buffer 1/16, file 6, 2.28 bars, 1.68%; reach 0.1, buffer 1/16, file 7, 3.16 bars, 1.98%). Mean cost of the rule's choices over all 280: 0.14%.0.0%0.5%1.0%1.5%2.0%2.5%0.11101001000≥10⁴within 2 bars: 51 sorts, 25 wrongfarther: 229 sorts, 5 wrongseparation of the choice from the nearest other option, in combined bars (log scale)cost of the choice over the cheapest measured, share of the sortringed: the bars said certain
Fig. 2 Every sort placed by the separation of the rule’s choice from the nearest other option (log scale) and by how much more the choice cost than the cheapest measured. Right choices sit on the zero line; wrong ones inside two bars are in one colour and outside in another, ringed.

Of the 280 sorts, 51 stood within two bars of an alternative and 229 stood farther. Thirty choices were wrong. Twenty-five of them were among the 51 close ones, and in every one of those 25 the true cheapest option was among the options the bars could not separate from the choice. So the bars sort the sorts into two kinds that behave very differently: a close choice was wrong about half the time, 25 of 51, and a separated one was wrong five times in 229.

The wrong choices also share a shape. In 272 of the 280 sorts the rule chose an end — no rounds, or every round down to one group — and in 22 of the 30 wrong ones the cheapest was a number of rounds partway between. A partway option leaves a few large groups that cross by rotation, which are the options with the widest bars and, as a table with one draw in each cell found of the first round, the ones the table had overpriced before. The bars place them correctly as uncertain; they cannot say which way the error runs.

That much is the prediction holding. The five wrong choices outside the bars are where it does not, and they are not scattered. All five are files whose tail reaches only a tenth of the way in, at the largest buffer measured, a 16th of the file. The three other files at that setting were wrong as well, just with separations under two. Every file at one setting chose wrong, and the bars called most of them certain.

Five sorts the bars called certain

At that setting the two options are no rounds, sending two pieces into the head, and one round, sending one group of all 6,553 tail keys. The rule priced them at 1.6493 and 1.6492 moves a key, a difference of six moves in a sort of more than a hundred thousand. Their bars were three hundred-thousandths of a move and smaller, so six moves was more than two bars. The sorts cost 1.706 and 1.740: the estimates were 3.3% and 5.2% low, and the order between them was wrong.

The reason is in which head keys the groups meet. A tail reaching a tenth of the way in is made of exactly the file’s top tenth of keys, in random order, so every tail key is larger than every head key. But the sort does not know where the tail begins. It finds the head by its first descent, and the tail’s first key, being larger than everything before it, continues the ascent and joins the head. So the head ends in one key from the tail, sitting somewhere in the tail’s range, and on two of the eight files in two. Almost every group’s smallest key is below that key, so almost every group crosses a head with exactly one key above it.

A run of 2,457 keys that fits a buffer of 4,096, crossing a head whose top few keys it meets: with none above it the crossing is free, with one it costs 0.46 moves a key and with eight 0.90, while the table, reading a straight line from its cell at none to its cell at 307, prices one key at 0.004 — a step the table draws as a rampMean moves of sixteen draws for a run of 2457 keys crossing a head at a buffer of 4096, at small numbers of head keys above its smallest, against the fine table's reading there, a straight line between its cell at A = 0 and its first grid cell at A = 307: A 0: measured 0.000, read 0.000; A 1: measured 0.459, read 0.004; A 2: measured 0.702, read 0.008; A 3: measured 0.754, read 0.012; A 4: measured 0.801, read 0.016; A 6: measured 0.884, read 0.024; A 8: measured 0.905, read 0.032; A 12: measured 0.927, read 0.049; A 16: measured 0.953, read 0.065; A 24: measured 0.984, read 0.097; A 32: measured 0.976, read 0.130; A 48: measured 1.020, read 0.195; A 64: measured 1.035, read 0.260; A 96: measured 1.066, read 0.390; A 128: measured 1.096, read 0.520; A 192: measured 1.148, read 0.780; A 256: measured 1.204, read 1.040; A 307: measured 1.247, read 1.247.00.5001head keys above the run's smallest (log scale of one more)moves a run key to cross0137153163127255measured, mean of 16the table's readingrun 2,457 · buffer 4,096 · ringed: one key abovecells at 0 and 307
Fig. 3 A run of 2,457 keys at a buffer of 4,096, crossing a head with a few keys above its smallest: the mean cost of sixteen draws at each, against the table’s reading there, a straight line between its cell at no head keys and its first cell at 307. The ringed point is one key above.

The table has a cell at no head keys, which the file is one draw too added after the last groups of a short reach were found to cost far less than the smallest cell suggested, and its next cell is at an eighth of the run’s length. Between them it reads a straight line. The cost is not a line. A run of 2,457 keys that fits the buffer costs nothing to cross a head with no keys above it, because nothing moves; with one key above it, it is copied out and that key moved past it, at 0.46 moves a run key on average; with eight, 0.90; and from there it climbs slowly to 1.25 at the first cell. The line reads one key above as 0.004. The single group of the one-round option, longer than the buffer, does the same thing by rotation: 5,971 moves to cross one key, priced at 10.

So both options were priced far too low, by amounts that had nothing to do with any draw. The bars were near zero because every draw at the cell for no head keys costs exactly zero and every draw at the first cell costs nearly the same, and a bar read between two cells that agree with themselves is a narrow bar. The error was not in the cells at all; it was in the space between them, where the table holds nothing to have a spread.

That is the dependence the prediction named as its risk, in a different form. The sources were supposed to be independent errors that average; this is a shared one, the same mispricing of a step for every group of every file at that setting, and it adds. A bar computed from how much draws differ cannot see an error that every draw shares.

How far the bars can be believed

A bar of two standard deviations should hold the truth about 95 times in a hundred if it is honest about all the error there is. The choice only needs the bars at the top of each sort’s options; the estimates of every option on every sort ask more of them.

Two bars should hold about 95% of estimates; across the 1520 estimates they hold 58% — the estimates whose groups rotate reach at most 76%, at a buffer of 1/1024, and those whose groups all fit the buffer at most 60%The share of every number of rounds' estimate, over eight files and five reaches, that lies within two of its own standard deviations of the measured cost, by buffer, separately for the options where some group is longer than the buffer and crosses partly by rotation, and those where every group fits. 1/16: rotating 35% of 40, fitting 0% of 40; 1/32: rotating 55% of 80, fitting 5% of 40; 1/64: rotating 72% of 120, fitting 20% of 40; 1/128: rotating 71% of 160, fitting 40% of 40; 1/256: rotating 75% of 200, fitting 20% of 40; 1/1024: rotating 76% of 280, fitting 60% of 40; 1/4096: rotating 55% of 360, fitting 0% of 40.0%25%50%75%100%95%some group longer than the bufferevery group fits the bufferbuffer 1/1635%0%buffer 1/3255%5%buffer 1/6472%20%buffer 1/12871%40%buffer 1/25675%20%buffer 1/102476%60%buffer 1/409655%0%share of estimates within two of their own barsdashed: what honest bars hold
Fig. 4 The share of every option’s estimate within two of its own bars of what it cost, at each buffer, over eight files and five reaches, separately for options in which some group is longer than the buffer and options in which every group fits.

Over all 1,520 estimates they hold 58%. The options with a group longer than the buffer do best, between 35% at a 16th and 76% at a 1,024th, and never reach 95. The options whose groups all fit the buffer do worst, from none at a 16th to 60% at a 1,024th, because their bars are almost nothing: their draws hardly vary, so the bars claim near-certainty, and the estimates are a percent or two off anyway. The bars are a measure of how much the cost varies between draws. They are not a measure of how far the table is from the cost.

What the bars do get right is scale, at the buffers where the error mostly is the draw.

The bars track the errors only in the middle: from a buffer of 1/32 to 1/256 the estimates' typical error is 2.7% to 4.0% of the sort and the typical bar 2.6% to 3.9%; at 1/16 the error is 1.9% against a bar of 0.04%, and at 1/4096 the bar has shrunk with 82 groups to 0.8% while the error stays at 2.5%By buffer, over eight files at five reaches and every number of rounds: the root mean square of each estimate's error and of its standard deviation, both as a share of the measured sort. 1/16: error 1.94%, bar 0.04%, 1.5 groups on average; 1/32: error 3.97%, bar 3.31%, 2.3 groups on average; 1/64: error 3.94%, bar 3.86%, 3.5 groups on average; 1/128: error 3.96%, bar 3.21%, 5.4 groups on average; 1/256: error 2.72%, bar 2.61%, 8.8 groups on average; 1/1024: error 1.87%, bar 1.40%, 26.0 groups on average; 1/4096: error 2.54%, bar 0.79%, 82.3 groups on average.0.10%1.0%1/161/321/641/1281/2561/10241/4096the estimates' errorsthe barseight files · five reaches · every number of roundsroot mean square
Fig. 5 By buffer, the root mean square of every estimate’s error and of its bar, both as a share of the sort, over every number of rounds on eight files at five reaches. Smaller buffers make more groups.

From a 32nd to a 256th of the file the typical error and the typical bar are within a fifth of each other, 2.7% to 4.0% against 2.6% to 3.9%. Those are the buffers where groups are few, longer than the buffer, and cross by rotation: the error is mostly the file’s draw, and the bars were built to measure the file’s draw. At both ends the bars fall away. At a 16th the error is 1.9% of the sort and the bar 0.04%, which is the step at the table’s edge. At a 4,096th the file makes 82 groups on average, so the draw averages away as the square root of their number, exactly as the file is one draw too said it would, and the bar falls to 0.8%. The error stays at 2.5%.

The error that does not average is the error each group shares with the others. The clearest case at a 4,096th is the option with no rounds on a file whose tail reaches a tenth of the way in: 410 pieces of sixteen keys, priced 5.8% low with a bar fifteen times smaller than its error. Why the table misprices pieces that small has not been measured. What has been measured is that it does it to all of them alike, so the bias the table carries in each cell becomes a bias in the sum, while the spread of the draws, the only thing the bars count, cancels. The covariance the registers already hold is the same lesson about sketches: a variance computed as if its parts were independent is too small by exactly what they share.

What being wrong costs

The bars are dishonest as error bars and yet the choices are rarely wrong. That is less contradictory than it sounds. A choice needs only the order of the cheapest two or three options, and on most sorts those are far apart: the median separation is 83 bars at a 16th, 8 at a 256th, 53 at a 4,096th. The options with the largest errors, rms 3.0%, are mostly the dear ones the rule would never choose; the option it chose was priced within 1.4% on the same measure. The second half of the prediction is about this: when the choice is wrong, how much does it cost?

What each rule costs over the cheapest number of rounds, by buffer: choosing the cheapest estimate never costs more than 2.1% of the sort and 0.14% on average; taking the steadiest option inside the bars is never cheaper and costs 0.16%; merging every round regardless of the draw costs 3.5% on average and up to 24%By buffer, over eight files at five reaches: the mean (bar) and worst (whisker) of how much more each rule's choice cost than the cheapest measured number of rounds, as a share of the sort. 1/16: cheapest estimate 0.37% (worst 2.1%), steadiest within the bars 0.37% (worst 2.1%), every round, always 1.82% (worst 6.3%); 1/32: cheapest estimate 0.45% (worst 2.1%), steadiest within the bars 0.45% (worst 2.1%), every round, always 4.87% (worst 14.3%); 1/64: cheapest estimate 0.02% (worst 0.4%), steadiest within the bars 0.02% (worst 0.4%), every round, always 7.02% (worst 20.6%); 1/128: cheapest estimate 0.00% (worst 0.0%), steadiest within the bars 0.00% (worst 0.0%), every round, always 7.05% (worst 24.4%); 1/256: cheapest estimate 0.00% (worst 0.0%), steadiest within the bars 0.00% (worst 0.0%), every round, always 3.50% (worst 19.1%); 1/1024: cheapest estimate 0.03% (worst 0.8%), steadiest within the bars 0.15% (worst 0.9%), every round, always 0.15% (worst 0.9%); 1/4096: cheapest estimate 0.08% (worst 0.7%), steadiest within the bars 0.11% (worst 0.7%), every round, always 0.11% (worst 0.7%). Sending every piece straight into the head, with no rounds, costs 3% at 1/16, 3% at 1/32, 7% at 1/64, 26% at 1/128, 71% at 1/256, 305% at 1/1024, 1014% at 1/4096 on average and is left off the scale.0%5%10%15%20%25%cheapest estimatesteadiest within the barsevery round, alwaysbuffer 1/16buffer 1/32buffer 1/64buffer 1/128buffer 1/256buffer 1/1024buffer 1/4096bars the mean over forty sorts, whiskers the worstshare of the sort
Fig. 6 By buffer, the mean (bar) and worst (whisker) of how much more each rule’s choice cost than the cheapest measured number of rounds, as a share of the sort, for the cheapest estimate, the steadiest option the bars cannot separate from it, and merging every round always.

Taking the cheapest estimate costs 0.14% of the sort on average over all 280 sorts. The worst wrong choice costs 2.1%, and every wrong choice costs under 2.2%: the prediction’s 3% holds with room. The five the bars called certain cost 1.5% to 2.0%, no more than the guesses did. At a 128th and a 256th the rule was never wrong at all.

The proposal suggested that a rule which knew it was guessing could do something with the knowledge: among the options the bars cannot separate, take the one whose cost varies least. That rule never does better. It differs from the cheapest estimate in eight sorts, all with the tail reaching a tenth of the way in, at a 1,024th and a 4,096th, and in all eight it is dearer, by 0.4% to 0.9% of the sort. The reason is that the steadiest option is nearly always one of the ends, and one of the ends is nearly always what the cheapest estimate already chose. Where the two differ, the steady option is a single group crossing nearly nothing — the option whose bar is narrowest because its cost sits at the table’s edge.

The other proposal, from the same closing section, was that for a few large groups the only safe rule might be the one whose cost does not depend on the draw. Merging every round down to one group comes closest: one group, one crossing. It costs 3.5% of the sort on average across the buffers and up to 24% on a single sort. Sending every piece straight into the head costs more again, many times the sort at small buffers. Both are rules that cannot be fooled by a draw and are worse than one that sometimes is, by an order of magnitude. The join order is a guess found the same economics in a query planner: an estimate badly wrong in one place still chooses well, because the choice depends on which of two costs is smaller, not on either being right.

What the prediction got

  • Every wrong choice inside the bars: 25 of 30. The other five were all one setting, and all a shared error at the table’s edge rather than a draw.
  • A wrong choice costing under 3% of the sort: all 30, the worst at 2.1%.
  • The bars as error bars: honest in scale at the middle buffers, where the error is the file’s draw, and too narrow at both ends, holding 58% of estimates where 95% was meant.
  • Knowing it guesses, choosing the steadier option: never cheaper, and dearer in all eight sorts where it differs.

The failure mode the essay named was the right one in kind. The two sources were assumed to be independent errors that average; the error that survived is the third kind, one that every draw shares, and no number of draws reveals it.

What a bar built from draws leaves out

Bias inside a cell. The bars count the spread of each cell’s sixteen draws. A table can be wrong about the expected cost of a file’s group, as at the edge and for the sixteen-key pieces at a 4,096th, while its draws agree with one another perfectly. Only a comparison against sorts the table did not come from can measure that, which is what the 280 sorts here are.

Correlation between options. The bars of two options are combined as though their errors were independent. On one file the options share keys, and the step at the edge mispriced both options at a 16th in the same direction. A separation is the uncertainty of a difference, and the error of a difference is the reminder that a difference can be far less certain, relative to its size, than either of its parts. Whether separations would be better read from the difference’s own uncertainty has not been measured.

Other files. Every file is 65,536 keys with a late tenth drawn uniformly from the top reach of the key range. The absorbed key that put every group one key from the head is particular to a tail that starts above every head key, which is the case of a tail reaching a tenth of the way in and of nothing else measured here.

The cost of the bars. A bar needs only the spread of draws the table already made, kept beside each cell’s mean, so it adds no measurement. What was never counted is the table’s own construction — sixteen synthetic sorts a cell — against the moves it saves.

A result the size of its own noise applies to the regrets themselves: a mean of 0.14% over 280 sorts in which 250 are zero is a statement about the 30, and thirty is a small number to state it from.

Still open: a table that starts at one head key

Every separated wrong choice came from one place: the table reads a straight line between no head keys and an eighth of the run’s length, and the cost of crossing is a step at one key followed by a slow climb. The table could place cells where that step is — at one head key, two, four and so on up to its present first cell, a grid in the logarithm of one more than the head keys rather than of the head keys — with sixteen draws in each as now.

The measurement that follows rebuilds the table that way and reruns the same 280 sorts. The prediction is that the five sorts at a 16th the bars called certain become right or fall inside the bars, that the coverage of two bars at a 16th rises from 18% to over 60%, and that nothing changes at a 128th and a 256th, where no group meets so small a head. It could fail at the other end: the pieces of sixteen keys at a 4,096th are priced 5.8% low, and most of them meet hundreds of keys above their smallest — the earlier pieces’ keys — far above the table’s first cell, so if their error is the same step at a finer scale the new cells will mend it, and if it is something else the bars will still claim a certainty the table has not earned. The question is whether a calibration can be made honest by putting its cells where the cost bends, or whether a bar that cannot see shared error needs a second term measured against real sorts.

Named alongside this one

Essays reaching for the same objects. Nobody chose these; they are what the concept index makes visible.

The objects this essay names

Each one links to every other essay that touches it.

Merge sortPredictionRotationStable sortVariance