A merge that decides per run whether to gallop

The runs a short list cannot have measured two ways to merge sorted lists whose keys take few values. The three-way textbook merge compares the heads of the two lists, and when they are equal takes a key from each — two keys placed for one comparison. The run merge, on an equal answer, gallops along each list to find where that value’s run ends, comparing the run’s first key with the keys one, three, seven places on until one differs, then halving back, and places both runs whole before comparing across again. Galloping pays on long runs and costs on short ones. At every list length measured it stopped paying at the same place, when a value’s run averages between sixteen and thirty-two keys a list, because a gallop over a run of $r$ keys costs about $4 \log_2 r + 1$ comparisons where walking it costs $r$ halves of one.

That is a rule about the whole input, a threshold on its mean run, and that page’s closing section noticed that a skewed input would want it value by value: gallop over the run of a common value, walk the run of a rare one. A merge cannot know a run’s length before it explores it, but it can know how the last few runs went, the way Timsort’s merge raises and lowers its bar for galloping — the merge most programs call when they sort, as the sort the library ships found. The proposal predicted that a merge galloping only when its last few runs averaged long would match the better of the two merges within a few per cent on uniform values, on both sides of their crossing, and beat both on skewed values. It named the failure: on a skewed input long and short runs alternate in no order, and a bar set by the last few runs is set by the wrong ones.

Four merges, and lists with a law in them #

The lists are drawn so that the proposal’s worry can happen. Each list has $m$ keys, from 256 to 4,096, drawn from $k$ values, from one to twice $m$. Under a Zipf law of exponent $s$ the value of rank $r$ is drawn with probability in proportion to $1/(r+1)^s$; the ranks are assigned to the values in a random order, so that along the sorted lists common and rare values interleave and a long run is as likely to follow a short one as another long one. Exponent nought is uniform. Thirty-two pairs of lists are merged at every setting, and every comparison is counted, across or inside a list.

Four merges are compared. Walk is the three-way textbook merge. Gallop is the earlier page’s run merge, galloping over every equal run. The history rule is the proposal’s: on an equal answer, gallop if the mean length of the last four runs the merge has learned exceeds a threshold θ, from 4 to 64 keys, and walk otherwise; a gallop learns its runs’ lengths exactly, and a walk learns a run’s length as the number of consecutive equal answers it gives, once the run ends. The bar is Timsort’s rule moved from wins to equal answers: on equal answers the merge walks, counting them, and when the count of consecutive equal answers for one value reaches a bar it gallops to the end of the run; after a gallop that extended the run by at least the bar, the bar falls by one, and otherwise it rises by one. The bar starts at seven, Timsort’s own starting value.

On skewed values the bar beats both #

Under Zipf 1, at 4,096 keys a list and 1,024 values, the bar makes 0.447 comparisons a key against 0.595 for walking and 0.594 for galloping: a quarter under both. This is the proposal’s prediction for skewed values, and it holds wherever the values are many. Where they are few, every run is long and galloping everything is right; the bar pays a little for walking the first few equal answers of every run before it gallops, 0.022 against galloping’s 0.020 at four values.

The mechanism is the one the proposal hoped for. Under a Zipf law the most common value holds a large share of each list — at exponent 1 and 1,024 values about an eighth — so its run is hundreds of keys long, the next few values’ runs hundreds too, and the next hundred values’ runs tens. The long tail of rare values has runs of one or two. Walking pays the long runs a comparison for every two keys; galloping pays the short runs four or five comparisons to discover they hold one key. The bar walks every run’s first seven or so equal answers, which a rare value never reaches, and gallops the rest, which only the common values have.

On uniform values it stays near the better #

On uniform values the bar stays within about a hundredth of a comparison a key of the better merge on both sides of their crossing, never more than 0.012 over, at the crossing itself. The proposal’s other prediction holds too, in its strong form: “within a few per cent” was the target, and the bar is within about two per cent of the better merge from 32 values up. Below that, where both merges cost a few hundredths of a comparison a key, a few thousandths is a larger share, and the bar is up to a fifth over galloping in ratio while being under three thousandths of a comparison over it in count.

At the crossing, uniform values make runs that all have about the same expected length: at 256 values and 4,096 keys a list, sixteen keys, with the spread chance gives them. The bar gallops a run once the run has passed its current bar and learns from each gallop, so it settles at a bar where galloping and walking cost about the same, which is exactly where the crossing is. It cannot beat the better merge there, because there is nothing to separate — every value is equally common — and it does not lose much to it.

The history rule cannot learn a run that has not ended #

The proposal’s own rule fails where its premise fails: at one, two or four values the history rule walks every run, 0.500 comparisons a key against the bar’s 0.022 at one value, because a walk learns a run’s length only when the run ends, and on a list of one value no run ever ends. It needs four runs learned before it will gallop at all, and with four values each list has only four runs. Where the values are many it learns, and it does no better than walking: at every number of values from 64, the bar beats every history rule.

The failure the proposal named — long and short runs alternating, the last few runs being the wrong ones — is real, and it is the smaller of the history rule’s two problems. The larger is that a run’s length is the one thing a walk cannot tell until the run is over, and by then the decision whether to gallop it has been made. The bar decides inside the run: it walks while the run is short enough that walking costs less than galloping would, and gallops the moment the run has shown itself long. It reads the current run, not the last ones, and needs no history of other runs at all except to set the bar, which moves by one at a time.

Where the gain is #

