The request no price of memory would make

A guarantee that depends on an allocation read the C++ standard’s promise for std::stable_sort — at most $N \log_2 N$ comparisons if enough extra memory is available, $N (\log_2 N)^2$ otherwise — and found it bounds the one quantity that barely changes. It re-implemented the structure libstdc++ uses. The sort asks for a buffer of $\lceil n/2 \rceil$ elements and, when an allocation fails, takes half, and half again. The page swept the buffer the sort actually obtains. Comparisons stayed within a third of $n \log_2 n$ at every buffer, while element moves rose from 18.71 a key with the full request to 159 with none. Half the request cost 1.4% more moves; a quarter cost 22%.

Its closing section asked why the request is $\lceil n/2 \rceil$ at all. A library could treat the buffer as a parameter: ask for less on purpose and pay a known number of extra moves, or ask for more and merge out of place entirely. If memory had a stated price, in moves per element of buffer held, the sweep already contained the price schedule. The section proposed computing it, for several record sizes. It predicted that for small records the request could fall to about an eighth of the input for under a tenth more moves, which would make $\lceil n/2 \rceil$ “a constant somebody chose”.

The request is a constant somebody chose, and more plainly than predicted. It is not the cheapest buffer at any price of memory. The eighth the prediction named costs far more than it expected, and the record size it wanted to vary turns out not to matter.

Moves against the buffer, from none to all #

The sort is the earlier page’s re-implementation, function for function. Moves count every assignment of an element into the array or the buffer, with a swap charged as three, and every run checks its output sorted and stable. The buffer runs from none through $n/256$, $n/128$ and on by doubling to the $\lceil n/2 \rceil$ the library asks for. As the “ask for more” option, the library’s own out-of-place merge sort — insertion sort in chunks of seven, then merge passes back and forth between the array and a buffer of $n$ — is run over the whole input. That is the routine the library already runs inside each half when its request succeeds.

Most of the benefit of a buffer arrives with the first sliver of it. A buffer of a 256th of the input, 256 elements at 65,536 keys, takes the sort from 159 moves a key to 60.5. With no buffer every merge is done by rotations, and a rotation moves every element it passes over. With even a small buffer the short runs at the bottom of the recursion are merged through it, and only the long runs at the top still need rotations. Each doubling after that removes some of the remaining rotations, and by a quarter of the input almost none are left.

Then the curve does something the earlier page’s sweep could not show, because it stopped at the request. The step from a quarter to the ⌈n/2⌉ request saves 0.26 moves a key. The step from the request to a buffer of n saves 1.50. The larger buffer is worth more per element than the smaller step before it.

The reason is structural. With exactly its request, the library sorts each half through the buffer and then does one adaptive merge of the two halves, copying the left half into the buffer and merging it back: a pass of $n/2$ moves into the buffer and $n$ out. With a buffer of $n$ there is no final adaptive merge. The merge passes go back and forth between the array and the buffer across the whole input, and the copy the adaptive merge makes is never needed. The quarter-buffer path pays almost the same as the request, since its extra rotations are few. So the request buys little over a quarter, and a full buffer saves about a pass and a half of moves over the request.

Where the moves go #

The sort’s moves can be split by what made them: insertion sort in the small chunks at the bottom, element-by-element merging, copying runs into the buffer, and rotations where a run will not fit the buffer. At 65,536 keys the split explains every step of the curve.

With no buffer, 149.7 of the 159.1 moves a key are rotations — 510,040 of them, each shifting everything between two split points. With a 256th of the input the sort performs 442 rotations, and they cost 39.5 moves a key; merging now costs 14.0, because the short runs are merged element by element through the buffer rather than rotated, and copying them into the buffer costs 3.9. Each doubling of the buffer then removes rotations at the top of the recursion, where runs are longest: 70 rotations at a 64th, 9 at a 16th, none of any size at a quarter. By then the moves are 3.2 for insertion, 14.0 for merging, 1.0 for copying into the buffer, and 0.75 for the last shuffling a run too long for the buffer needs.

