Rewrite binarysort()

[tim-one]

Feature or enhancement

Proposal:

I tried many things to speed listobject.c's binarysort(), but nothing really helped (neither code tweaks nor entirely different approaches).

However, I got annoyed enough at the ancient code to rewrite it 😉 Some specific annoyances:

• When sortslices were introduced, this was left with a slightly weird signature, mixing a semi-abstract sortslice argument with raw pointers into the key part.

• My aging eyes can often no longer see the difference between "l" and "1".

• While it's still idiomatic C to do pointer arithmetic "by hand", the code is clearer when written in a[index] style. At least for simple code like this, modern optimizing compilers should produce much the same machine instructions either way.

Has this already been discussed elsewhere?

No response given

Links to previous discussion of this feature:

No response

Linked PRs

• GH-116939: Rewrite binarysort() #116940

[tim-one]

BTW, an interesting phenomenon I didn't pursue to the end: when this code was first written, comparisons were enormously more expensive than moving pointers.

Since then, sorting grew optimizations to specialize for type-homogenous lists (checked at runtime whenever .sort() is invoked), and further specialized for common built-in types (int, float, str, ...). In such cases, comparisons are very much cheaper than, e.g., invoking __lt__ on Python objects.

The curious thing: on the best of these cases (e.g., list of ints or floats), sorting of randomized data is actually a bit faster now if the binary insertion sort is replaced with an ordinary insertion sort. I'm not entirely sure why. Ordinary insertion sort has O(n**2) worst-case and average-case comparison count. But binary insertion sort on randomized data remains significantly faster in cases where comparison remains very expensive.

So, at some point, comparisons get so cheap that O(n**2) comparisons don't much matter for n <= 64.

The mystery is why the binary version is ever slower on randomized data. The code is more complex than for ordinary insertion sort, but not much more complex. It just takes an add and a shift (both dirt cheap) to pick the next element to compare.

Best guess: randomized data is, on all platforms I've ever tested it on, the worst case for binary insertion sort. Despite that it requires about only half the amount of data movement of reverse-ordered input (any flavor of insertion sort's worst case for data movement), binary insertion sort finishes reverse-ordered data faster than randomized data. At least for the n <= 64 cases relevant here.

This appears to be due to branch-prediction failures. On randomized data, binary search is equally likely to take either branch, with no consistency from one test to the next. But ordinary insertion sort takes the same branch every time until the next value's final position is found (on randomized inputs, to insert the next value it will crawl over about half the already-sorted prefix), Its branch outcomes are highly predictable. A misprediction penalty can take longer than doing several more comparisons + correctly predicted branches, if the comparisons are cheap enough(*),

How to exploit this? Not sure. Also not sure it's worth any effort to try 😉

But, for the future: if CPython can get general __lt__ compares cheap enough, it would probably pay to drop minrun to, say, 32 (maybe even 16!) and use an ordinary insertion sort to pad out short natural runs. That would already have a small payoff for the cases .sort()'s runtime type specialization excels at.

