The code could typically be faster if it did what its comments imply it does: skip the expense of PyObject_RichCompareBool() entirely for the first pair of tuple elements. It actually always calls PyObject_RichCompareBool() on the first pair, and only if that says "not equal" does it use the faster ms->tuple_elem_compare to resolve "ok, so it's less than?".

Instead it could do the first pair before, and entirely apart from, the loop, along the lines of:

- Use ms->tuple_elem_compare to see whether u[0] < v[0]. If so, or if an error, we're done.

- Use ms->tuple_elem_compare to see whether v[0] < u[0]. If so, or if an error, we're done.

Else we can assume u[0] == v[0], and go on to compare u[1:] to v[1:] via a trivial variation of the current code.

In cases where the first pair does resolve it (common!), replacing a PyObject_RichCompareBool() with a ms->tuple_elem_compare can be significantly faster overall.

FYI, this is fallout from a StackOverflow mystery:

https://stackoverflow.com/questions/69468552/efficiency-of-sorting-by-multiple-keys-in-python/69610671#

The attached tupsort.py gives a simple. focused example. Typical output on my box:

float       3.10
(float,)   11.75
[float]    25.68

It's sorting a large list of floats. In the first line the list contains plain floats. In the second line, each float was wrapped in a 1-tuple. In the last line, wrapped in a singleton list.

Essentially any overhead of any kind is more expensive than merely comparing two floats in HW, so overhead is approximately everything here.  The tuple and list comparison functions are very similar, and the large advantage of "(float,)" over "[float]" is mostly due to that unsafe_tuple_compare() uses one less PyObject_RichCompareBool() call to resolve each compare (assuming that all floats in the list are distinct, which I didn't check, but is almost certainly the case).

Getting rid of its other PyObject_RichCompareBool() should yield another nice speed boost.

The pattern is worth addressing because tuples are routinely used as key= arguments to achieve multi-key sorting.

That's how Elliot did it in the original proposal: https://bugs.python.org/issue28685

Back then you pointed out that "Else we can assume u[0] == v[0]" isn't true for float('nan') values:
https://github.com/python/cpython/pull/582#issuecomment-285838656
https://github.com/python/cpython/pull/582#issuecomment-285841789

If you sort objects that always return True for both `<` and `==`, this would also have the opposite problem, considering tuple u smaller than v when it shouldn't.

That said, maybe the function could be optimized for known "well-behaving" types?

Stefan, I have scant memory of ever caring, but, if I did, I got over it ;-) 

>>> math.nan == math.nan
False
>>> {math.nan : 5}[math.nan]
5

That is, PyObject_RichCompareBool() takes object identity as overriding __eq__; that's why the dict lookup works. But this one doesn't:

>>> {math.nan : 5}[float("nan")]
... Traceback (most recent call last):
KeyError: nan

Although that may change too.

I used to care a little, but not at all anymore. There's no sense trying to _make_ sense of what sorting could possibly mean in the absence of a total ordering.

> If you sort objects that always return True for both `<` and `==`,

A case of "garbage in, garbage out" to me.

> this would also have the opposite problem, considering tuple u smaller
> than v when it shouldn't.

What justifies "shouldn't"? If u[0] < v[0], then by the definition of lexicographic ordering, u < v. But if u[0] == v[0], which apparently is _also_ the case, then the same definition says the ordering of u and v is inherited from the ordering of u[1:] and v[1:]. There's no principled way of declaring one of those possibly contradicting definitions "the right one".

> That said, maybe the function could be optimized for
> known "well-behaving" types?

A type is well-behaving to me if and only if it implements a total ordering. If a type doesn't, what you get is an implementation accident, and code relying on any specific accident is inherently buggy.

> What justifies "shouldn't"?

I based that on your old comments. Looked like tuple comparison results in sorting shouldn't differ from tuple comparison results elsewhere. I had actually proposed this exact method in a comment under your stackoverflow answer, but deleted it when I found that it had been discussed and discarded back then. But if it feels ok now, then good :-)

Stefan, I looked at that old PR and can't find anywhere I suggested that he change the unsafe_tuple_compare() logic. I just _asked_ him "I'm curious about what the patched Python prints for this program:".

And, in fact, that program showed that CPython was _already_ inconsistent with how NaNs were treated during tuple comparison (object identity overriding float.__eq__).

In any case, no, I have no problem at all with inferring "x == y" from "not (x < y) and not (y < x)".

