The threshold somebody chose

Every essay on this site until this phase has been concerned with constants the notation throws away. Merge sort and heapsort are both $\Theta(n \log n)$ and their comparison counts differ by a factor of two; that factor is a property of the algorithms, it emerges from their structure, and nobody chose it.

The constants in this essay are different in kind. They were typed into a source file by a person, they can be changed by editing one line, and the algorithm’s behaviour changes when they are. There are four of them worth measuring, they are all in code running on billions of devices, and none of them is documented with a derivation.

The site’s discipline says a constant is measured rather than repeated. So: sweep each one, hold everything else, and see what the shipped value bought.

minrun #

The comparison count says: use 4. On nearly sorted input, minrun = 4 costs 26,703 comparisons and the shipped 32 costs 33,449 — 25% more. On random input the whole sweep spans 95,270 to 102,191, a 7% band with no clear structure, and the shipped value sits in the middle of it.

So on the counter this site was built around, minrun is a pessimisation. It makes the adaptive case worse and the random case no better. If comparisons were the only quantity, the right value would be 1 — do not pad runs at all, merge whatever the input contains.

This is exactly where the site’s habit earns its keep: do not conclude the library is wrong, ask which counter it was chosen against. There are three others available.

There it is. On random input the comparison count is flat and the write count grows by a factor of 5.4 across the sweep, because extending a run to length $k$ by binary insertion costs $\Theta(\log k)$ comparisons and $\Theta(k)$ moves — logarithmic in the counter that is flat, linear in the counter that is not.

And in the other direction, the number of merges falls from 2,040 to 31. A merge is not free beyond its comparisons: it copies a run into scratch, walks two pointers, and copies back. Two thousand merges of thirty-two elements each is a great deal of loop setup for the same comparisons as thirty-one merges of two thousand.

So minrun sits where the comparison curve has gone flat and the write curve has not yet turned up — somewhere between 16 and 32 at this size, and the shipped rule produces 32. It is not the minimum of anything. It is the knee of a trade between two counters that move in opposite directions, and neither of them alone identifies it.

That is the finding this field was built to produce, and it took two counters to see. One counter says “smaller”; the other says “larger”; the shipped value is in between, and a sweep of either one alone would have concluded the library was wrong.

The rule that computes it, and the reason it is not a constant #

minrun is not literally a number in CPython. It is computed from the array’s length by a rule that fits in five lines: take the top six bits of $n$, and add one if any bit below them is set. The result is always between 32 and 64.

The stated reason is that Timsort’s merge tree balances best when the number of runs is a power of two. If $n/\text{minrun}$ comes out at 2,049, the last merge joins a run of 2,048 minruns against a single one, and that merge costs a full pass over the array to move one run’s worth of elements. If it comes out at exactly 2,048, every merge joins equal-sized runs and none of the work is wasted.

The rule arranges for $n/\text{minrun}$ to be just at or below a power of two rather than just above one, which is a different objective from minimising minrun and produces the jagged values it produces: 32 at $n = 1024$, 33 at $n = 1025$, 63 at $n = 1000$, 32 again at $n = 4096$.

That is checkable and the gate checks it: for a range of sizes, $n/\text{minrun}$ is required to sit in the upper half of the interval below the next power of two. It is one of the few constants in this essay with a stated derivation, and it is the only one where the derivation turns out to be about the shape of the merge tree rather than about a cost.

Which raises a question the sweep above cannot answer. The measurements were all taken at $n = 8{,}192$, where $8192/32 = 256$ exactly — a power of two, the best case for the rule. At $n = 8{,}193$ the rule gives 33 and $n/\text{minrun}$ is 248.3, and the merge tree is not balanced. Everything above is therefore measured at the size the rule is happiest at, and a sweep across $n$ at fixed minrun would show a sawtooth that this one cannot. That is a real limitation and it is why the figure names its $n$.

The insertion cutoff #

The comparison count is minimised at 8, at 133,623, and the shipped 16 costs 134,880 — a difference of 0.9%. That is close enough to be uninteresting on its own, so again: which counter?

The two counters point in opposite directions and the shipped value is between them again:

Comparisons are minimised at 8. Reads are minimised at 12. Mispredictions fall all the way to 96 and beyond. The shipped 16 is 0.9% off the comparison optimum, 0.04% off the read optimum, and better on branches than either of them.

Sixteen is not the best value for any of the three counters and it is close to the best for two of them while being on the right side of the third. That is what a well-chosen threshold looks like once there are enough counters to see it — and it is worth noticing that this observation was not available to this collection until the branch counter existed — without it the answer would have been “the shipped value is 0.9% wrong”.

MIN_GALLOP #

Swept in when galloping pays, where the answer turned out to be that the question is malformed: MIN_GALLOP is not a fixed parameter during a sort. It starts at 7 and the algorithm moves it — down by one every time a gallop pays, up by two every time the mode is left — so the shipped value is an initial condition for a feedback loop rather than a setting.

A sweep that holds it fixed measures a version of the algorithm that does not exist. That figure is drawn anyway, and it is labelled, because a measurement of the wrong thing that says so is more useful than an absence: it shows the cost is flat below 7 and rises above it, which is the reason 7 is a safe starting point in either direction.

The depth factor #

This one is the most interesting of the four, because the two inputs disagree completely and the disagreement is not a matter of a few per cent.

On random input, larger is better and the improvement stops at 3. On few distinct values, smaller is better by a factor of 6.7 between 0.5 and 6, and there is no flattening at all: every extra level of quicksort on duplicate-heavy input is spent splitting a block of equal elements that heapsort would have finished.

The shipped 2 is a compromise that costs 0.14% on random input and a factor of 2.5 on duplicates. Given the previous essay’s argument that duplicates are the common case rather than the special one, that looks like the wrong compromise — and the reason it is not is that introsort’s authors were not choosing between these two columns. They were choosing a value at which quicksort’s guarantee holds and the fallback essentially never runs, because the fallback is heapsort, and heapsort’s constant is worse and its memory behaviour is much worse, and a program whose sort silently becomes heapsort on a fifth of its inputs has a performance profile nobody can reason about.

The duplicate problem is real and introsort’s answer to it is not the depth limit. It has no answer to it, which is why pdqsort exists.

The other thing every sweep above holds fixed is $n$, and a threshold is a constant measured against a size. Run the first sweep at a sixteenth of the input and the shipped value stops being anywhere near the minimum.

The thresholds interact, which is why none of them can be tuned alone #

Every sweep above holds the other three constants fixed. That is the only way to draw a two-dimensional figure and it hides something.

The insertion cutoff and the depth factor are not independent: a larger cutoff means fewer partition levels, which means the recursion is shallower, which means the depth limit is reached less often. At a cutoff of 96 the recursion at $n = 8{,}192$ is about $\log_2(8192/96) \approx 6.4$ levels deep before the cutoff catches it, against a limit of 26 — so the depth factor could be halved with no effect at all, and the sweep of the depth factor at cutoff 16 says nothing about its behaviour at cutoff 96.

Timsort’s are worse entangled. minrun decides how many runs there are; the number of runs decides how many merges the policy performs; the merges are where galloping fires; and galloping’s threshold moves during the sort in response to how well it is doing. Four constants, three of them affecting the conditions under which the fourth is evaluated.

The honest description of what the four figures above show is: the cost as one constant varies with the others at their shipped values. That is a one-dimensional slice through a four-dimensional surface, taken at the point somebody else chose, and it can only ever answer “was this choice locally reasonable” rather than “is this the best choice”. Both figures say so.

It is also the reason these constants have not moved in twenty years despite the hardware changing completely underneath them. A constant that could be tuned independently would have been retuned; a constant entangled with three others, in code that billions of programs depend on behaving predictably, is left alone unless something is demonstrably wrong. The stability of these numbers is a fact about the risk of changing them rather than evidence that they are optimal, and the sweeps above are the closest this site can come to saying which.

Three of the four are absolute and one is a ratio #

Set the four constants beside each other and they divide into two kinds, and the division decides how each of them ages.