At the request the split changes shape. The library takes its other path: it sorts each half through the buffer and then merges the two halves with one adaptive merge. That final merge is a fifteenth pass of element-by-element merging where the quarter-buffer path does fourteen, and copying the left half into the buffer for it costs 0.5 a key. The rotations and most of the copying are gone, and a whole extra merge pass has arrived. The out-of-place sort with a buffer of $n$ does fourteen merge passes, copies nothing into a buffer it has not already merged into, and makes no rotations: 3.2 plus 14.0, and nothing else. The half-sized request pays for a merge pass that neither of its neighbours needs, and that pass is what puts it above the hull.

What each step up is worth #

Read as prices, the steps say how much memory is worth to the sort. Going from no buffer to 256 elements saves 25,233 moves for every element of buffer added: at 65,536 keys, 6.5 million moves for 256 elements. Each later doubling is worth less per element — by a factor of ten after the first step, and of two to three a step after that — down to 31.5 from an eighth to a quarter. Then the exchange collapses: the request’s extra quarter of the input saves 1.02 moves per element, and the next half saves 2.99. The steps do not shrink in order. A sequence that falls smoothly and then rises at the last step has a point above the line joining its neighbours, and that point is the request.

This is a small effect in moves — 0.33 of a move a key, 1.8% of what the request costs — and an unambiguous one in what it implies. The exchange rate nobody wrote down priced moves against comparisons for this collection’s sorts. Here the exchange is between moves and memory, and the library’s choice sits at the one point of the schedule no exchange rate selects.

The buffers some price would choose #

If a byte of memory held during the sort costs something, the cheapest buffer at that price minimises moves plus the price times the buffer. As the price falls from very high to zero, the cheapest buffer steps through the lower convex hull of the moves curve, and a buffer above that hull is never the cheapest, at any price.

Every buffer measured is on the hull except the one the library asks for. A buffer of a quarter of the input is the cheapest for memory priced between 2.3 and 31.5 moves per element held. Below 2.3 moves per element, a buffer of the whole input is cheapest. Between 31.5 and 68.8, an eighth; and so on down to no buffer at all, which is cheapest only when an element of buffer is worth more than 25,233 moves. The $\lceil n/2 \rceil$ request lies 0.33 moves a key above the straight line from a quarter to a buffer of $n$. At 16,384 keys it lies 0.34 above, and at 4,096 keys 0.36. For any price of memory, one of its neighbours does better, and at a price near 2.3 moves an element, where the two neighbours tie, both do.

So the request is not a compromise between cheap moves and cheap memory. A compromise lies on the curve of best trades, and this one lies inside it. The threshold somebody chose found constants in Timsort and introsort that were reasonable and never derived. This one is reasonable, since a buffer of half the input is enough for the library’s own adaptive merge. It is simply not the optimum of anything the sort is charged for.

Records large and small #

The proposal wanted the schedule “for several record sizes”, on the reasoning that large records make moves dear and should push the buffer up. The reasoning misses that large records make the buffer dear in exactly the same proportion.

The record size does not move the cheapest buffer at all. A record of 512 bytes costs 64 times as much to move as one of 8 bytes, and a buffer of 512-byte records holds 64 times as many bytes. Every term in the trade scales by the same factor, and the choice is unchanged. What the record size does change is how much the whole sort costs, and therefore how much the choice is worth. On large records the 0.33 moves a key the request wastes are 0.33 copies of a large record.

A buffer is not the only memory a stable sort can spend. The order equal keys keep made any sort stable by decorating each record with its arrival position, a word of memory a record that the program allocates and knows it has. That memory scales with the number of records and not with their size, so on large records it is cheap beside a buffer of the records themselves, and on small ones it is dear. It is the one memory in this family whose price does move with the record size.

