A guarantee that depends on an allocation

The sort the library ships set out the premise the essays on library sorts work from: the sorts that run when a program calls sort are policies rather than algorithms. Each is a structure plus a set of decisions, and each decision has a threshold somebody typed into a source file. The three essays since then measured Timsort’s runs, its galloping and pdqsort’s pattern-breaking. All three decisions are made on the data.

This page is about a decision made on something else. C++'s std::stable_sort asks the memory allocator for a buffer before it looks at a single key, and what it does next depends on the answer. The standard writes that dependence into the function’s contract:

If enough extra memory is available, N log₂(N) comparisons. Otherwise, at most N log₂²(N) comparisons.

That sentence is the only guarantee a C++ programmer has about the cost of a stable sort. It is conditional on an event the program does not control and is not told about. It names one counter. The question here is what the sentence leaves out — and on this collection’s usual instruments, the answer is almost everything that changes.

The library’s structure, counted #

What follows re-implements the structure of libstdc++'s recent releases, function for function, on an array of records carrying a key and their arrival position. Two counters run: comparisons, and element moves — every assignment of an element into the array or into the buffer, with a swap charged as three. Every run checks its own output, sorted by key and with every tie in arrival order.

The structure has three paths. stable_sort asks for a buffer of ⌈n/2⌉ elements. If it gets all of them, it sorts each half by a buffered merge sort — insertion sort in chunks of seven, then merge passes that bounce between the array and the buffer — and finishes with one merge that copies the shorter half into the buffer and merges back. If it gets a smaller buffer, it keeps halving the problem until the halves fit, and wherever a merge’s runs are both too long for the buffer it splits the merge by binary search and rotation. If it gets nothing, it sorts by insertion below fifteen elements and does every merge by binary search and rotation alone.

The allocator’s side is real too. get_temporary_buffer asks for the size wanted and, when the allocation fails, retries at half, and half again, down to nothing. So a program under memory pressure does not get an arbitrary buffer. It gets ⌈n/2⌉, ⌈n/4⌉, ⌈n/8⌉ and so on, and the sweep below uses exactly those sizes.

One merge, two ways #

The mechanism is visible in a single merge, before any sort is run.

A buffered merge copies the shorter run out, then writes every key once as the merge fills the gap. That is a move and a half per key, and one comparison per key, whatever the length.

A merge without a buffer cannot write a key anywhere except over another key. So it does something else. It takes the middle key of the longer run and finds by binary search where that key belongs in the other run. Then it rotates the block between the two cut points so that everything left of the cut is smaller than everything right of it. That leaves two independent merges of about half the size, and it recurses on both.

The binary searches are cheap in comparisons. Each costs a logarithm, and there are about as many searches as keys, but the searches get shorter as the pieces shrink, and the total stays near one and a half comparisons per key at every length on the plate. The rotations are not cheap. A rotation of a block moves every key in it, the blocks at each level of the recursion cover the whole merge, and there are about log₂ m levels. So every key is moved again at every level: moves grow as $m \log m$ while comparisons grow as $m$.

That is the entire story in one merge: without a buffer, comparisons stay linear and moves pick up a logarithm. Everything else on the page is this fact propagated through a sort.

The whole sort, at every buffer the allocator can hand back #

Read the two curves separately, because they are two different stories.

The comparisons barely notice the buffer. They are 15.81 per key with the full request and still 15.81 at 2,048 elements, one thirty-second of the keys. They pass 16 only at 64 elements of buffer and below, and with nothing at all they reach 20.85. From the best case to the worst that is 32% more comparisons, and almost all of it is paid in the last few halvings, where the buffer is tens of elements.

The moves notice every halving. Half the request costs 1.4% more moves. A quarter costs 22% more. At 1,024 elements the sort moves each key 40.76 times against 18.71, more than double. With none it moves each key 159 times, a factor of 8.5.

The shape of the moves curve is the one-merge plate summed over the sort. With a buffer of $B$, the levels of the recursion where runs are shorter than $B$ merge through the buffer at a move and a half per key. The levels above them — about $\log_2(n/B)$ of them — merge by rotation, and a rotation merge at a level costs moves proportional to its own depth of splitting. So the extra moves grow as the square of the number of levels the buffer cannot reach, $n \log^2(n/B)$ roughly. Each halving of the buffer adds one more such level and a little more than the last one did.