minrun is between 32 and 64. MIN_GALLOP is 7. The insertion cutoff is 16. All three are absolute counts of elements, and none of them mentions $n$, the word size, the cache line or anything else about the machine.

The depth factor is 2 × log₂ n. It is a ratio, it scales with the problem, and it means the same thing at every size.

That difference matters because of what the absolute constants are implicitly relative to. An insertion cutoff of 16 is a claim that insertion sort wins below about sixteen elements, and that claim is a fact about how a cache line, a register file and a branch predictor behave — none of which are in the source, all of which have changed by more than a factor of sixteen since the number was chosen. A threshold expressed as a bare integer is a threshold that has been silently detached from the quantity it was really about.

The measurements in this essay show what that detachment looks like from the inside. The insertion cutoff’s comparison optimum is 8, its read optimum is 12, and its branch optimum is off the top of the sweep — three different numbers, all in units of elements, and the shipped 16 is a settlement between them under one set of relative costs. Change the relative cost of a mispredicted branch against a comparison, which is exactly what a decade of processor design does, and the settlement moves without a line of the source changing.

The depth factor has no such exposure. It is defined against $\log_2 n$, and what it is really about — how many levels of quicksort are permitted before the recursion is judged pathological — is a property of the algorithm rather than of the hardware. It is also, of the four, the one whose sweep above has a genuinely flat region on the input it was chosen for: anything from 2 to 6 is identical on random data.

So one of the four is scale-free and three of them are calibrated against a machine that no longer exists. That is not an argument that they are wrong — the sweeps say the insertion cutoff is well placed even now — but it says which of them would be worth re-measuring first, and it says why the answer would be a different number rather than the same one.

Why they are not tuned at run time #

The obvious repair to a constant that has drifted is to stop having a constant: measure at run time and choose. It is worth saying why no library sort does this, because the reasons are good ones and they are not laziness.

The measurement costs more than the win. The insertion cutoff’s optimum spans 8 to 16 and the difference across that span is about one per cent of comparisons. Detecting which end of it a particular machine is at requires timing runs whose noise is larger than the effect, and a sort that spends a millisecond calibrating before sorting two hundred elements has lost by orders of magnitude.

It destroys reproducibility. A sort whose behaviour depends on a measurement taken at start-up is a sort that does different things on the same input on the same machine on different days. For a library that everything depends on, a performance profile that cannot be reproduced is worse than one that is one per cent off.

And the thresholds interact, as the section above sets out, so tuning one at run time means tuning a four-dimensional surface at run time — with each dimension’s optimum depending on where the others sit.

What is done instead is tuning at build time, by the people who ship the library, on the hardware of the day, once. That is the correct answer to all three objections and it explains the stability the previous section describes: the constants have not moved because moving them requires somebody to redo the four-dimensional measurement and defend the result against every workload in the world.

What a threshold is #

Four constants, four sweeps, and the same result four times: the shipped value minimises nothing.

That could be read as sloppiness and it is the opposite. A constant that minimised one counter would be a constant chosen by someone who measured one thing. Each of these sits at a point where several quantities have been traded against each other, and the trade is invisible without all of them. This site now has five, and it took the fifth to see that the insertion cutoff of 16 is well chosen rather than 0.9% wrong.

There is a second consequence and it is the more useful one. These constants are the algorithm. Timsort with minrun set to 1 and MIN_GALLOP set to infinity is a bottom-up merge sort with run detection; set minrun to $n$ and it is binary insertion sort. The same code, the same complexity class, and two completely different algorithms, distinguished by numbers that appear nowhere in the analysis.

The count somebody chose argued that choosing what to count decides what an analysis can conclude. This is the same argument one level in: choosing the thresholds decides what the algorithm does, and an analysis conducted at the level of asymptotic classes cannot see any of it.

That last point deserves the final word. Every figure on this site is drawn between $n = 32$ and $n = 65{,}536$, and the fits are stated over ranges starting at 256 for exactly the reason this essay has been circling. Real programs sort small arrays constantly — a few dozen elements, a few hundred — and in that range a library sort is almost entirely its thresholds. The asymptotic class describes what happens somewhere most sorting never reaches.