[issue45530] Improve listobject.c's unsafe_tuple_compare()

Stefan Pochmann added the comment: > 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

[issue45530] Improve listobject.c's unsafe_tuple_compare()

Change by Tim Peters : -- resolution: -> fixed stage: patch review -> resolved status: open -> closed ___ Python tracker ___ ___

[issue45530] Improve listobject.c's unsafe_tuple_compare()

Tim Peters added the comment: 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 --

[issue45530] Improve listobject.c's unsafe_tuple_compare()

Tim Peters added the comment: 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,

[issue45530] Improve listobject.c's unsafe_tuple_compare()

Stefan Pochmann added the comment: 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

[issue45530] Improve listobject.c's unsafe_tuple_compare()

Tim Peters added the comment: 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,

[issue45530] Improve listobject.c's unsafe_tuple_compare()

Stefan Pochmann added the comment: > 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

[issue45530] Improve listobject.c's unsafe_tuple_compare()

Tim Peters added the comment: > 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

[issue45530] Improve listobject.c's unsafe_tuple_compare()

Stefan Pochmann added the comment: 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

[issue45530] Improve listobject.c's unsafe_tuple_compare()

Tim Peters added the comment: 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

[issue45530] Improve listobject.c's unsafe_tuple_compare()

Stefan Pochmann added the comment: 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

[issue45530] Improve listobject.c's unsafe_tuple_compare()

Stefan Pochmann added the comment: 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

[issue45530] Improve listobject.c's unsafe_tuple_compare()

Tim Peters added the comment: > 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

[issue45530] Improve listobject.c's unsafe_tuple_compare()

Stefan Pochmann added the comment: 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

[issue45530] Improve listobject.c's unsafe_tuple_compare()

Tim Peters added the comment: 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

[issue45530] Improve listobject.c's unsafe_tuple_compare()

Stefan Pochmann added the comment: > 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

[issue45530] Improve listobject.c's unsafe_tuple_compare()

Tim Peters added the comment: 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

[issue45530] Improve listobject.c's unsafe_tuple_compare()

Stefan Pochmann added the comment: 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

[issue45530] Improve listobject.c's unsafe_tuple_compare()

Change by Raymond Hettinger : -- nosy: +rhettinger ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe:

[issue45530] Improve listobject.c's unsafe_tuple_compare()

Change by Tim Peters : -- assignee: -> tim.peters ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe:

[issue45530] Improve listobject.c's unsafe_tuple_compare()

Change by Tim Peters : -- keywords: +patch pull_requests: +27345 stage: needs patch -> patch review pull_request: https://github.com/python/cpython/pull/29076 ___ Python tracker

[issue45530] Improve listobject.c's unsafe_tuple_compare()

Tim Peters added the comment: 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

[issue45530] Improve listobject.c's unsafe_tuple_compare()

Tim Peters added the comment: FYI, this is fallout from a StackOverflow mystery: https://stackoverflow.com/questions/69468552/efficiency-of-sorting-by-multiple-keys-in-python/69610671# -- ___ Python tracker

[issue45530] Improve listobject.c's unsafe_tuple_compare()

New submission from Tim Peters : 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