Two pivots and what they cost

In 2009 Vladimir Yaroslavskiy posted a quicksort variant to the OpenJDK mailing list. It partitions the array into three parts using two pivots in a single pass, rather than into two parts using one. Benchmarks showed it faster than the existing sort. In 2011 it became java.util.Arrays.sort for primitive types, where it remains, and it is one of the most-executed sorting implementations in the world.

Then the theory caught up. Wild and Nebel’s analysis in 2012 found that dual-pivot quicksort performs about $1.9\,n\ln n$ comparisons against classical quicksort’s $2\,n\ln n$ — about 5% fewer — and about $0.6\,n\ln n$ swaps against $0.33\,n\ln n$ — about 80% more.

Fewer of the thing textbooks count and nearly twice as many of the thing they do not. That is the entire subject of this essay, and it is the site’s oldest question — the count somebody chose — arriving in a case where a real decision was made on the answer.

Four counters, four answers #

Here is dual-pivot quicksort against the single-pivot introsort on random input at $n = 8{,}192$, on every counter this site has.

Dual-pivot wins four of five, and the fifth is the newest counter on the site.

That does not match Wild and Nebel’s swap figures, and the mismatch is instructive rather than a contradiction. Their comparison is between two partitioning schemes analysed in isolation. This is a comparison between two complete library sorts, one of which uses a Lomuto-style partition with a median-of-three pivot and a final insertion pass, and the other of which uses a five-element pivot selection and an insertion cutoff of seventeen. Almost none of the difference in the table above is the number of pivots.

That is not a defect in either measurement. It is the difference between the question “which partitioning scheme uses fewer swaps” and the question “which sort should Java ship”, and the second is the one that got answered in 2011.

Timsort’s 162 swaps against introsort’s 73,121 is worth a moment. A merge sort does not swap at all; the 162 are the in-place reversals of descending runs. The swap counter does not measure “data movement” — it measures one particular way of moving data, and merge sort’s movement is entirely in its 233,865 reads and its writes to the buffer.

Which is exactly the trap the count somebody chose is about, and it is worth restating in this specific form: a counter that returns zero for a whole family is not saying that family is free.

What three parts buys #

The mechanism is simple enough to state precisely. Choose two pivots $P_1 \le P_2$. One pass over the array puts every element into one of three regions: less than $P_1$, between the two, and greater than $P_2$. Recurse on all three.

The argument for it is about the number of elements each comparison eliminates. In single-pivot quicksort every element is compared against one pivot and lands in one of two parts, so one comparison places one element. In dual-pivot, an element less than $P_1$ takes one comparison; an element between the pivots takes two; an element above $P_2$ takes two. So the average is between one and two comparisons per element per level — worse per level — but there are $\log_3$ levels rather than $\log_2$, and $\log_3 n \times 1.5 < \log_2 n \times 1.0$ by a small margin.

That margin is the 5%. It is real, it is small, and it is entirely dependent on the pivots landing near the tertiles — which is why the JDK selects them by sorting five sampled elements rather than three, and why the sampling positions are at sevenths rather than at obvious fractions.

And the middle part is where it goes wrong. If the two pivots are equal, the middle part is every element equal to them, and the code skips recursing on it — a special case that turns duplicate-heavy input into a fast path. If the two pivots are merely close, the middle part is large, the recursion is unbalanced in a way the analysis does not model, and the cost climbs.

The pivot selection is most of the algorithm #

The JDK’s dual-pivot sort does not choose its pivots by sampling three elements, or five random ones. It samples five elements at positions spaced by $n/8 + n/64 + 1$ around the centre, sorts those five in place with an explicit network of comparisons, and takes the second and fourth as the pivots.

Every part of that is a decision.

Five rather than three, because two pivots need two order statistics rather than one, and estimating the tertiles from three samples is much worse than estimating the median from three.

Spaced by sevenths rather than evenly, so the samples are not adjacent — adjacent samples on data with local structure are correlated and the estimate is worse than the sample count suggests.

Sorted by an explicit sequence of comparisons rather than by a loop, because at five elements a loop’s overhead exceeds the comparisons and the sequence is short enough to write out.

Positions computed from the length, which means the pivot selection touches five widely separated cache lines before the partition touches anything — a prefetch pattern that is very good on a modern processor and was much less good in 2011.

