Speed sorting tuples whose first elements have the same type

[tim-one]

Feature or enhancement

Proposal:

As listobject.c says,

/* The idea is that most tuple compares don't involve x[1:]. */

in the comment before unsafe_tuple_compare().

But the code nevertheless copies the tuple object's all-purpose comparison function, by calling PyObject_RichCompareBool(... Py_EQ) on both tuples' elements first, in a loop, to find the first position where the tuples differ. It only benefits if the result of that loop is "OK, the first difference is at index 0".

But the comment is right in its intent: most times comparing the 0th elements on their own would resolve the question.. v[0] < w[0] on its own implies v < w; if not, w[0] < v[0] implies w < v, so again we could get out early ("no, v is not less than w"). And if not that either, only then do we need the greater expense of the loop the code now starts with, although we can start at index 1 instead of 0 (we've already established that the 0th elements are equal).

Sorting tuples is common (all kinds of "decorate" patterns do this), and I expect this would pay handsomely.

I'll write the code if nobody else beats me to it, but I think this is a high bang-for-the-buck change well suited to an aspiring core dev. The change is confined to a single small function, and while delicate is not truly difficult.

Has this already been discussed elsewhere?

This is a minor feature, which does not need previous discussion elsewhere

Links to previous discussion of this feature:

No response

[pochmann3]

Does this differ from this previous attempt which caused trouble and got reverted?

[tim-one]

Good catch! I had forgotten that we've been in this pit before. I don't have the will or energy remaining to resume the fight, so I'll just close this. Thanks!

[tim-one]

Closed.