A bar that wins rarely meet

Merging two sorted lists of $m$ keys costs about $2m$ comparisons when the keys are distinct, and much less when they repeat. The merge that can say equal let a merge answer “equal” as well as “less”, so that two keys of the same value leave together for one comparison, and the floor when the values repeat priced how far below the distinct-key floor such a merge can go. The runs a short list cannot have added galloping on equal answers: having seen two keys equal, search each list exponentially for the end of the value’s run and place both runs at once, which pays when runs are long and loses when they are short, crossing near a mean run of 16 to 32 keys a list.

A merge that decides per run found the rule that learns that crossing as it goes. Timsort’s rule, turned onto equal answers: walk a run of equal answers one comparison at a time until a bar of them have come in a row, then gallop to the run’s end; lower the bar by one after a gallop that extended the run by at least the bar, raise it by one otherwise. On uniform values it matched the better of walking and galloping everywhere, and on skewed values it beat both, by up to a fifth under Zipf 1, because it gallops the common values’ long runs and walks the rare ones’.

Timsort’s own bar is not for ties. Its merges count consecutive wins by one list — the left list’s key smaller, again and again — and gallop through the winning list for the first key that is not smaller, on the reasoning that real data has runs where one input dominates for a while. The closing section noticed that a merge of repeated values meets both kinds of stretch. A long run of one value in one list facing a short run of it in the other is a stretch of wins, since after the ties are spent one list keeps winning; two long runs of the same value are a stretch of ties. Each bar sees one kind and walks the other. The proposal was one count of consecutive answers of either kind — ties, or wins by the same list — and one bar moved by either kind of gallop. It predicted a further tenth saved over the equal-answer bar under Zipf 1, from the stretches where one list holds a common value’s long run and the other a few of its keys, and nothing changed on uniform values. It named the risk: a gallop over ties places two keys a comparison and one over wins places one, so a bar tuned by one may be wrong for the other.

One count, one bar #

The lists, the values and the counts are the earlier essays’. Two sorted lists of $m$ keys are drawn from $k$ values with probability proportional to $1/(\text{rank} + 1)^s$, the ranks permuted among the values so that common and rare values interleave along the lists; $s$ = 0 is uniform. Every comparison is counted, across the lists and inside one, and the cost is comparisons a key of output, averaged over 32 trials, each on a fresh pair of lists.

The shared bar keeps one count: how many answers in a row have been of the same kind, where the kinds are a tie, a win by the first list and a win by the second. When the count reaches the bar, the merge gallops. After ties it gallops along both lists to the end of the value’s run, as before; after wins by one list it gallops through that list for the first key not smaller than the other list’s current key, exponentially and then by halving. Either gallop moves the one bar by Timsort’s rule. A second version keeps two bars, one for each kind of stretch, each moved only by its own gallops, to answer the named risk directly.

A hundredth, not a tenth #

The tenth predicted under Zipf 1 is a hundredth at most: the shared bar saves at best 1.0% over the bar for ties alone, at 256 values, and on uniform values it costs up to 1.3%. At every number of values under Zipf 1 the two bars land within a hundredth of each other: 0.515 comparisons a key for the tie bar and 0.510 for the shared bar at 256 values, 0.600 and 0.599 at 1,024, 0.414 and 0.411 at 64. On uniform values the shared bar is never cheaper and at 128 to 512 values is slightly dearer, 0.615 against 0.607 at 128. Under Zipf 1.5 the picture is the same at a smaller scale.

The prediction failed by an order of magnitude, and its second half, that nothing would change on uniform values, nearly held — a cost of a hundredth is close to nothing. The failure is not a small effect masked by noise; the shared bar is consistently a hundredth either side of the tie bar because it is, nearly always, the tie bar.

Zipf 1, curve by curve #

Zipf 1, two lists of 1,024 keys: one bar for ties and wins costs within 1.0% of the bar for ties alone at every number of values — at best 1.0% under it, at 256 values, and at worst 0.5% over, at 32 — and a bar for each kind of stretch is no better than one. The curves the earlier essays drew are all still here: the walk at about half a comparison a key at few values rising to 0.69 at 2,048; the gallop on every tie far below it at few values and above it from about 128; and the tie bar under both, at the better of the two everywhere and under both from 64 values up. The two new bars are drawn on top of the tie bar and cannot be told from it at this scale.

So the risk the proposal named — one bar tuned by ties being wrong for wins — is not what limits the saving; two bars, each tuned by its own gallops, do no better than one, 0.416 at 64 values against the shared bar’s 0.411. The limit is that there is little to save.

Wins are rare and short #

Under Zipf 1 the shared bar’s gallops are over wins at most 18% of the time: the stretches where one list wins repeatedly are rare and short in two lists drawn from the same distribution, and where values are many enough for wins to dominate — 93% of gallops on uniform values at 1,024 — there is nothing left to gallop over. The proposal pictured a common value with a long run in one list and a few keys in the other. With both lists drawn from the same distribution that is uncommon: a value common enough for a long run in one list is common in the other too, and its two runs tie for most of their length. The excess of one run over the other is about the square root of the run’s length, so a common value’s run of a hundred keys in each list leaves a stretch of wins of about ten.

On uniform values with as many distinct values as keys, almost every answer is a win, and the shared bar’s gallops are nearly all over wins. But there the stretches of wins are what any merge of two random lists has: a run of one list’s keys lying between two keys of the other averages one or two, and a gallop needs about seven before the bar lets it start. The few that reach the bar are as likely to end just after it as to run on, and the bar rises. When galloping pays priced this for distinct keys: a gallop pays only when the stretch it skips is longer than about twice the logarithm it spends finding the end, and random merges almost never offer one.