Here the page runs into measuring what an algorithm keeps: a sort’s working memory is part of its cost, and here that is sharpened into a price schedule. Every halving of the memory a stable sort is given has a price in moves. The price rises as the memory falls, and the comparison count reports none of it until the buffer is nearly gone.

The ceiling the standard allows #

With the buffer it asked for, the library makes 1,036,113 comparisons against a ceiling of 1,048,576. That is inside, by 1.2% — the insertion-sorted chunks of seven and the adaptive final merge buy a little. So the first clause of the standard is a real bound, met with little to spare.

The second clause is not a real bound on this structure at all. It allows 16,777,216 comparisons, and the structure makes 1,366,510 with no buffer, a twelfth of what it is permitted. On random input the ceiling is loose by a factor of twelve, and the looseness grows with $n$, because the ceiling has $\log^2 N$ in it and the comparisons have only $\log N$.

The quantity that does grow as $\log^2 N$ is on the plate too: the moves, 10.4 million with no buffer. They are the quantity the standard’s second clause appears to be describing, and it names the wrong counter for them. A reader who takes the standard at its word concludes that a stable sort under memory pressure makes up to sixteen times as many comparisons. In fact it makes a third more comparisons and eight and a half times as many moves.

Which of those matters depends on what is being sorted, and the exchange rate nobody wrote down computed that exchange rate for this collection’s sorts. On four-byte keys compared by one instruction, a move and a comparison cost about the same, and the fallback is roughly five times dearer overall. On five-hundred-byte records with a short key, a move costs a hundred times a comparison, and the fallback is eight and a half times dearer in almost exactly the currency the standard does not mention.

Where the work goes when the buffer does not come #

The split changes what the algorithm is. With its buffer, the sort is a merge sort in the ordinary sense: 80% of its moves and 85% of its comparisons are spent merging, and the rest are insertion sort on the chunks of seven and one copy into the buffer.

With no buffer, merging almost disappears as a cost. 94% of the moves are rotations. 72% of the comparisons are binary searches — the cuts the rotation merge uses to divide its work — and only 16% are the comparisons of merging proper. The sort is still called a merge sort, and it still produces the same stable order. It is spending its effort on a search-and-rotate procedure that exists only because there was nowhere to put a key.

The middle row shows the transition, and it is not a switch. With a buffer of 1,024 elements the merges low in the recursion still run through the buffer, and the rotations appear only in the top five levels. They already account for half the moves, while the binary searches account for 1,874 comparisons out of a million. That asymmetry is the whole page again, in one bar: the rotations are expensive in moves and the cuts that produce them are nearly free in comparisons.

The growth law, measured #

Divided by $n \log_2 n$, a count that grows as $n \log n$ draws a flat line, and a count that grows as $n \log^2 n$ draws a line that rises by a fixed amount for every doubling of the logarithm’s argument. The unbuffered moves rise by 1.42, 1.44, 1.45 and 1.45 per fourfold size — a straight line on this scale. That makes about $0.72\, n \log_2^2 n$ moves plus lower terms, and the class is read off the measured slope rather than presumed. Fitting a class to measurements asks for exactly this before a class is granted.

The unbuffered comparisons creep upwards too, from 1.21 to 1.32 per $n \log_2 n$ across the range, which is lower-order terms settling rather than a second logarithm: they rise by less each time, 0.03, 0.03, 0.02, 0.02. The buffered moves fall slightly, because the chunks of seven insertion-sorted at the bottom become a smaller share of the whole as the recursion deepens.

So the library has two cost laws, one for each answer the allocator can give. Which law a program is running under is decided at run time, by memory that other parts of the program happen to be holding, and nothing in the result says which one it was. A benchmark that sorts on a quiet machine measures the first law. A production system under memory pressure runs the second, and the comparisons it would log look almost identical.

The input on which the fallback wins #

Everything above was measured on random keys, and the fallback lost on all of it. It does not lose on every input.