The one term that does not scale is the comparisons, since comparing two records reads their keys and not the whole records. The comparisons would tilt the choice if the buffer changed them, and it barely does.

With any buffer at all, from 256 elements to the whole input, the sort makes between 15.81 and 15.86 comparisons a key at 65,536 keys. Only with none at all does it make more, 20.85, because the rotation-based merge finds each split point by binary search. So the comparisons tip the choice only between no buffer and a tiny one, and at every price where anything larger is chosen, the record size has nothing to act on.

The prediction, and the eighth #

The prediction said that for small records the request could fall to an eighth of the input for under a tenth more moves. An eighth costs 22% more moves than the request at every size measured: 22.90 a key against 18.71 at 65,536. A quarter costs 1.4% more, and would have met the prediction’s terms with room to spare. The prediction put the knee of the curve one halving too low. That is the same error the earlier page’s sweep could have shown and did not frame: from a quarter down, each halving of the buffer costs a fifth more moves, and above a quarter almost nothing.

The knee sits at a quarter for a reason the library’s structure makes plain. With a buffer too small for its request, the library halves the problem until the pieces fit the buffer, sorts them through it, and merges upward. A quarter of the input fits pieces of a quarter, so every merge below the top one has its shorter run inside the buffer, and only the final merge of two halves must split its runs and rotate. With an eighth, the merges at the top two levels no longer fit; with a sixteenth, three. Each halving below a quarter adds one level of the recursion that rotates, and each level costs about the same. Above a quarter there is no level left to rescue, which is why the request’s extra quarter saves almost nothing.

The more useful half of the proposal was the other option, “ask for more and merge out of place entirely”, which the prediction did not price. A buffer as large as the input saves 8% of the request’s moves. When memory is cheap — below about 2.3 moves an element held — it is the right request. When memory is dear, a quarter is. There is no price at which the half is.

What was measured and what was not #

Random distinct keys. Every run sorts a random permutation. On presorted input the library’s merges find their splits early and move little, and the buffer’s value is different. The sort the library ships and a run is a property of the input measured how much presortedness changes what a sort does; that measurement was not repeated here.

Moves as the cost of a buffer’s absence, memory as a price per element held. The price of memory here is a number per element for the duration of the sort. A real allocator’s price is not linear: small buffers come from a thread cache almost free, and large ones may fault in fresh pages. That would bend the hull and could move the quarter’s range; it cannot put the request back on the hull unless the price of going from a quarter to a half is lower per element than from a half to the whole, which an allocator whose large allocations cost more than small ones would not do.

The out-of-place option is the library’s own routine applied to the whole input. It is not a different algorithm. A library that asked for a buffer of $n$ would need a code path that took it — merge_sort_with_buffer over the whole range — which libstdc++ does not have; it asks for half and uses it as half.

The fast paths are not modelled. libstdc++ rotates trivially copyable types with memmove rather than by swaps, which cheapens the rotation path at small buffers. The earlier page flagged this. It would lower the left end of the curve and leave the right end, where the request sits, unchanged.

Still open: a request that knows the input’s runs #

Every buffer here is requested before the sort looks at the input. When galloping pays and the pattern that defeats the pattern found that sorts which look first can spend much less on presorted input. A merge whose runs are already long needs a buffer only as large as the shorter run it merges, and the longest merge in a natural merge sort is often far smaller than half the input.

The measurement that follows gives the sort one linear pass first to find the input’s natural runs and requests a buffer the size of the largest merge its schedule would perform. It compares the moves and the buffer with the fixed request of a quarter, a half and the whole, on random input and on inputs made of a few long runs. The prediction is that on random input the pass costs a little and saves nothing, since the runs are all short and the largest merge is half the input. On inputs of a few long runs, the request should fall to the size of the second-longest run, with moves no higher than the half-buffer sort’s. The question is how presorted an input must be before the pass pays for itself.