[issue28685] Optimizing list.sort() by performing safety checks in advance

STINNER Victor added the comment: New changeset 8017b804a06804793bcc0a7f734d8a846b0fe18a by Victor Stinner in branch 'master': bpo-28685: Fix compiler warning (GH-5423) https://github.com/python/cpython/commit/8017b804a06804793bcc0a7f734d8a846b0fe18a --

[issue28685] Optimizing list.sort() by performing safety checks in advance

Change by STINNER Victor : -- pull_requests: +5258 ___ Python tracker ___ ___

[issue28685] Optimizing list.sort() by performing safety checks in advance

ppperry added the comment: ... and I'm still trying to come up with even more pathological mutating cases -- ___ Python tracker ___

[issue28685] Optimizing list.sort() by performing safety checks in advance

Tim Peters added the comment: Thank you for giving this worthy orphan a home, Raymond! Victor, don't fret too much. The code is really quite simple, and at worst affects only `sorted()` and `list.sort()`. The vast bulk of review effort (of which it got enough) went into

[issue28685] Optimizing list.sort() by performing safety checks in advance

Raymond Hettinger added the comment: New changeset 1e34da49ef22004ca25c517b3f07c6d25f083ece by Raymond Hettinger (embg) in branch 'master': bpo-28685: Optimize sorted() list.sort() with type-specialized comparisons (#582)

[issue28685] Optimizing list.sort() by performing safety checks in advance

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

[issue28685] Optimizing list.sort() by performing safety checks in advance

Change by Raymond Hettinger : -- assignee: -> rhettinger ___ Python tracker ___

[issue28685] Optimizing list.sort() by performing safety checks in advance

STINNER Victor added the comment: I suggest to post-pone this optimization to Python 3.8. Faster list.sort() is nice to have, but I'm not sure that it's a killer feature that will make everybody move to Python 3.7. It can wait for 3.8. No core dev took the lead on

[issue28685] Optimizing list.sort() by performing safety checks in advance

Tim Peters added the comment: I agree it would be nice (very!) to get this in. Indeed, I'm surprised to see that this is still open :-( But who can drive it? I cannot. -- ___ Python tracker

[issue28685] Optimizing list.sort() by performing safety checks in advance

Raymond Hettinger added the comment: It would be really nice to have this into 3.7 -- nosy: +rhettinger priority: normal -> high ___ Python tracker

[issue28685] Optimizing list.sort() by performing safety checks in advance

Kirill Balunov added the comment: What is the current status of this issue and will it go into Python 3.7? -- nosy: +godaygo ___ Python tracker

[issue28685] Optimizing list.sort() by performing safety checks in advance

Tim Peters added the comment: @ppperry, I believe you're right - good catch! I expect the current patch would treat the NotImplemented return as meaning "the first argument is less than the second argument". I added a comment to the code (on github) suggesting an obvious fix for that.

[issue28685] Optimizing list.sort() by performing safety checks in advance

ppperry added the comment: - Doesn't youre skipping PyObject_RichCompareBool and directly getting tp_richcompare also mean that you bypass the NotImplemented checking? Thus, wouldn't this code, which raises a TypeError currently, silently work? class PointlessComparator: def

[issue28685] Optimizing list.sort() by performing safety checks in advance

Elliot Gorokhovsky added the comment: OK, I added the safety check to unsafe_object_compare. I verified that it matches the current implementation on all the tests proposed in this thread. -- ___ Python tracker

[issue28685] Optimizing list.sort() by performing safety checks in advance

Elliot Gorokhovsky added the comment: I am embarrassed! That's why I said IIRC... I remembered that either RichCompare calls RichCompareBool, or the other way around, and I was too lazy to check :) I did remember about do_richcompare, though! On Sat, Mar 11, 2017 at 10:07 PM Tim Peters

[issue28685] Optimizing list.sort() by performing safety checks in advance

Tim Peters added the comment: Elliot, PyObject_RichCompareBool calls PyObject_RichCompare. That in turn does some checks, hides a small mountain of tests in the expansions of the recursion-checking macros, and calls do_richcompare. That in turn does some useless (in the cases you're aiming

[issue28685] Optimizing list.sort() by performing safety checks in advance

Elliot Gorokhovsky added the comment: Eryk Sun: Thanks for your detailed response. I'm curious, though: can you figure out why those other two examples *didn't* fail? It's driving me crazy! For reference: https://bugs.python.org/msg289435 -- ___

[issue28685] Optimizing list.sort() by performing safety checks in advance

Elliot Gorokhovsky added the comment: Ya, that makes sense... I just don't get why it's faster at all, then! Because if we add the (v==w) check, and the tp_richcompare check, how is unsafe_object_compare any different from PyObject_RichComareBool? Is it that we're saving function calls?

[issue28685] Optimizing list.sort() by performing safety checks in advance

Tim Peters added the comment: The impact would be small: it would add one (or so) pointer-equality compare that, in practice, will always say "yup, they're equal". Dirt cheap, and the branch is 100% predictable. -- ___ Python tracker

[issue28685] Optimizing list.sort() by performing safety checks in advance

Elliot Gorokhovsky added the comment: It was a release build -- it would blow up in a debug build. Now, regarding the fix you propose: I'll benchmark it tomorrow. If the impact is small, I agree that it would be an elegant fix. If not, however, perhaps we just have to get rid of

[issue28685] Optimizing list.sort() by performing safety checks in advance

Eryk Sun added the comment: > assignment of "__lt__" change the value of the tp_richcompare slot? Yes. CPython doesn't implement individual dispatching of the rich-comparison functions. There's a single tp_richcompare slot, so overriding one rich comparison forces the use of

[issue28685] Optimizing list.sort() by performing safety checks in advance

Tim Peters added the comment: Elliot, did you run the example in a release build or a debug build? I'm wondering why this: assert(v->ob_type == w->ob_type && v->ob_type->tp_richcompare != NULL && v->ob_type->tp_richcompare == compare_funcs.key_richcompare); didn't blow

[issue28685] Optimizing list.sort() by performing safety checks in advance

Elliot Gorokhovsky added the comment: On Sat, Mar 11, 2017 at 9:01 PM Tim Peters wrote: > > Elliot, I don't care if the example behaves differently. Although someone > else may ;-) > > The only things `.sort()` has ever tried to guarantee in the presence of > mutations

[issue28685] Optimizing list.sort() by performing safety checks in advance

Tim Peters added the comment: Elliot, I don't care if the example behaves differently. Although someone else may ;-) The only things `.sort()` has ever tried to guarantee in the presence of mutations (of either the list or the elements) during sorting are that (a) the implementation won't

[issue28685] Optimizing list.sort() by performing safety checks in advance

Tim Peters added the comment: @ppperry, I have no idea what the bulk of the code in typeobect.c is trying to do. -- ___ Python tracker ___

[issue28685] Optimizing list.sort() by performing safety checks in advance

Elliot Gorokhovsky added the comment: I just ran it. With the patched interpreter, I get no error. With the unpatched interpreter, I get ValueError. :(. -- ___ Python tracker

[issue28685] Optimizing list.sort() by performing safety checks in advance

ppperry added the comment: Wouldn't the assignment of "__lt__" change the value of the tp_richcompare slot? That seems to be what the code in Objects/typeobject.c is doing with the update_slot method and the related helper functions. -- ___ Python

[issue28685] Optimizing list.sort() by performing safety checks in advance

Tim Peters added the comment: I haven't tried the example, but at this point I'd be surprised if it failed. The caching here isn't at level of `__lt__` but at the higher level of (invisible from Python code) a type's tp_richcompare slot. A heap type - regardless of whether it derives from a

[issue28685] Optimizing list.sort() by performing safety checks in advance

ppperry added the comment: What about if one of the relevant comparison functions is implemented in C? class WackyComparator(int): def __lt__(self, other): elem.__class__ = WackyList2 return int.__lt__(self, other)

[issue28685] Optimizing list.sort() by performing safety checks in advance

Elliot Gorokhovsky added the comment: Actually, I just ran this in the patched interpreter, and it worked! It printed: zebra gizmo zebra gizmo zebra gizmo zebra gizmo zebra gizmo zebra gizmo zebra gizmo Inspired by the above result, I ran your counterexample (below) to see if it would work as

[issue28685] Optimizing list.sort() by performing safety checks in advance

ppperry added the comment: And what about even wackier code like this? class A(int): def __lt__(self, other): print("zebra") A.__lt__ = A.__false_lt__ return int.__lt__(self, other) __true_lt__ = __lt__ def

[issue28685] Optimizing list.sort() by performing safety checks in advance

Elliot Gorokhovsky added the comment: Yup, I was completely wrong. If your classes were defined in pure-Python, this would raise an exception (since the pure-Python operators/functions check for bad types, correct me if I'm wrong). However, if you defined your compares at the C API level, you

[issue28685] Optimizing list.sort() by performing safety checks in advance

ppperry added the comment: > > Elliot Gorokhovsky added the comment: > > Your code changes __class__, not type, which would remain equal to > "instance". (my understanding, could be wrong). The docs say the > following: > Nope: class A:pass class B:pass a = A() a.__class__ = B

[issue28685] Optimizing list.sort() by performing safety checks in advance

Elliot Gorokhovsky added the comment: Your code changes __class__, not type, which would remain equal to "instance". (my understanding, could be wrong). The docs say the following: https://docs.python.org/3.7/reference/datamodel.html > Like its identity, an object’s type is also unchangeable.

[issue28685] Optimizing list.sort() by performing safety checks in advance

ppperry added the comment: Does this work with wacky code like this? @functools.total_ordering class ClassAssignmentCanBreakChecks(): def __init__(self, i): self._i = i def __lt__ (self, other):

[issue28685] Optimizing list.sort() by performing safety checks in advance

Elliot Gorokhovsky added the comment: On Fri, Mar 10, 2017 at 12:26 AM Serhiy Storchaka wrote: > > Serhiy Storchaka added the comment: > > The issue shouldn't be closed until it resolved or rejected. > Ya, sorry about that. This is my first time contributing. > > I

[issue28685] Optimizing list.sort() by performing safety checks in advance

Serhiy Storchaka added the comment: The issue shouldn't be closed until it resolved or rejected. I like the idea, and benchmarking results for randomized lists look nice. But could you please run benchmarks for already sorted lists? -- nosy: +serhiy.storchaka stage: resolved -> patch

[issue28685] Optimizing list.sort() by performing safety checks in advance

Changes by Elliot Gorokhovsky : -- pull_requests: +479 ___ Python tracker ___

[issue28685] Optimizing list.sort() by performing safety checks in advance

Elliot Gorokhovsky added the comment: Will post the final version of this patch as a pull request on Github. -- stage: -> resolved status: open -> closed ___ Python tracker

[issue28685] Optimizing list.sort() by performing safety checks in advance

STINNER Victor added the comment: list.sort() is a very sensitive function. Maybe (dummy idea?), you may start with a project on PyPI, play with it and try it on large applications (Django?). And come back later once it's battle tested? -- ___

[issue28685] Optimizing list.sort() by performing safety checks in advance

Elliot Gorokhovsky added the comment: Oh wait... uh... never mind... we want "faster" to refer to total time taken, so 1-def/ref is indeed the correct formula. I just got confused because perf outputs ref/dev, but that doesn't make sense for percents. --

[issue28685] Optimizing list.sort() by performing safety checks in advance

Elliot Gorokhovsky added the comment: So thanks for pointing out that perf has a --compare_to option: it turns out I had calculated the times wrong! Specifically, I had used (ref-dev)/ref while I should have used ref/dev which is what perf --compare_to uses. Anyway, the actual times are

[issue28685] Optimizing list.sort() by performing safety checks in advance

Changes by Elliot Gorokhovsky : Added file: http://bugs.python.org/file45508/fastsort.patch ___ Python tracker ___

[issue28685] Optimizing list.sort() by performing safety checks in advance

Elliot Gorokhovsky added the comment: On Mon, Nov 14, 2016 at 10:32 AM STINNER Victor wrote: > You can use perf timeit --compare-to to check if the result is significant > or not, and it displays you the "N.NNx faster" or "N.NNx slower" if it's > significant. > Will do

[issue28685] Optimizing list.sort() by performing safety checks in advance

STINNER Victor added the comment: Maybe we should investigate more optimizations on specialized lists. PyPy uses a more compact structure for lists of integers for example. Something like compact strings, PEP 393, of Python 3.3, but for lists.

[issue28685] Optimizing list.sort() by performing safety checks in advance

Elliot Gorokhovsky added the comment: Sure, if it compiles without that def, I'll remove it from the patch. I added it because I did all the development in an extension module, which also included Python.h, but for some reason it gave me a "function implicitly defined" error for using Py_ABS.

[issue28685] Optimizing list.sort() by performing safety checks in advance

Julien Palard added the comment: Hi Elliot, nice spot! Why are you redefining Py_ABS, which looks already defined in `pymacro.h` included itself by `Python.h`? I'm not fan of undefining it later, it may surprise someone later expecting it to be there. I tried to compile without your

[issue28685] Optimizing list.sort() by performing safety checks in advance

Changes by Elliot Gorokhovsky : -- nosy: +tim.peters ___ Python tracker ___ ___

[issue28685] Optimizing list.sort() by performing safety checks in advance

New submission from Elliot Gorokhovsky: When python compares two objects, there are many safety checks that have to be performed before the actual comparison can take place. These include checking the types of the two objects, as well as checking various type-specific properties, like