(*) NOTE ADDED LATER: the reverse-ordered case doesn't suffer branch misprediction penalties for binary insertion sort. In those, the branch outcome is always "the element you're adding is less than the one you're comparing it to". Not suffering misprediction penalties more than makes up for the cost of doing twice the data movement of the randomized cases. Note that the number of compares done by binary insertion sort doesn't depend on the data values (so doesn't differ between the reverse-ordered and random-ordered cases - or from the already-sorted case, for that matter).

[tim-one]

The biggest difference between binary and regular insertion sort now is on sortperf.py's "%sort": take a sorted array of floats, and replace 1% of its entries, at random locations, with new random floats. When inserting the next element into a sorted prefix of length 2**k - 1, binary insertion sort always does exactly k comparisons. Regular insertion sort, in %sort, can usually get away with doing just 1 or 2.

[tim-one]

Pushed a new commit that lets you easily pick (by recompiling) whether binary or regular insertion sort is used. And, in the binary case, another switch to enable an experimental rewrite that tries to eliminate the innermost branch.

[pochmann3]

I've also experimented with variations of this, also targeting cases like sortperf.py's "%sort", to reduce the number of comparisons, and the results looked promising.

Simplest variation was just to not do a binary search right away, but first be optimistic and compare the to-be-inserted pivot value with the one right before it, a[ok-1]. In cases like %sort, that likely suffices and you're immediately done. Otherwise, do the binary search (but in a[0:ok-1] instead of a[0:ok]).

Another variation was a backwards exponential search, like compare with a[ok-1], a[ok-2], a[ok-4], a[ok-8], ..., and finish with a binary search in the reduced range.

And another idea was to use statistics and switch between strategies, similar to what you do in galloping-or-not. Like tracking the insertion point averages, and if they're usually in the middle, then use raw binary searches, but if they're usually towards the end, then use the optimistic or exponential variation, and if they're usually near the start, then do optimistic/exponential from the start. The strategy could be chosen either per new pivot element or just per binarysearch invocation.

[tim-one]

Ya, I tried a bunch of things like that. As listsort.txt notes, any compare done to try to exploit order has a negative payoff for randomly ordered data. There's nothing to exploit in the random case.

For sorting things like ints and floats, I saw fractions-of-a-percent timing differences (except, of course, in constructed-to-be-favorable cases). But when comparisons remained expensive, all such gimmicks obviously hurt (e.g., 10% slowdowns for sorting randomly-ordered Python objects wrapping ints with a dead simple int-comparing __lt__).

So I'm reluctant to do more than one "speculative" compare per run. Overall, they slow sorting random data, but there are no more than O(len(a)/minrun) of them (note that I recently changed count_run() to add another in the ascending-run case), and the potential payoffs can be huge on long runs.

Another thing I tried was to cut data movement. Since there are no more than 64 elements passed to binarysort, a byte vector can be used for indirect indexing.

ix = bytearray(i for i in range(n)) # but spelled in C

Then instead of accessing a[i], use a[ix[i]]. Sorting can proceed this way never moving keys or values, just single bytes in that vector. That cuts data movement by a factor of 8 (or 16 if values isn't NULL). The byte vector fits in a single line of an x86 L1 cache.

At the end, the keys (& values) are moved at most once each (via a "pass-and-a-half" over ix, chasing the cycles in the permutation it records).

It didn't help, and may have hurt a bit, until minrun was boosted to absurd values (like into the thousands - but then also moving to an indirect-indexing array of shorts). Then it helped a lot.

"The problem" seems to be that 64 is so small that 128 pointers also fit easily in L1 cache. Moving things around in L1 cache is blazing fast.

A similar idea was used to drive a number of plain-old mergesort variants, which are naturally O(n log n) worst-case for compares and data movement.

The ones I liked best used the byte vector to create "linked lists" of keys (the successor of rhe key at a[i] is a[ix[i]], with -1 acting as a NULL - end of list - sentinel). The first list is created from the run count_run() returns (ix[i] = i+1 across those at first). Code to merge linked lists is very brief and easy, requires no data movement, and only needs O(1) "extra" memory.

There are many ways to create runs to merge out of what remains (like top-down, bottom-up, keep looking for natural mini-runs), and strategies to merge them all. The best of these seemed faster than what we have now, but only slightly. I gave up, judging that it wasn't worth adding another large pile of code.

[pochmann3]

Yeah, I wasn't trying to improve random cases, only other cases while not hurting random ones. The thing is, currently you find the insertion position, use it to insert, and then throw it away. That feels like wasting information. If you keep insertion position statistics and only do something different than binary search if you detect a clear bias, then that should not affect the number of comparisons for random cases while allowing fewer comparisons for biased cases. And simple statistics should be cheap to do.

Oh I forgot the idea you gave me when you mentioned saving moves: Compare each pivot with the previous or next pivot.

• If the data is mostly ascending or mostly descending, then using the previous insertion point as the first M and thus comparing with the previous pivot might be good.
• Or insert in pairs, comparing the current pivot with the next (or rather with "the other current" pivot), then first inserting the larger pivot by moving prior elements by two positions, then inserting the smaller pivot further left.

[tim-one]

I won't believe any speculative change is harmless on random data before code proves it. I have a long history of failed actual-code attempts to justify skepticism 😉

Note that this is all in the context of Python's list.sort(), where the relevant arrays have no more than 64 elements, and count_run() has already identified the longest monotone prefix. If order remains to be exploited within the short array, it's at a micro-level.

"Number of comparisons" becomes increasingly irrelevant, in this context, the cheaper comparisons get. For example, sorting a list of floats has comparisons as cheap as they get. Sort specializes to a local function that just returns the C x < y applied to the machine doubles stored in the float objects. No method lookups, or layers of function calls, or even refcount fiddling, during the sort.

On a specific randomized array of 2**20 floats just now, binarysort did 19_651_636 compares. But plain insertion sort on the same array appeared to run a bit faster, despite doing 24_793_017 comparisons (over 25% more). The difference is entirely due to the number of comparisons needed to extend short runs.

What's the difference there? Plain insertion sort has predictable branches, but this version of binarysort shouldn't be doing any branch based on the comparison outcome:

            k = ISLT(pivot, a[M]);
            if (k < 0)
                goto fail;
            Py_ssize_t Mp1 = M + 1;
            R = k ? M : R;
            L = k ? L : Mp1;

The other difference is that plain insertion sort doesn't need the seemingly dirt cheap add and shift to compute the midpoint, or the ternary selection operations shown above. Its inner loop is cheaper that way, and in the presence of dirt-cheap comparisons too that can matter.

But for cases that involve the far more expensive Python-level __lt__, binarysort beats plain insertion sort by a wide margin on randomized data.

I understand that you're not suggesting changing "the" inner loop, but don't see a reason to hope that new cruft at a higher level wouldn't also hurt.

you find the insertion position, use it to insert, and then throw it away. That feels like wasting information

Its insertion position was used to cut the search range by half. For randomized data, what else could we learn from it? Well, nothing. Trying to find patterns will cost new cycles & branches, which won't pay on randomized data except by luck of the draw.

At the higher level of runs already extended to length (at least) minrun, sure, we do some speculative compares, because the possible payoffs are huge. But we don't enter "galloping mode" at all before some run wins 7 times in a row, which is more than binarysort ever does when moving a new element into place.

~sort is a good example of unexploited "micro-level" order. It's basically of the form [1.0, 2.0, 3.0, 4.0] * (n // 4). but all distinct objects, count_run() finds the ordered prefix of length 4, and asks binarysort to extend it. A binary insertion sort does worst at this, and an ordinary insertion sort better (mostly because all other instances of 4.0 belong at the end of the already-sorted prefix). But a linked-list bottom-up "tiny mergesort" does best. Total seconds just now to sort a list of that form with 2**25 elements:

1.43 binary insertion
1.28 plain insertion
1.17 linked-list bottom-up tinymerge

The difference is about 10% from one line to the next, so despite that there are no more than n/32 calls to the extend-short-run routine, it can still have significant effect on overall time even with comparisons as cheap as they get.

BTW, ~sort has always been a source of puzzles: when the code was first written, it was the only case that ran significantly faster (than CPython's previous sort) on some platforms but significantly slower on others. No good explanation for that was ever found.

BTW too, using pairs to try to cut the number of compares didn't help either, but did make the code more complicated. It takes a compare to order the next two candidate pivots. On randomized data, if we're lucky the smaller pivot will end up near the end of the sorted prefix, or if unlucky near the start. "On average" it will cut the search range for the larger pivot about in half. But the compare used to order the pivots to begin with could have been used instead to always cut the search range for the second pivot by half.

Although I expect that, as you suggest, using ordered pairs could reliably cut the amount of data movement inrsertion sort needs. If compares were always cheap, I'd pursue it.

[tim-one]

FYI, against my better judgment 😉 I tried just one scheme. If a pass placed the next entry at the start of the sorted prefix, set M=0 for the start of the next pass. Similarly if a pass put the next entry at the end of the prefix, check the new end first next. Provided we have an ascending sequence that belongs at the end, or a descending sequence that belongs at the start, it will take just one compare to put each new entry in place.

It doesn't complicate the code much - but then there's nothing I have that it sped, either. Of course inputs can be contrived where it always pays.

For random data the net payoff is negative, but a saving grace is that "last pass put the new entry at the start or the end" is unusual to begin with. So there are new branches checking for things that usually won't happen (but predictable branches because they usually won't happen).

Random data will trigger it by luck from time to time. When that happens, it will burn a compare to usually just cut the search range by 1. Mostly a waste of time - but not often triggered.

As expected, it hurts overall most obviously on randomized data with expensive compares.

[tim-one]

using pairs to try to cut the number of compares didn't help either

I should clarify that - as explained but not stressed, - this was in the context of a binary insertion sort. Working by pairs can definitely cut the number of comparisons in a regular insertion sort.