The wins two sources leave

A bar that wins rarely meet tested a proposal that sounded like a free improvement and found it worth almost nothing. A merge of two sorted lists of repeated values meets two kinds of stretch. In a stretch of ties, both lists hold a run of the same value — the case the merge that can say equal first priced, and the runs a short list cannot have first galloped — and a merge that decides per run had learned to gallop those: walk a run of equal answers until a bar of them have come in a row, then search both lists exponentially for the run’s end, lowering the bar after a gallop that paid and raising it after one that did not. In a stretch of wins, one list supplies key after key while the other waits, which is the stretch Timsort’s own bar is for. One count of consecutive answers of either kind, and one bar moved by either kind of gallop, was predicted to save a further tenth under Zipf 1.

It saved at most 1.0%, and the reason was in the lists. Both were drawn from one distribution, so a value common enough to have a long run in one list was common in the other too, and its two runs tied for nearly their whole length; what was left over for one list to win was the difference between two long runs’ lengths, about the square root of either. Stretches of eight or more wins held 1% of keys or less at every number of values. The essay closed by naming the case the proposal had pictured and the measurement had excluded: two lists from different sources, a merge of this week’s keys into last month’s, where the values common in one are rare in the other.

Ranks that do not agree #

The lists here are drawn as before, with one change. Two sorted lists of 1,024 keys each are drawn from $k$ values with probability proportional to $1/(\text{rank}+1)^s$, and a permutation decides which value has which rank. In the earlier essays both lists used the same permutation. Here the second list’s permutation is allowed to differ from the first’s, under a dial called agreement: at full agreement both lists share one permutation, which is exactly the earlier lists; at none the second permutation is drawn independently; in between, a share of the ranks is chosen at random and re-dealt among themselves, and the rest keep their place.

The values and the weights are identical in both lists at every setting. What changes is only which values are common where. That isolates the one thing the earlier essay said was missing, and it leaves a clean control: on uniform values, where every rank has the same weight, re-dealing ranks cannot change anything.

The merges are the earlier ones, unchanged: the walk, which compares and places one key at a time; a gallop on every tie; the bar for ties alone; one bar shared by both kinds of stretch; and a bar for each kind. Every comparison is counted, across the lists and inside one, and the cost is comparisons a key of output over 32 trials.

A third, not a tenth #

With independent ranks the shared bar saves 33.5% over the bar for ties alone at 64 values, and more than a tenth at every number of values from 32 to 2,048: 32.1% at 128, 28.1% at 256, 22.8% at 1,024, 18.9% at 2,048. With half the ranks re-dealt it saves up to 21.7%, at 128 values. With all of them agreeing it is back to the earlier essay’s result, at most 1.0%.

So the prediction held, by a factor of three, on the lists it was made about. Its failure in the earlier essay was not a defect of the rule but of the inputs it was tried on, and the earlier essay’s account of why — that wins are rare and short when two lists share a distribution — is confirmed from the other side: make them disagree and the wins are neither.

The curves rise from zero at few values for the same reason as before. With sixteen values or fewer every value is common enough to appear in both lists whatever its rank, nearly every value is a tie somewhere, and there is nothing for either list to win. The saving appears at 32 values, where the rarest values in one list start to be absent from the other, and peaks between 64 and 128.

Where the saving comes from #

The size of the saving is not the shared bar doing something clever. It is the bar for ties alone collapsing.

On lists whose ranks agree, the bar for ties cost 0.510 comparisons a key at 256 values. On lists whose ranks are independent it costs 0.838, against the walk’s 0.864 — it has lost nearly everything it had. The shared bar costs 0.603, a fifth above where the tie bar was on agreeing lists, and a bar for each kind of stretch 0.593.

The reason is what each list’s common values now face. Under Zipf 1 at 256 values, the commonest value in the first list holds about a sixth of its keys, a run of about 170. In the second list that value has a random rank, so it is typically one of the rare ones: a run of zero, one or two keys. A tie bar sees one or two equal answers, never reaches its bar, and walks the other 168 keys one comparison at a time — which is the walk. The shared bar sees seven wins in a row by the first list, gallops to the first key not smaller than the second list’s current key, and places the run in about sixteen comparisons. Every common value of either list is such a run, and the common values hold most of the keys.