Measured, that selection is 9 comparisons per partition — small against the $n$ comparisons the partition itself performs at the top level, and not small at all at the bottom, where a subarray of eighteen elements pays 9 comparisons to choose pivots and then partitions eighteen. This is why the insertion cutoff is 17: below that, the pivot selection costs more than the sort it is choosing pivots for.

The threshold and the pivot rule are chosen together, which is the point the threshold somebody chose makes about all four of this phase’s constants, arriving here in a particularly direct form: the cutoff of 17 is the size at which a five-element pivot selection stops paying, and if the rule sampled three the cutoff would be smaller.

The one claim the fit refused #

Every algorithm on this site declares a complexity class per input kind and the class is granted only if the measured counts fit it. Dual-pivot quicksort declares four and there were five inputs.

On eight distinct values in up to 16,384 elements, the spread against $n\log n$ is 1.624 and the tolerance is 1.6. The claim is withdrawn. Not by much — it misses by one and a half per cent of the tolerance — and the runner-up class is worse, so no class is granted at all.

The site’s rule is that a near miss is a miss, because the alternative is a tolerance that moves to accommodate the answer. This is the second time that rule has cost a claim this phase and the seventh time overall, and it is the first time the margin has been this thin.

What is happening is the middle part. With eight distinct values in 8,192 elements, the two sampled pivots are frequently equal — in which case the fast path fires and the middle is skipped — and frequently adjacent, in which case the middle part holds an eighth of the array and is recursed on with two pivots that will be equal next time. The cost is neither the fast path’s nor the general case’s; it is a mixture whose proportions change with $n$, and a mixture with $n$-dependent proportions is exactly what a single class cannot describe.

pdqsort has no such problem — its equal-element partition sweeps the block out in one pass and the class fitted is linear. The difference between the two is one branch: pdqsort asks whether the chosen pivot equals the element to the left of the range, and if so partitions the other way. Dual-pivot quicksort asks whether its two pivots are equal, which is a weaker test — it catches the case where the whole sample landed on one value and misses the case where the block of equals is large but the sample straddled it. Timsort has no such problem, because a merge does not care whether elements are equal. Introsort holds $n \log n$ at a spread of 1.104. Of the four, the one that struggles is the one whose whole mechanism is a middle region.

It is worth being clear that this is a small effect and that the withdrawal is a statement about this site’s tolerance rather than about Java’s sort being bad at duplicates. Dual-pivot takes 84,892 comparisons on the input where median-of-three quicksort takes 4,245,685 — it is fifty times better than the naive algorithm and about 45% worse than the best of the four. The refusal says only that no single class in this site’s vocabulary describes its growth across the range to the flatness the site requires, which is a narrower claim and the only one the measurement supports.

What decided it in 2011 #

The comparison count and the swap count point in opposite directions, so neither decided it. What decided it was benchmarks: dual-pivot quicksort was measurably faster on the JVM, on the hardware of 2011, on the JDK’s benchmark suite.

That is a defensible way to choose and it is not a measurement of the kind this site makes. A benchmark result is a single number that combines every counter with weights supplied by the hardware, and it has three properties worth naming.

It is not decomposable. A benchmark says which is faster; it does not say why, and it does not say what would happen if the weights changed. Wild and Nebel’s analysis exists because somebody wanted the why, and it arrived a year after the decision.

The weights change. A mispredicted branch cost about fifteen cycles in 2011 and costs about twenty now; a cache miss cost about two hundred and costs about three hundred; a swap cost roughly what it costs today. The ratios that made dual-pivot faster in 2011 are not the ratios of today’s hardware, and nothing in the JDK re-derives the choice.

It cannot be reproduced from a paper. This site’s numbers can be: every count in this essay is an integer that any machine will reproduce exactly. That is the whole reason the site counts rather than times, and the cost of that choice is precisely that it cannot answer the question the JDK actually faced.

That figure is the essay’s point in one picture, and it is a point about method rather than about Java. A decision made by weighing counters is a decision that expires, silently, as the weights drift — and the only defence is that the counters were recorded separately so the weighing can be redone.

The one input where it is clearly ahead #

For all the disagreement above, there is one column where dual-pivot quicksort wins on every counter at once, and it is worth naming because it is probably why the benchmarks came out as they did.

On reversed input at $n = 8{,}192$, dual-pivot takes 83,263 comparisons against introsort’s 166,216 — exactly half — and 23,572 swaps against 100,259, a factor of 4.3. On sorted input it takes 73,645 against 81,928.