Curious factoid: in [x, y].sort(), CPython never asks "x < y?". Because that's irrelevant ;-) The list is already sorted if and only if "not (y < x)". Which is how "x <= y" is spelled, because the implementation promises to do only "<" comparisons.

I misinterpreted you then, sorry. I guess also because Elliot shortly after retrated from the approach, saying he "rewrote unsafe_tuple_compare to move the less-than after the equality testing, to make sure it's 100% consistent".

I'd say the inconsistency the program showed was different. Yes, the xs got sorted differently than the ys, but the xs differed from the ys. The proposed method would change comparisons of *the same* tuples. You'd for example no longer have "sorted(tuples) == [min(tuples), max(tuples)]" for a list of two tuples.

Also curious factoid: I recently saw a case where despite the "only <" promise, sorting caused an "x > y" comparison (because "y < x" wasn't implemented).

(tiny note: tupsort.py does "range(2", should be "range(1" I think)

> Elliot shortly after retrated from the approach, saying he
> rewrote unsafe_tuple_compare to move the less-than after
> the equality testing, to make sure it's 100% consistent".

I remember at the time having no idea what he meant by that comment - and I still have no idea ;-)

> The proposed method would change comparisons of *the same* tuples.
> You'd for example no longer have
> "sorted(tuples) == [min(tuples), max(tuples)]"
> for a list of two tuples.

Since very little is defined about the result of sorted() in the absence of a total ordering (just that it's _some_ permutation of the original), that's not surprising. It's already the case anyway (using the released 3.10.0):

>>> ts = [(float("nan"), 1), (float("nan"), 1.0)]
>>> sorted(ts) == [min(ts), max(ts)]
False

> I recently saw a case where despite the "only <" promise, sorting
> caused an "x > y" comparison (because "y < x" wasn't implemented).

Sorting itself never asks for __gt__, only __lt__. What the _rest_ of the language does to implement __lt__ is out of sorting's control. For example, tuple.__lt__ and list.__lt__ go on to invoke __eq__ on contained elements. A more general subsystem in the language falls back on x.__gt__(y) if y.__lt__(x) isn't implemented. Sorting has no control over any of that.

> tupsort.py does "range(2", should be "range(1" I think)

Good catch - thanks! Repaired now :-)

Ok, I agree, the change only possibly "breaks" expectations that were already broken (including my naive sorted-vs-minmax).

Yes, I know sort itself only asks `<` (I've actually read most of its code and all its documentation). That's why I was irritated for a moment when I saw a `>`.

Hmm. What do you think about using "<" inside the loop for the remaining tuple elements as well? It's even less likely that both the first and the second elements are equal.

When the second elements differ, this saves 0.5 PyObject_RichCompareBool (average 1.5 "<" instead of one "==" and one "<").

When the second elements are equal, this costs 1 PyObject_RichCompareBool more (two "<" instead of one "==").

That's fewer PyObject_RichCompareBool calls if they're equal less than 1/3 of the time.

It's rare that an optimization is a _pure_ win. Some cases win, others lose. There's almost never "a proof" of net gain ending with "QED".

Of course it's dead easy to construct examples where "many duplicates in the first tuple position" rules, and even easy to construct realistic examples.

But, as you already said in the SO report, in those cases it's a better idea to do multiple single-key sorts instead of a single multiple-keys-in-a-tuple sort. The base sorting algorithm can exploit duplicates in a single-key sort - indeed, the more duplicates there are, the more benefit it can get.

The sorting HOWTO could do a service by discussing this for CPython's sorting algorithm - it's not obvious, and can have major effects.

In the meantime, I'm only aiming to speed tuple keys for cases where they're well-suited to begin with: the first tuple elements _are_ mostly distinct. Giving up a significant win for the relative handful of people who know how to exploit the algorithm is not worth it, to me, to avoid making suboptimal uses even less optimal.

I'm more a pragmatist than a Utopian :-;

Extending the idea to positions beyond the first is dubious on those grounds: if the first tuple positions in fact often match, then the optimization has already backfired. Time to admit defeat then, not double down on failed arrogance ;-)

One idea I'm playing with: keep track of how often, during a tuple-key sort, a compare _is_ resolved by the first elements. Then adjust `unsafe_tuple_compare()` to switch to "the other" approach when "the current" approach isn't working out.