A gallop on every tie does worse still at most numbers of values, because the ties that remain are short and every one of them now costs a search. That was the earlier essays’ finding about galloping on short runs, and disagreement makes almost every run that still ties a short one.

The stretches the lists offer #

The earlier essay explained its null result by measuring the stretches directly, and the same measurement explains this one.

With agreeing ranks, stretches of eight or more wins hold at most 1% of keys anywhere. With independent ranks they hold 18% at 256 values, 30% at 512, 42% at 1,024 and 44% at 2,048; with half agreeing, 10% to 22% from 256 values up. The share of keys whose value the other list also holds falls just as sharply: at 1,024 values from 79% with agreeing ranks to 32% with independent ones.

The plate’s rise with the number of values is the reverse of the saving’s fall, and the two are consistent. At many values more keys lie in long stretches of wins, but the stretches are made of more distinct values — a stretch is a run of one list’s values the other lacks, not one value’s run — and a gallop through a stretch of mixed values must still find where it ends among them. The mean stretch falls from 13.2 keys at 64 values to 5.1 at 1,024, so each gallop saves less, and the saving over the tie bar falls with it.

A steeper skew #

Under Zipf 1.5 the effect is larger at every number of values. The tie bar alone costs 0.917 comparisons a key at 256 values, against the walk’s 0.951 and against the 0.292 it cost on agreeing lists; the shared bar costs 0.319, within a tenth of where the tie bar was on agreeing lists. The saving over the tie bar is between 60% and 65% at every number of values from 64 up.

A steeper skew puts more of each list into fewer values. With agreeing ranks that is all tie, and the tie bar gallops it; with independent ranks it is all win, and only a bar that counts wins can gallop it. The shared bar is nearly indifferent to which: from 64 values up under Zipf 1.5 it costs 0.253 to 0.313 comparisons a key on agreeing lists and 0.279 to 0.353 on independent ones. A merge with one bar for both kinds of stretch costs about the same whether its inputs come from one source or two, and a merge with a bar for ties alone is fast on one and slow on the other.

That is the real argument for the shared bar, and it is not the one the earlier proposal made. The proposal promised a further saving on top of the tie bar’s. What the shared bar actually supplies is insurance: on lists from one source it costs a hundredth either way, and on lists from different sources it saves between a fifth and two thirds.

How much disagreement it takes #

The earlier essay’s closing section predicted that the gain would “fall smoothly as the ranks are made to agree”. It does fall, and it falls in the wrong shape for smoothly.

Re-dealing a tenth of the ranks buys 7.4% under Zipf 1 and 17.0% under Zipf 1.5, already a fifth and a quarter of what independent ranks give. A quarter re-dealt buys 10.7% and 33.0%. Half buys 21.7% and 52.1% — 65% and 80% of the full saving. The last half of the re-dealing adds the remaining third or fifth.

The curve is steep at the start because the saving is carried by a few values. Under Zipf 1 at 128 values the five commonest values hold about two fifths of the keys; re-dealing a tenth of the ranks moves one of them, on average, to a rank where it is rare in the second list, and that one value’s run is long enough to be galloped for a large saving. Once the commonest values have disagreed, re-dealing the rare ones adds little, because rare values make short stretches whichever list they favour. A merge does not need two sources that disagree everywhere for the shared bar to pay; it needs two sources that disagree about their few most common values.

That is the ordinary case for merging data from different times or places. The commonest values of this week’s log and last month’s are likely to differ in a few places — a new error, a retired endpoint, a client that appeared — and it is exactly those few places that the plate says decide the saving.

The control #