On already sorted input the sort with no buffer is the cheaper one, by a factor of ten in moves and two in comparisons. Its merges begin by binary-searching for a cut, the search finds that every key of the left run already belongs before the right run’s middle, and the rotation it then performs is of an empty block. The whole merge becomes a handful of binary searches and no moves at all. The only moves left are the insertion sorts on the runs of fewer than fifteen keys at the bottom, which each read and write every key once.

The buffered sort cannot do that. Its final merge copies the shorter half into the buffer before comparing anything, and its merge passes bounce every key between the array and the buffer at every level, sorted or not: 1,095,384 moves to confirm an order that was already there. It also makes 589,822 comparisons against the fallback’s 302,795, because a buffered merge compares key by key until one side runs out and a rotation merge finds the same boundary by bisection.

Reversed input sits between. The fallback’s rotations are real, every block moves, and it makes three times the moves. It still makes half the comparisons, for the same bisection reason. Sixteen distinct values behave like random input with fewer distinct cuts, at 5.8 times the moves.

None of this rescues the fallback. A library cannot choose it for sorted input, because it does not know the input is sorted until it has looked, and Timsort — the sort a run is a property of the input measured — is the design that does look first, and makes $n - 1$ comparisons and no moves on the same input. What it shows is that the two paths are not one good algorithm and one degraded one. They are different algorithms with different best cases, and the standard’s contract describes them both with a single sentence about comparisons.

What the sentence would need to say #

The standard’s clause is written the way these essays have spent many pages arguing a cost should not be written: as one counter, with the conditions that decide it left implicit. A guarantee names its model is the thread here, and this is a clean example of it. The guarantee is correct — the library meets both ceilings. What it guarantees is not what changes.

A contract that described what a C++ program is actually running would need three things the current one lacks. It would state the buffer’s size, since “enough” is ⌈N/2⌉ in libstdc++ and is not given anywhere in the standard. It would state what happens between enough and none, because a program under memory pressure gets a power-of-two fraction of the request, not a clean zero. And it would name the moves, which with no buffer grow as $N \log^2 N$ where the comparisons grow as $N \log N$.

The order equal keys keep priced stability another way. Decorating each record with its arrival position makes any sort stable, at the cost of a word of memory per record. That decoration is also a buffer, one the program allocates itself and therefore knows it has. stable_sort offers the same property without asking the program for memory, and pays for it in a currency the program cannot see.

What is measured and what is modelled #

The counts are exact for the structure as re-implemented here, and that structure follows libstdc++'s source function by function: the ⌈n/2⌉ request, the chunks of seven, the fifteen-element insertion cutoff, the adaptive and resize paths, the rotation algorithm and the binary-search cuts. They are not a trace of a compiled binary.

Two things libstdc++ does are not modelled. For element types that can be copied as bytes, it rotates a one-element block with a single memory move rather than a chain of swaps, which lowers the rotation cost on small keys without changing its growth. And the allocation itself — including the failed attempts that precede a halved buffer — is not charged at all, though on a real system it is a system call and possibly a page fault.

Other libraries were not measured. libc++ and Microsoft’s implementation also ask for a buffer and also fall back to merging by rotation, under thresholds of their own, and nothing here says their numbers match these.

The plates also count moves and comparisons, not time. On a real machine a rotation is a sequential sweep that the memory system handles well, and a buffered merge touches two arrays at once. The count is not the time is the page on why counters and clocks can disagree, and nothing here claims the factor of 8.5 in moves is a factor of 8.5 in seconds.

Still open: what the stable sort should do with a buffer it can choose #

Every plate on this page takes the buffer as given. A library could instead treat it as a parameter: ask for less than ⌈n/2⌉ on purpose, trading moves for memory at a known rate, or ask for more and merge out of place entirely. The sweep above already contains the price schedule for the first choice. Half the request costs 1.4% in moves, a quarter costs 22%, and the curve is flat near the top and steep near the bottom.

The measurement that follows asks where a library should put its request if the price of memory were stated, in moves per element of buffer held. It computes the moves saved by each extra halving of the buffer against the memory that halving holds, and finds the buffer size at which the two cross, for several record sizes. The prediction is that for small records the request could fall to about an eighth of the input with under a tenth more moves. On that prediction the ⌈n/2⌉ request is a constant somebody chose, of the kind the threshold somebody chose found in Timsort and introsort: reasonable, never derived, and not the optimum of anything the standard asks for.