Three lengths of list #

The lists here are 1,024 keys each, the middle of the three lengths the earlier essays used, and the length decides how long a common value’s runs can be. At 4,096 keys a list the runs of a common value are four times as long and their difference in length, if it grows as the square root, twice as long; a stretch of wins that averaged ten keys would average twenty, enough for a gallop to save a little. At 256 keys the stretches would be half as long and save nothing. The essay’s lists were chosen for continuity with the bar it extends, and the figures were not rerun at the other lengths, so the hundredth measured here is the hundredth at one length. The account above predicts that it grows slowly with the lists, by about a factor of the square root of the length, which would still leave it well under a tenth at any length these essays have used.

Steeper skew #

Under Zipf 1.5 the shared bar is within 0.8% of the tie bar everywhere, at best 0.8% under it at 2,048 values. A steeper skew concentrates the keys in fewer values, so their runs are longer and their wins’ excesses longer too; the plate shows the shared bar a fraction ahead at the largest numbers of values, where a few very common values supply what stretches of wins there are. But the steeper the skew, the more of every list is in those few values’ runs, and the tie bar has already galloped them.

Why the shared bar can cost #

On uniform values from 128 to 512 the shared bar is a hundredth dearer than the tie bar, and the plates allow one account of it. At those numbers of values the runs of ties are a few keys long, so the tie bar has already risen high and rarely gallops; the shared bar, counting wins as well, sees an occasional stretch of seven wins in a row and gallops over it. Most such stretches end soon after the bar, the gallop pays less than it spends, and by Timsort’s rule the bar rises — the same bar that governs the ties. A shared bar is therefore raised by failed win-gallops and lowered by successful tie-gallops, and on inputs where neither kind of stretch is long it does a little worse than a bar that only ever sees one kind. The two-bar version shows the same small cost, 0.618 at 128 values against the tie bar’s 0.607, which says the cost comes from the win-gallops themselves rather than from the sharing: a bar of its own for wins does not stop them being tried.

The cost is small because the wins’ stretches rarely reach seven. A run of one list’s keys falling between two consecutive keys of the other list is, in two independent random lists, about as likely to be of length one as two, and a stretch of seven or more is a few per cent of them. Each such stretch, galloped over, costs about the logarithm of its length twice — once outward, once back — and saves its length minus one; at seven or eight keys that is about break-even, which is why the measured costs and savings are hundredths.

The ties were already doing the work #

Under Zipf 1 at 256 values the shared bar saves a hundredth, the most it saves anywhere, and the tie bar alone saves a sixth over the walk there, 0.515 comparisons a key against 0.603. That proportion is the finding: the earlier essay’s bar on ties captured almost everything a gallop can capture on these lists, and the wins that remain are the small residue left when two runs of a common value are of slightly different lengths. How close anything gets to the floor measured how far any merge sits above the information-theoretic floor for these inputs; the gap the tie bar leaves is mostly in the rare values’ short runs, which neither bar can gallop and both walk. Closing that residue needs a different kind of saving altogether — fewer comparisons on a short run, not a faster way past a long one — and none of the merges measured here or in the essays before has found one that a merge can make without knowing the values’ frequencies in advance, which is the one thing a merge of two unseen lists does not have.

A merge’s two kinds of stretch #

The closing question was whether a merge needs one bar or two, or whether the kind of stretch it is in matters less than how long the stretch has already lasted. The measurements answer a prior question: on lists like these, stretches of wins long enough to matter barely occur, so neither one bar nor two can make use of them. Both bars, and the shared one, end up decided by the ties.

That says something about where Timsort’s rule earns its keep. The sort the library ships runs on real data, where one input often does dominate for a while — a nearly sorted list, a merge of a long sorted block with a few late arrivals — and stretches of wins are the common case. Two lists drawn from one distribution are the opposite case, and the stretch that matters there is the tie. The pattern that defeats the pattern found the same kind of dependence for a sort’s adaptivity: a rule tuned to a structure helps only on inputs that have it.

What the lists do not have #

Independent lists. Both lists are drawn from the same distribution independently. Lists from different distributions — one list’s common values rare in the other — would have long stretches of wins, and there the shared bar might gain what was predicted. That was not run.

Comparisons only. Every comparison is counted the same, a tie-gallop’s equality test and a win-gallop’s ordering test alike, and moves of keys are not charged at all.

One starting bar. Every bar starts at seven, Timsort’s value. A shared bar that started lower, or adjusted by more than one, was not tried.

Still open: lists that do not share a distribution #

The shared bar had nothing to gallop over because two lists drawn from one distribution rarely let one of them win for long. The case the proposal pictured — a common value with a long run in one list and a few keys in the other — is the ordinary case when the lists come from different sources: a merge of this week’s keys into last month’s, where the recent values are common in the new list and rare in the old.

The measurement that follows draws the two lists from Zipf distributions with the same values but their ranks permuted independently, so that a value common in one list is typically rare in the other, and from a mixture in between, and runs the same merges. The prediction is that with independent ranks the shared bar saves a tenth or more over the tie bar under Zipf 1, since a common value’s run in one list now faces a short run in the other and leaves a long stretch of wins, and that the gain falls smoothly as the ranks are made to agree. It could fail on the ties: with independent ranks the ties themselves become short, and a bar shared with them may be raised by failing tie-gallops just when the wins are long. The question is whether a merge’s gallops should be counted by the kind of stretch or by the source of the lists, and whether a merge can tell the two apart from its own answers.