The reason is the five-element pivot selection combined with three-way partitioning. On a reversed array the five samples are perfectly spaced order statistics of a known distribution, so the two pivots land almost exactly at the tertiles, and the first partition splits the array into three nearly equal parts with no wasted comparisons. Introsort’s median-of-three on the same input picks a good median and then partitions into two, and pays $\log_2$ levels where dual-pivot pays $\log_3$.

Reversed and nearly-sorted data is common — much more common than uniformly random data — and a sort that halves its comparisons on it is a sort that will look good in a benchmark suite. The measurement that decided the JDK’s choice was probably measuring the input distribution as much as the algorithm, which is not a criticism: a library should be chosen against the inputs it will see, and choosing against uniform random data would be choosing against an input almost nobody has.

What this site can add is the decomposition. The advantage is real, it is largest where the input has structure, it is smallest on random data, and it reverses entirely on duplicates — which is a much more useful description than one number.

Most of the idea’s value is lost to estimating the pivots #

Two of this essay’s measurements are the same comparison on two inputs, and setting them beside each other separates the mechanism from the estimate.

On reversed input dual-pivot takes 83,263 comparisons against introsort’s 166,216 — a factor of exactly two. On random input it takes 118,175 against 134,880 — a factor of 1.12.

Both algorithms are the same algorithms in both rows, so the difference between a factor of two and a factor of 1.12 is a property of the input, and the essay names it: on reversed input the five sampled positions are exact order statistics, so the two pivots land on the tertiles precisely. On random input they are a noisy estimate of them.

Read that as a decomposition and it says something the benchmark cannot. The three-way partitioning mechanism is worth a factor of two when its pivots are right, and pivot estimation gives back seven eighths of it. The 12% that dual-pivot quicksort actually delivers on unstructured data is what survives.

That also explains why the loss is so lopsided between the two algorithms, because both have noisy pivots on random input and only one of them collapses. A single-pivot sort estimates one order statistic from three samples; a dual-pivot sort estimates two from five, and two order statistics of a five-element sample are a much worse estimate of the tertiles than the median of three is of the median — the samples nearest the ends carry most of the error and both pivots depend on them. So the same amount of sampling noise moves dual-pivot’s split further from balanced, and it does so at every level of the recursion.

Which puts the JDK’s five-element network in a different light. It is usually read as care — five samples where three would do — and the arithmetic above says it is closer to the minimum: five is the fewest that gives two order statistics at all, and the mechanism it is estimating for is the one with the most to lose from getting them wrong.

So the lever nobody pulled is sample count. Raising it from five to seven or nine would recover part of the factor of two, and the reason to hesitate is the coupling this essay already identifies: a wider sample costs more comparisons per partition, which raises the size below which the pivot selection is not worth performing, which raises the insertion cutoff from seventeen. The two constants move together, and the value of moving them is bounded above by the factor of two the reversed-input row shows.

That bound is the useful part. Whatever a better pivot rule buys, it cannot buy more than the gap between 1.12 and 2.00 on random data, because the upper end is what the algorithm does with pivots that are exactly right. What randomising the pivot buys is the same separation for a single pivot — the rule and the estimate are different things, and only one of them is the algorithm — and the threshold somebody chose is why the two constants cannot be tuned apart.

Two more inputs, because which library sort is best is a question whose answer changes with the input before it changes with the counter.

The counting convention, one more time #

A last note on a detail that would change every number above.

This site counts swap(i, j) as one swap, two reads and two writes. That is a convention and it is stated in lib/count.js. A real implementation does not swap: it moves elements one at a time, holding one in a register, and a three-way partition’s data movement is a sequence of moves that no pairwise swap count describes well.

Under a move counter rather than a swap counter, dual-pivot quicksort’s advantage would look different again, and the direction is not obvious. The honest position is the one this site has held since the foundation: the counter is a choice, the choice is stated, and a conclusion that depends on it is a conclusion about the choice as much as about the algorithm.

Which is why five counters are reported here rather than one, and why none of the five is called the answer.

That last figure is the argument for the whole apparatus, and it is the sharpest version of it this phase has produced. Four algorithms, all of them $\Theta(n \log n)$ on this input by their own declarations, all of them audited and granted that class over a stated range — and their read counts span from 24,574 to 400,827, a factor of sixteen.

The class is what they have in common. Everything anybody would actually want to know is in the part the class discards, and that has been this site’s position since the first essay. What the practice field adds is that for the algorithms people actually run, the discarded part is not a constant factor of two or three. It is a factor of sixteen, and it changes sign depending on the input.