On uniform values the dial does nothing, as it must: the bar for ties and the shared bar cost the same with agreeing and independent ranks to within three thousandths of a comparison a key at every number of values, and the shared bar is never cheaper than the tie bar — 0.645 against 0.638 at 256 values with independent ranks, the same small cost the earlier essay found and explained as failed win-gallops raising the bar. Every effect in the plates above comes from frequencies that disagree, and none from the act of drawing a second permutation.

A merge does not know its sources #

The plates set agreement by hand. A merge is given two sorted lists and nothing about where they came from, so the useful question is what a merge should do when it cannot tell which case it is in.

The answer the plates give is unusually clean. On agreeing lists the shared bar costs at most a hundredth more than the tie bar, and on uniform values at most 1.6% more; on disagreeing lists it costs a fifth to two thirds less. A rule whose worst case is a hundredth and whose best case is two thirds is not a bet. It is what a library should ship, and the sort the library ships already ships most of it: Timsort’s bar is a bar for wins, and what the earlier essays added was a bar for ties. The shared bar is those two rules counting together.

The opposite failure is the one the pattern that defeats the pattern recorded for adaptive sorting: a rule tuned to a structure the input happens to have, losing badly when the input has a different one. The bar for ties alone is that rule here. It is the best of the merges measured on lists from one source and nearly the worst on lists from two, and nothing in either list tells it which it is facing until it has already walked the long runs.

One bar or two #

The earlier essay asked whether a merge’s gallops should be counted by the kind of stretch, and found the question idle because only one kind occurred. With independent ranks both kinds occur, so the question can be answered.

Two bars, one for each kind of stretch, do slightly better than one. Under Zipf 1 with independent ranks they save 37.1% over the tie bar at 64 values against the shared bar’s 33.5%, and 35.3% against 32.1% at 128; from 512 values up the two are within half a point. Under Zipf 1.5 the difference is at most 1.3 points. The risk the earlier proposal named — that a gallop over ties places two keys a comparison and a gallop over wins one, so a bar tuned by one is wrong for the other — is real and is worth a few points at the numbers of values where both kinds of stretch are common. It is not worth a second count on lists where they are not.

When galloping pays gives the arithmetic for why the difference is small. A gallop pays when the stretch it skips is longer than about twice the logarithm of its length. The bars that decide when to try one differ by a few keys, and the stretches here are either much longer than seven (the common values’ runs) or much shorter (the rare values’), so either bar makes the same decision on almost every stretch that matters.

What the measurement does not include #

All the lists are 1,024 keys. Longer lists make the common values’ runs longer and the saving larger; the earlier essays measured three lengths and these plates measure one, so the percentages are percentages at one length.

The lists are drawn independently given their permutations. Real data from two sources has structure the dial does not model: the two lists’ common values might differ only in their top few ranks, or one list might be a time-shifted copy of the other. The dial’s concave shape says the top ranks are what matter, which suggests the first case behaves much like the plate’s left-hand end; neither was measured.

And nothing here touches the floor. How close anything gets to the floor measured the information-theoretic floor for merges of repeated values on agreeing lists; on disagreeing lists the floor is lower still — a merge that knew each value’s run lengths in both lists could place each run with one comparison — and how near the shared bar comes to it is not measured.

Still open: a floor for lists that disagree #

The plates price two bars against each other and against the walk, and never against what a merge of these lists must spend. On agreeing lists that gap was the whole story of the earlier essays: the floor when the values repeat set it and the tie bar came within a sixth of it. On disagreeing lists nobody has set it.

The measurement that follows computes the floor for a merge of two lists with given run lengths — the logarithm of the number of interleavings consistent with both lists’ runs — for agreeing and independent ranks, and places the five merges against it. The prediction is that with independent ranks the floor falls further than the shared bar does, so the shared bar sits about a third above the floor where the tie bar sat a sixth above it on agreeing lists, and that the gap is in the rare values’ short stretches, which a bar of seven never gallops. It could fail on the interleavings: when the lists disagree, the number of ways to interleave two runs of different values grows quickly, and the floor may not fall at all. The question is whether disagreeing sources make a merge cheaper in principle or only cheaper for a merge that can gallop.