I see you mentioned that PyObject_RichCompareBool(..., Py_EQ) might be faster for example because it checks identity. Why not do an identity check before the ms->tuple_elem_compare calls? Too expensive and rarely successful?
 
> Extending the idea to positions beyond the first is dubious on those grounds: if the first tuple positions in fact often match, then the optimization has already backfired. Time to admit defeat then, not double down on failed arrogance ;-)
 
I don't see that. First and second positions are quite different.

For example I sorted a million tuples where both first and second element are randomly chosen from a population of 10,000. So their amounts of duplication were the same. But these are the statistics from sorting:
- First position:   18,603,981 equality comparisons, 29.87% equal
- Second position:   5,556,203 equality comparisons,  0.09% equal
Many first positions matched, almost no second positions matched.

One more idea: What do you think of sorting lists of tuples (or tuple keys) in two stages?
1) Sort the list only by first position (comparing with only one tuple_elem_compare).
2) Identify equal-first-position-runs (with tuple_elem_compare) and sort each run independently (comparing only positions 1+).
Some experiments I did with this looked good, not sure if too off-topic to post here...

> I see you mentioned that PyObject_RichCompareBool(..., Py_EQ) might be
> faster for example because it checks identity.

For example, in tupsort.py replace

    xs = [random() for _ in range(length)]

with

    xs = ['z' * 100 for _ in range(length)]

Then sorting that directly is _slower_ than wrapping each string in a 1-tuple first. That's so today, and also so in the latest version of the PR (but not in the original PR code).

> Why not do an identity check before the ms->tuple_elem_compare calls? Too
> expensive and rarely successful?

It's a cheap test, but, ya, "rarely successful" outside of special cases. PyObject_RichCompareBool() already does that special-casing now, and the PR now adjusts to use PyObject_RichCompareBool(Py_EQ) instead when the pair of ms->tuple_elem_compare calls isn't paying off. It's enough that one part of the chain rarely pays off, but gets nearly all the potential benefit when it does pay off. Duplicating the special-casing would double the overhead with scant additional payoff when it pays.

> I sorted a million tuples where both first and second element
> are randomly chosen from a population of 10,000.

So you expect about 100 repetitions of each value in each tuple position.

> So their amounts of duplication were the same. But these are the
> statistics from sorting:
> - First position:   18,603,981 equality comparisons, 29.87% equal
> - Second position:   5,556,203 equality comparisons,  0.09% equal

Well, for any given fixed value in the first tuple position, you expect about 100 tuples total to have that value in the first position, and the second position in those contains a random sample (with repetition) of 100 elements out of 10,000. It's not surprising the 2nd positions are rarely equal _given_ that the universe has been reduced to the 100 tuples with the same first element.

In any case, I don't see the point to this exercise ;-)

BTW, don't overlook that tuple_elem_compare can _only_ be used on the very first elements of the tuples. The pre-scan developed no idea whatsoever of the types of tuple elements other than the first.


> One more idea: What do you think of sorting lists of tuples
> (or tuple keys) in two stages?

Primarily that I'm not looking for a term project here - I'm looking to get an easy win from simple changes to one function.

What's there in the PR now is designed to play well with how sorting works. When there are many duplicates, a merge will find about 7 comparison attempts in a row where the first elements are equal, and the code adjusts to use PyObject_RichCompareBool(Py_EQ) for at least all but the first compare. Galloping mode will continue with that for a brief time at the start, but probably soon hit a chain of cases all of which can be resolved solely with tuple_elem_compare calls, and the code adjusts to that too, never using PyObject_RichCompareBool(Py_EQ) again after the first time it sees that return "no, not equal".

OTOH, when there are no duplicates, PyObject_RichCompareBool(Py_EQ) isn't helpful, and in fact will never be called.

> 1) Sort the list only by first position (comparing with only one
>    tuple_elem_compare).

Not sure what that means, exactly. (the "with only one tuple_elem_compare" part; I know what it means to sort by the first position)

> 2) Identify equal-first-position-runs (with tuple_elem_compare) and
> sort each run independently (comparing only positions 1+).

What are you aiming at? There was no motivation given here.

> Some experiments I did with this looked good, not sure if too
> off-topic to post here...

Will, this issue report is about unsafe_tuple_compare(), so, ya, if the changes you envision aren't limited to that, I'd say you want to open a different issue report and a different PR :-)

> It's not surprising the 2nd positions are rarely equal _given_ that the universe has been reduced to the 100 tuples with the same first element.

Yes, exactly.