Under a skewed law the bar gains where the values are many, most under Zipf 1: at 4,096 keys a list and 1,024 values it makes 1.001, 0.999, 0.752 and 0.893 times the better merge’s comparisons under exponents 0, 0.5, 1 and 1.5. Zipf 0.5 is too flat to separate common runs from rare ones; at 1,024 values its commonest value’s run is a few dozen keys and a typical run a handful, so galloping and walking each lose on the other’s runs about equally and the bar gains nothing. Zipf 1.5 is so steep that a few values hold most of each list and galloping everything is already close to right, so there is less for the bar to add. Zipf 1 sits where both kinds of run are common, and there the bar gains a quarter.

The bar’s advantage grows with the lists: its best is 0.922, 0.800 and 0.752 times the better merge at 256, 1,024 and 4,096 keys a list. Longer lists give the common values longer runs, which galloping covers in logarithmically many comparisons, and give the rare values no longer runs, which walking covers in one or two. The two kinds of run grow apart as the lists grow, which is when a merge that treats them differently earns most.

What the bar gallops #

The bar gallops where galloping pays and stops where it does not: on uniform values it gallops 86% of the equal runs it meets at 128 values and none at 1,024; under Zipf 1 it gallops 6% of them at 1,024 values. The 6% is the point. Under a Zipf law nearly every run a merge meets is a rare value’s short run, and the few it gallops are the common values’ runs, which hold a large share of the keys. The bar finds them without knowing which values are common, by noticing that a run has gone on for seven equal answers.

That is a different kind of adaptivity from the one the earlier pages measured. When galloping pays and the floor when the values repeat treated the input’s run lengths as a property of the input, to be known or estimated before choosing a merge; the bar treats them as a property of each run, discovered while merging it, and makes the choice once a run. A threshold on the mean run is the right rule only when the runs are all alike.

What the bar costs on a run #

The bar’s cost on any one run can be written down, and it explains both its small losses and its large gains. A run of $r$ equal keys in each list costs $r$ comparisons to walk, one for every two keys placed, and about $4 \log_2 r + 1$ to gallop, by the earlier page’s count. The bar walks the first $b$ equal answers and gallops the rest, so it pays about $b + 4 \log_2(r - b) + 1$ on a run longer than its bar and exactly the walk’s $r$ on a run shorter. On a run of five hundred keys with a bar of seven that is about forty-four comparisons where galloping from the start costs thirty-seven, a fifth more; on a run of three it is three, where galloping costs about eight.

So the bar is never far from the better merge on any single run, and it is the better merge on runs of mixed lengths, because it pays the cheaper price for each. On uniform values with few values, where every run is long, it pays the first $b$ answers of every run for nothing, which is the few thousandths it loses to galloping there. On uniform values near the crossing, where every run is about as long as a gallop’s break-even, both prices are about the same, which is why it neither gains nor loses. Under a Zipf law the runs are of every length at once, and the bar’s choice per run is worth a quarter.

The bar moves, but on these lists it does not move far. It falls when a gallop extends a run by at least the bar, and on a list of common values that happens on most gallops, so there the bar falls toward one; on rare values it never gallops, and the bar stays where it was. Seven, Timsort’s starting value, was chosen for runs of distinct keys from two lists, where a gallop’s break-even is about where it is here, and the sort the library ships found the library’s constants tuned for the inputs the library expects. The plates suggest the same constant serves for equal runs, and none of these lists tested a different starting value.

The floor this does not reach #

The merge that can say equal solved the game exactly at four keys a list and found the counting floor met by a merge that answers “equal”. These lists are thousands of keys long, too long to solve, and none of the four merges is claimed to be optimal on them. How close anything gets to the floor measured sorts by their distance from the bound nothing can cross; a merge of Zipf-distributed lists has such a bound too — the logarithm of the number of interleavings consistent with the lists’ value counts — and how far above it the bar sits under Zipf 1 is the measurement this page did not make. The bar is a quarter under the better of two merges, which is a statement about those merges, not about the floor.

What these lists leave out #

Equal answers only. The bar here counts consecutive equal answers. Timsort’s own bar counts consecutive wins of one list over the other, which is how it gallops over long stretches of distinct keys in which one list’s keys all come first. These lists have that structure too, wherever two adjacent values each have long runs, and a merge using both bars was not measured.

One law of interleaving. The ranks are assigned to values at random, so long and short runs alternate in no order. A law whose common values come first — a list of priorities, say — would give the history rule the long runs together and might rescue it; the bar does not depend on the order, any more than the pattern that defeats the pattern found pdqsort’s pattern-breaking needed to know which pattern it faced.

Comparisons only. Every cost is comparisons. A gallop also moves a run whole where a walk moves it a key at a time, and the moves were not counted; the floor a merge cannot reach is the reminder that a merge’s comparisons and its moves are two different floors.

Still open: one bar for equal answers and wins #

Timsort gallops when one list wins repeatedly, the bar here when the lists tie repeatedly, and a merge of repeated values meets both: a long run of one value in one list facing a short run in the other is a stretch of wins, and two long runs of the same value are a stretch of ties. Each bar sees one kind of stretch and walks the other.

The measurement that follows gives the merge both bars, sharing one count of consecutive answers of either kind — ties or wins by the same list — and one bar that moves as either kind of gallop pays or fails, and runs it on the same lists, uniform and skewed, at every length. The prediction is that it gains a further tenth 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 changes nothing on uniform values, where such stretches are no longer than the ties. It could fail on the shared bar: a gallop over wins and a gallop over ties pay at different run lengths, since a tie places two keys a comparison and a win one, and a bar tuned by one may be wrong for the other. The question is 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.