> In any case, I don't see the point to this exercise ;-)

Just to illustrate why I disagree with what I responded to there. I'm not convinced that many matches at the first tuple position are really an indication that there'll be many matches at the second position as well, so that one should "admit defeat" and that it's "arrogance" to hope for only few matches at the second position. I'd wager it's rather typical that the matching rate at the second position is significantly lower. If you sort people by last and then first name, I think you'd get the same effect as with my above random example, for the same reason. If you sort a set of 2D coordinates, you'll even *never* get matches at the second position. Even with that SO question's data and its massive duplication (especially at the second position) *and* its correlation between first and second position (since both "sorted(x)" and "x[::2]" are derived from the same x) and its 43% matching rate at the first position, there's still only 27% matching rate at the second position (lower than the 1/3 break-even point).

> BTW, don't overlook that tuple_elem_compare can _only_ be used on the very first elements of the tuples.

Yes, that's why I only talked about PyObject_RichCompareBool there.

> > 1) Sort the list only by first position (comparing with only
> >    one tuple_elem_compare).

> Not sure what that means, exactly. (the "with only one tuple_elem_compare" part;

Just wanted to make clear it wouldn't used two tuple_elem_compare or a PyObject_RichCompareBool.

> > 2) Identify equal-first-position-runs (with tuple_elem_compare)
> > and sort each run independently (comparing only positions 1+).

> What are you aiming at? There was no motivation given here.

Much fewer comparisons, especially PyObject_RichCompareBool comparisons. For example for sorting a million pairs with first/second element chosen from a population of 100,000, I get these numbers of comparisons (per element):

            current  groupsort
------------------------------
== first     18.60      none        (PyObject_RichCompareBool)
 < first     16.19     19.60        (tuple_elem_compare)
== second     2.41      2.36        (PyObject_RichCompareBool)
 < second     2.41      2.36        (PyObject_RichCompareBool)
------------------------------
total slow   23.42      4.72        (PyObject_RichCompareBool)
total fast   16.19     19.60        (tuple_elem_compare)
------------------------------
total        39.61     24.32

(With "current" I mean before your optimizations, which I can't test yet.)

> Will, this issue report is about unsafe_tuple_compare(), so, ya, if the changes you envision aren't limited to that, I'd say you want to open a different issue report and a different PR :-)

Ok, I might try that.

Stefan, thanks - I think I understand what you're driving at now.

You're (re)discovering that sorting by lexicographic ordering rules is _inherently_ suboptimal if list elements can only be compared "starting at index 0" each time. Not just tuples, but also, e.g., lists, byte arrays, and even strings. Any sequence type whose ordering derives from lexicographic generalization of its elements' ordering.

This is quite independent of whether or not CPython tries to exploit type homogeneity.

The usual(*) solution is indeed to exploit a kind of bucket sort instead, first sorting at elements' index 0 alone, saying all those elements with the same value at index 0 constitute "a bucket", and then applying the same idea to each bucket but sorting on index 1 instead. Where those in turn are partitioned into buckets equal at index 1, and those buckets are similarly each sorted on index 2. And so on, and so on.

No doubt that can be a big win, and even in the absence of the type homogeneity tricks. It's far beyond the scope of _this_ PR, though, and is really an entirely different approach.

I've thought about it at times, but it's "a real project" to do it right. In effect, it would implement an optimized generalization of the SO OP's "automagically convert multikey to multisort" wish.

Fine by me if someone pursues that, but I don't have the energy for it, nor much interest either in doing a half-hearted job of it.

I always expected that if it came up at all, it would be in the context of sorting lists of strings.  For example, consider:

    xs = ['x' * 10_000 + str(i) for i in range(1_000_000)]
    random.shuffle(xs)

Even with type homogeneity tricks, Python's sorting of the result is very far from optimal. Every single comparison starts by burning time skipping over the (at least) ten thousands equal characters at the start.

The "bucket sort" (or it could be viewed as a form of MSD radix sort) quickly discovers that all the characters at index 0 are equal, and also all those at index 1, ..., and all those at index 9999. The "real work" of sorting is then reduced to working on the (at most) 6 characters remaining.

(*) But I'm lying ;-) The actual usual solution is to use "multikey quicksort", because it's easy to code and works "in place". But it's not a stable sort. String sorting doesn't care about that, but sorting other kinds of sequences can care a lot.

Yes, I'm more familiar with the issue in the context of strings or lists. Your example of strings like "'x' * 10_000 + str(i)" looks like something I almost certainly used before as counterexample to someone's time complexity claim :-)

I the context of multi-criteria sort I might not have thought of it before, I guess because you usually don't have many criteria. But now this made me think we can take even more advantage of the existing tuple_elem_compare.

I the context of multi-criteria sort I might not have thought of it before, I guess because you usually don't have many criteria. But now the optimized tuple_elem_compare makes me think we can take even more advantage of it.

I think those type-specific optimized comparison functions are what I left out when I previously read the sort, that's why it was new to me. I just saw you also use powersort's merge strategy now. Kinda sad, I had seen you lament that your own strategy "remains hard to grasp why it's always correct now", while I think it's rather straightforward and had considered adding a little explanation in the doc.

Bucket sort is a name I considered, but I wrote two, so named them after their implementation (groupsort first used itertools.groupby).

To be concrete, here's an implementation of a full-blown, stable lexicographic sort based on "bucket refinement". `xs` is a list of sequences to be sorted in lexicographic order. The types of the sequences don't matter (lists, tuples, strings, ...). Indeed, since list elements are never compared against each other directly, they don't even have to be the same sequence type.

This is already faster in pure Python than list.sort() for cases like:

    xs = [random.choices(range(100000), k=random.randrange(5, 30))
          for i in range(1000000)]

However, for cases like strings of the form

    'x' * 10_000 + str(i)

it's very much slower than list.sort(), despite that it "should be" very much faster. That appears mostly due to the:

            t.sort(key=lambda x: x[k])
            xs[lo : hi] = t

lines. list.sort() doesn't accept `lo` and `hi` arguments, so sorting _just_ a slice requires copying that slice into a temp list, sorting the temp, then copying the sorted temp back in. So dealing with a single `x` position in the string prefixes effectively requires physically copying the entire list twice over - mad overhead to copy the list 20 thousand times.

While the need doesn't come up all that often, I'd support adding optional `lo` and `hi` arguments to `list.sort()`. This isn't the first time the lack has turned a slick approach into a timing disaster for me ;-)

About list.sort()'s merge strategy, I'm glad to be rid of the original. It's not just correctness, it's the effort of _reasoning_ about its consequences. It was about a full decade before the first proof was published of that it really is a worst-case O(N log N) sort. listsort.txt didn't contain a proof because the only proof attempts I had were so complicated not even _I_ found them compelling ;-)

Vincent Jugé in particular started at the other end, looking for a merge strategy that made proof straightforward instead of Byzantine. It's straightforward under the "powersort" strategy too, although it relies on "well known" results about approximations to optimal binary search trees.

    def lexisort(xs):
        buckets = [(0, len(xs), 0)]
        while buckets:
            lo, hi, k = buckets.pop()
            t = []
            for i in range(lo, hi):
                x = xs[i]
                if k >= len(x):
                    xs[lo] = x
                    lo += 1
                else:
                    t.append(x)
            t.sort(key=lambda x: x[k])
            xs[lo : hi] = t
            while lo < hi:
                pivotk = xs[lo][k]
                i = lo + 1
                while i < hi and xs[i][k] == pivotk:
                    i += 1
                if i - lo > 1:
                    buckets.append((lo, i, k + 1))
                lo = i
            assert lo == hi

New changeset 51ed2c56a1852cd6b09c85ba81312dc9782772ce by Tim Peters in branch 'main':
bpo-45530: speed listobject.c's unsafe_tuple_compare() (GH-29076)
https://github.com/python/cpython/commit/51ed2c56a1852cd6b09c85ba81312dc9782772ce

> This is already faster in pure Python than list.sort() for cases like:

Seems to depend on the system, it's slower on my laptop but faster on GCE:

Python 3.10.0 on my laptop:
 7.42 s  lexisort
 6.83 s  sort
 5.07 s  groupsort

Python 3.9.2 on Google Compute Engine:
 2.09 s  lexisort
 2.64 s  list.sort
 1.52 s  groupsort

This is my groupsort btw:

def groupsort(xs):
    xs.sort(key=itemgetter(0))
    start = 0
    n = len(xs)
    tail = itemgetter(slice(1, None))
    for i in range(1, n+1):
        if i == n or xs[i-1][0] < xs[i][0]:
            sublist = xs[start:i]
            sublist.sort(key=tail)
            xs[start:i] = sublist
            start = i