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

[STINNER Victor]

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


--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[STINNER Victor]

Change by STINNER Victor :


--
pull_requests: +5258

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[ppperry]

ppperry  added the comment:

... and I'm still trying to come up with even more pathological mutating cases

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Tim Peters]

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 dreaming up pathological cases (like mutating 
list elements, and even list element comparison methods, _while_ a sort was in 
progress).

I confess I didn't press for more benchmarks, because I don't care about more 
here:  the code is so obviously a major speed win when it applies, it so 
obviously applies often, and the new worst-case overhead when it doesn't apply 
is so obviously minor compared to the cost of a sort (`len(list)-1` wasted 
C-level pointer equality compares).  The only real value of timing benchmarks 
to me here was as a gross sanity check, and enough of those were run to confirm 
that all the preceding were qualitatively on target.  It really doesn't matter 
at all, e.g., whether the best cases are 2 times faster or 10 times faster, or 
the truly pathologal worst cases 10% slower or 20% slower.  Regardless, it's as 
close to a pure win as just about anything can be.

Nevertheless ... if this brings a major player's server to its knees, blame 
Raymond ;-)

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Raymond Hettinger]

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)
https://github.com/python/cpython/commit/1e34da49ef22004ca25c517b3f07c6d25f083ece


--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Raymond Hettinger]

Change by Raymond Hettinger :


--
resolution:  -> fixed
stage: patch review -> resolved
status: open -> closed

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Raymond Hettinger]

Change by Raymond Hettinger :


--
assignee:  -> rhettinger

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[STINNER Victor]

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 this non-trivial issue, and IMHO it's getting too 
late for 3.7.

It see that Serhiy started to review the change and asked for more benchmarks. 
Serhiy would be a good candidate to drive such work, but sadly he seems to be 
busy these days...

While such optimization is nice to have, we should be careful to not introduce 
a performance regressions on some cases. I read quickly the issue, and I'm not 
sure that it was fully carefully reviewed and tested yet. Sorry, I only read it 
quickly, ignore me if I'm wrong.

Well, if someone wants to take the responsability of pushing this right now, 
it's up to you :-)

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Tim Peters]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Raymond Hettinger]

Raymond Hettinger  added the comment:

It would be really nice to have this into 3.7

--
nosy: +rhettinger
priority: normal -> high

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Kirill Balunov]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Tim Peters]

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.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[ppperry]

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 __lt__(self, other):
return NotImplemented
[PointlessComparator(),PointlessComparator()].sort()

... ... ...

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Elliot Gorokhovsky]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Elliot Gorokhovsky]

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  wrote:

>
> 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 at) tests and finally gets around
> to invoking tp_richcompare.  Your patch gets to that final step at once.
>
> I'm surprised you didn't know that ;-)
>
> --
>
> ___
> Python tracker 
> 
> ___
>

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Tim Peters]

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 at) tests and finally gets around to 
invoking tp_richcompare.  Your patch gets to that final step at once.

I'm surprised you didn't know that ;-)

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Elliot Gorokhovsky]

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

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Elliot Gorokhovsky]

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? (PyObject_RichCompareBool calls
do_richcompare, so it's one extra call IIRC).

On Sat, Mar 11, 2017 at 9:32 PM Tim Peters  wrote:

>
> 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 
> 
> ___
>

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Tim Peters]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Elliot Gorokhovsky]

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 unsafe_object_compare entirely? The
common use cases would still work just fine, and maybe we could add a case
for bytes or something to compensate for the loss.

On Sat, Mar 11, 2017 at 9:12 PM Tim Peters  wrote:

>
> 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 up (in `unsafe_object_compare`).
>
> If that does blow up in a debug build, it suggests "a fix":
> unconditionally check whether the tp_richcompare slot is the expected
> value.  If not, use `PyObject_RichCompareBool(v, w, Py_LT)` instead.
>
> --
>
> ___
> Python tracker 
> 
> ___
>

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Eryk Sun]

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 slot_tp_richcompare. For built-in types this 
incurs the performance penalty of using a wrapper_descriptor for the other rich 
comparisons. For example, overriding F.__lt__ forces calling float.__gt__ for 
the greater-than comparison. 

Before:

>>> F() > 1

Breakpoint 0 hit
python37_d!float_richcompare:
`6099d930 4489442418  mov dword ptr [rsp+18h],r8d
  ss:0056`cefef280=a1670058
0:000> kc 3
Call Site
python37_d!float_richcompare
python37_d!do_richcompare
python37_d!PyObject_RichCompare
0:000> g
False

After:

>>> F.__lt__ = lambda a, b: 0
>>> F() > 1

Breakpoint 0 hit
python37_d!float_richcompare:
`6099d930 4489442418  mov dword ptr [rsp+18h],r8d
  ss:0056`cefef0a0=a39d7c70
0:000> kc 9
Call Site
python37_d!float_richcompare
python37_d!wrap_richcmpfunc
python37_d!richcmp_gt
python37_d!wrapper_call
python37_d!_PyObject_FastCallDict
python37_d!call_unbound
python37_d!slot_tp_richcompare
python37_d!do_richcompare
python37_d!PyObject_RichCompare

The __gt__ wrapper_descriptor gets bound as a method-wrapper, and the 
method-wrapper tp_call is wrapper_call, which calls the wrapper function (e.g. 
richcmp_gt) with the wrapped function (e.g. float_richcompare). The object ID 
in CPython is the object address, so we can easily get the address of the 
__gt__ wrapper_descriptor to confirm how these C function pointers are stored 
in it:

>>> id(vars(float)['__gt__'])
2154486684248

0:001> ln @@(((PyWrapperDescrObject *)2154486684248)->d_base->wrapper)
(`60a20580)   python37_d!richcmp_gt   |
(`60a205c0)   python37_d!slot_tp_finalize
Exact matches:
python37_d!richcmp_gt (struct _object *, struct _object *, void *)

0:001> ln @@(((PyWrapperDescrObject *)2154486684248)->d_wrapped)
(`6099d930)   python37_d!float_richcompare   |
(`6099e6f0)   python37_d!float_getzero
Exact matches:
python37_d!float_richcompare (struct _object *, struct _object *, int)

--
nosy: +eryksun

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Tim Peters]

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 up (in `unsafe_object_compare`).

If that does blow up in a debug build, it suggests "a fix":  unconditionally 
check whether the tp_richcompare slot is the expected value.  If not, use 
`PyObject_RichCompareBool(v, w, Py_LT)` instead.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Elliot Gorokhovsky]

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 (of either the list or the elements) during sorting are that (a)
> the implementation won't segfault; and, (b) the list at the end is _some_
> permutation of the input list (no elements are lost or duplicated).
>
> If crazy mutation examples can provoke a segfault, that's possibly "a
> problem" - but different results really aren't (at least not to me).
>
>
That's great to hear. (Of course, one could always remove
unsafe_object_compare from the patch and keep the rest, but that would be a
real shame). I don't think segfaults are possible if the code is
pure-Python, because all the builtin/stdlib functions type-check anyway, so
you would just get an exception. Right? Of course, using the C API you
could probably provoke segfaults, but there are much easier ways to
segfault using the C API :).

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Tim Peters]

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 segfault; and, (b) the list at the end is _some_ 
permutation of the input list (no elements are lost or duplicated).

If crazy mutation examples can provoke a segfault, that's possibly "a problem" 
- but different results really aren't (at least not to me).

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Tim Peters]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Elliot Gorokhovsky]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[ppperry]

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 tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Tim Peters]

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 C-level or Python-level type - has to 
be prepared for methods to pop into existence, change, or vanish at (almost) 
any time.  So its tp_richcompare has to be defensive itself.  For example:

>>> class F(float):
... pass
>>> a = F(2)
>>> b = F(3)
>>> a < b
True

Is F.tp_richcompare the same as float.tp_richcompare?  We can't tell from 
Python code, because tp_richcompare isn't exposed.  But, _whatever_ 
F.tp_richcompare is, it notices when relevant new methods are defined (which 
float.tp_richcompare emphatically does not); for example, continuing the above:

>>> F.__lt__ = lambda a, b: 0
>>> a < b
0
>>> del F.__lt__
>>> a < b
True

That said, I know nothing about how comparison internals changed for Python 3, 
so I may just be hallucinating :-)

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[ppperry]

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)

class WackyList1(list):pass
class WackyList2(list):
def __lt__(self, other):
raise ValueError
lst =
list(map(WackyList1,[[WackyComparator(3),5],[WackyComparator(4),6],[WackyComparator(7),7]]))
random.shuffle(lst)
elem = lst[-1]
lst.sort()

This code raises ValueError, and caching seems like it would cache the
comparator for WackyList1 objects, which is the same as the comparator for
'list' objects -- and midway through comparison, one of them changes type
to WackyList2, which has its own (broken) comparison function.

Python is very very dynamic ...

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Elliot Gorokhovsky]

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 well:
from random import *
class ClassAssignmentCanBreakChecks():
def __init__(self, i):
self._i = i
def __lt__ (self, other):
print('gizmo')
last.__class__ = OrdinaryOldInteger
return self._i < (other._i if hasattr(other, '_i') else other)

class OrdinaryOldInteger:
def __init__(self, i):
self._i = i
def __lt__(self, other):
print('rocket')
return self._i < (other._i if hasattr(other, '_i') else other)
lst = [ClassAssignmentCanBreakChecks(i) for i in range(10)]
shuffle(lst)
last = lst[-1]
lst.sort()

And it did! It printed:
gizmo
gizmo
gizmo
gizmo
gizmo
gizmo
gizmo
gizmo
gizmo
gizmo
gizmo
gizmo
gizmo
gizmo
gizmo
gizmo
gizmo
gizmo
gizmo
rocket
rocket
rocket

Note the "rocket" prints at the end; those could not have printed if the
compare method didn't change!

Do I have any idea *why* these tests work? No. But I swear, I *just*
re-made the patched interpeter in the directory where I ran the tests. You
will definitely be able to reproduce my results on your system.

Wacky! (seriously though I have no idea *why* this works, it just...
does... I'm scared...)

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[ppperry]

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 __false_lt__(self, other):
print("gizmo")
A.__lt__ = A.__true_lt__
return int.__lt__(self, other)


[A(i) for i in range(20, 5, -1)].sort()

This alternates printing "zebra" and "gizmo" for every comparison, and there is 
no way to add some sort of caching without changing this behavior.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Elliot Gorokhovsky]

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 could get a segfault. There are much easier ways to get segfaults using
the C API, however :)

Overall, I feel like if you're mutating the objects while they're being
sorted, you should be prepared for undefined behavior. Specifically, in the
current implementation, the sort result can be incorrect if you mutate as
you sort; no sort algorithm will recheck comparisons periodically to see if
you've tried to fool it.

Anyway, here's what Tim Peters said on the Github PR comments, where I
asked about the issue you raised:

> About the __class__-changing example, I don't care provided it doesn't >
blow up. But someone else should weigh in on that. I hope we can get, >
e.g., Raymond Hettinger to stare at this issue too.

Either way, great catch! Thanks for the feedback.

On Fri, Mar 10, 2017 at 6:15 PM ppperry  wrote:

>
> 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
> type(a)
> returns ""
>
> --
>
> ___
> Python tracker 
> 
> ___
>

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[ppperry]

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
type(a)
returns ""

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Elliot Gorokhovsky]

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. [1]
>
> [1] It is possible in some cases to change an object’s type, under
certain controlled conditions.
> It generally isn’t a good idea though, since it can lead to some very
strange behavior if it is
> handled incorrectly.

So I think it's safe to assume that type doesn't change; if you change
type, you get undefined ("very strange") behavior. Based on the comment in
the footnote, other code clearly assumes that type doesn't change, so I
don't see why list.sort() should be any different.

On Fri, Mar 10, 2017 at 5:08 PM ppperry  wrote:

>
> 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):
> last.__class__ = OrdinaryOldInteger
> return self._i < (other._i if hasattr(other, '_i')
> else other)
> @functools.total_ordering
> class OrdinaryOldInteger:
> def __init__(self, i):
> self._i = i
> def __lt__(self, other):
> return self._i < (other._i if hasattr(other, '_i')
> else other)
> lst = [ClassAssignmentCanBreakChecks(i) for i in range(10)]
> random.shuffle(lst)
> last = lst[-1]
> lst.sort()
> It looks like it will initially say that all are the same type, and
> attempt that optimization, which will probably lead to unexpected results
> as that condition is no longer true after the first compare.
>
> --
> nosy: +ppperry
>
> ___
> Python tracker 
> 
> ___
>

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[ppperry]

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):
last.__class__ = OrdinaryOldInteger
return self._i < (other._i if hasattr(other, '_i') else 
other)
@functools.total_ordering
class OrdinaryOldInteger:
def __init__(self, i):
self._i = i
def __lt__(self, other):
return self._i < (other._i if hasattr(other, '_i') else 
other)
lst = [ClassAssignmentCanBreakChecks(i) for i in range(10)]
random.shuffle(lst)
last = lst[-1]
lst.sort()
It looks like it will initially say that all are the same type, and attempt 
that optimization, which will probably lead to unexpected results as that 
condition is no longer true after the first compare.

--
nosy: +ppperry

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Elliot Gorokhovsky]

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 like the idea, and benchmarking results for randomized lists look nice.
> But could you please run benchmarks for already sorted lists?
>

David Mertz asked for the same thing on python-ideas. Here's what I replied
(you can also find these numbers in my pull request description):

***
You are entirely correct, as the benchmarks below demonstrate. I used the
benchmark lists from Objects/listsort.txt, which are:

  \sort: descending data
  /sort: ascending data
  3sort: ascending, then 3 random exchanges
  +sort: ascending, then 10 random at the end
  %sort: ascending, then randomly replace 1% of elements w/ random
values
  ~sort: many duplicates
  =sort: all equal

My results are below (the script can be found at
https://github.com/embg/python-fastsort-benchmark/blob/master/bench-structured.py
):
Homogeneous ([int]):
\sort: 54.6%
/sort: 56.5%
3sort: 53.5%
+sort: 55.3%
%sort: 52.4%
~sort: 48.0%
=sort: 45.2%

Heterogeneous ([int]*n + [0.0]):
\sort: -17.2%
/sort: -19.8%
3sort: -18.0%
+sort: -18.8%
%sort: -10.0%
~sort: -2.1%
=sort: -21.3%

As you can see, because there's a lot less non-comparison overhead in the
structured lists, the impact of the optimization is much greater, both in
performance gain and in worst-case cost. However, I would argue that these
data do not invalidate the utility of my patch: the probability of
encountering a type-heterogeneous list is certainly less than 5% in
practice. So the expected savings, even for structured lists, is something
like (5%)(-20%) + (95%)(50%) = 46.5%. And, of course, not *all* the lists
one encounters in practice are structured; certainly not *this* structured.
So, overall, I would say the numbers above are extremely encouraging.
Thanks for pointing out the need for this benchmark, though!
***

Thanks for the feedback!

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Serhiy Storchaka]

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 review
status: closed -> open

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Elliot Gorokhovsky]

Changes by Elliot Gorokhovsky :


--
pull_requests: +479

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Elliot Gorokhovsky]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[STINNER Victor]

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?

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Elliot Gorokhovsky]

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.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Elliot Gorokhovsky]

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 even more 
incredible than I could have imagined! First, here's my benchmark script:

#!/bin/bash
rm ref.json dev.json 2> /dev/null
python-dev/python -m perf timeit -s "$1" "sorted(l)" --rigorous -o dev.json > 
/dev/null
python-ref/python -m perf timeit -s "$1" "sorted(l)" --rigorous -o ref.json > 
/dev/null
python-ref/python -m perf compare_to ref.json dev.json

And here are the results:

./bench.sh "import random; l=[random.uniform(-1,1) for _ in range(0,100)]"
Median +- std dev: [ref] 8.34 us +- 0.18 us -> [dev] 3.33 us +- 0.13 us: 2.50x 
faster

So it's 150% faster! (i.e. 150% + 100% = 250%). 150% faster sorting for 
floats!!! If we make them tuples, it's even more incredible:
Median +- std dev: [ref] 20.9 us +- 1.0 us -> [dev] 4.99 us +- 0.27 us: 4.19x 
faster

319% faster!!! And earlier, I had thought 75% was impressive... I mean, 319%!!! 
And again, this is an application that is directly useful: DEAP spends a great 
deal of time sorting tuples of floats, this will make their EAs run a lot 
faster.

"import random; l=[str(random.uniform(-1,1)) for _ in range(0,100)]"
Median +- std dev: [ref] 15.7 us +- 0.9 us -> [dev] 9.24 us +- 0.52 us: 1.70x 
faster

"import random; l=[int(random.uniform(-1,1)*2**15) for _ in range(0,100)]"
Median +- std dev: [ref] 8.59 us +- 0.19 us -> [dev] 4.35 us +- 0.13 us: 1.98x 
faster

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Elliot Gorokhovsky]

Changes by Elliot Gorokhovsky :


Added file: http://bugs.python.org/file45508/fastsort.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Elliot Gorokhovsky]

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 -- I'm writing this up as a paper since this is my science fair
project, so I'll redo the measurements that way and upload a pdf here.

> About benchmarks, I also would like to see a benchmark on the bad case,
> when specialization is not used. And not only on an empty list :-) For
> example, sort 1000 objects which implement compare operators and/or a sort
> function.
>

The worst case is the third benchmark from the top -- a list of floats with
a single, sad, solitary long at the end. That disables optimization because
keys_are_all_same_type gets set to 0 when assign_compare_function finds the
long (since key_type == _Type). That benchmark is the *absolute*
worst case for two reasons:

1. Float compares are really cheap, so the ratio doesn't get messed up by
the common term "time spent actually comparing floats" (since the total
time is "time spent on overhead + time spend actually comparing floats").
2. The list is of size 10. I guess I could've used size 3 or 4, but it
shouldn't be too far off... smaller lists give worse ratios because the
overhead is O(n) while sorting is O(nlogn).

So, again, the absolute worst possible case is the third benchmark, which
suffers a 10% slowdown. Certainly a reasonable price to pay considering how
rare that case is in practice, and considering the 40-75% gains we get on
the common cases.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[STINNER Victor]

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.

http://doc.pypy.org/en/latest/interpreter-optimizations.html#list-optimizations

But we are limited by the C API, so we cannot change deeply the C structure 
without breaking backward compatibility.


> # (difference is within std dev)

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.

About benchmarks, I also would like to see a benchmark on the bad case, when 
specialization is not used. And not only on an empty list :-) For example, sort 
1000 objects which implement compare operators and/or a sort function.

--
nosy: +haypo

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Elliot Gorokhovsky]

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. Even though I had included
Python.h. Weird, right? So I assumed I had to leave it in the patch as
well. Thanks for pointing this out!

On Mon, Nov 14, 2016 at 6:09 AM Julien Palard 
wrote:

>
> 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 definition of Py_ABS, just in case I
> missed something in the includes, and it works.
>
> --
> nosy: +mdk
>
> ___
> Python tracker 
> 
> ___
>

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Julien Palard]

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 definition of Py_ABS, just in case I missed 
something in the includes, and it works.

--
nosy: +mdk

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Elliot Gorokhovsky]

Changes by Elliot Gorokhovsky :


--
nosy: +tim.peters

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Elliot Gorokhovsky]

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 character width for strings or the number of machine-words 
that represent a long. 

Obviously, the vast majority of the work done during a list.sort() is spent in 
comparisons, so even small optimizations can be important. What I noticed is 
that since we have n objects, but we're doing O(nlogn) comparisons, it pays off 
to do all the safety checks in a single pass and then select an optimized 
comparison function that leverages the information gained to avoid as many 
sort-time checks as possible. I made the following assumptions:

1. In practice, lists to be sorted are almost always type-homogeneous.
2. Most lists to be sorted consist of homogeneous elements of the following 
types:
a. Latin strings (i.e. strings whose characters are one machine-word wide)
b. Longs that fit in a single machine-word
c. Floats
d. Tuples of the above
3. The above assumptions also hold for lists constructed by taking a list of 
tuples to be sorted and extracting the first elements.
4. The vast majority of tuple comparisons never get past the first element 
(i.e. the first elements of tuples are rarely equal).

My patch adds the following routine to list.sort():
1. Go through the list and see which of the assumptions, if any, hold (except 
(4), which can't be checked in advance).
2. Replace PyObject_RichCompareBool() with an optimized compare function that 
is able to ignore some safety checks by applying the assumption we've already 
verified to be true.

There are then two questions: when none of the assumptions hold, how expensive 
is (1)? And when we do get a "hit", how much time do we save by applying (2)?

Those questions, of course, can only be answered by benchmarks. So here they 
are, computed on an isolated CPU core, on two python interpreters, both 
compiled with ./configure --with-optimizations:

# This is a runnable script. Just build the reference interpreter in python-ref 
and the patched interpreter in python-dev.

# Pathological cases (where we pay for (1) but don't get any savings from (2)): 
what kind of losses do we suffer?

# How expensive is (1) for empty lists?
python-dev/python -m perf timeit -s "l=[]" "sorted(l)" --rigorous 
python-ref/python -m perf timeit -s "l=[]" "sorted(l)" --rigorous  
# Median +- std dev: 212 ns +- 9 ns
# Median +- std dev: 216 ns +- 10 ns
# (difference is within std dev)

# How expensive is (1) for singleton lists?
python-dev/python -m perf timeit -s "l=[None]" "sorted(l)" --rigorous 
python-ref/python -m perf timeit -s "l=[None]" "sorted(l)" --rigorous
# Median +- std dev: 235 ns +- 16 ns
# Median +- std dev: 238 ns +- 15 ns
# (difference is within std dev)

# How expensive is (1) for non-type-homogeneous lists?
# (we use small lists because as n gets large, the fraction time spent in (1) 
gets smaller)
python-dev/python -m perf timeit -s "import random; l=[random.uniform(-1,1) for 
_ in range(0,10)]+[1]" "sorted(l)" --rigorous 
python-ref/python -m perf timeit -s "import random; l=[random.uniform(-1,1) for 
_ in range(0,10)]+[1]" "sorted(l)" --rigorous 
# Median +- std dev: 784 ns +- 35 ns
# Median +- std dev: 707 ns +- 51 ns
# 10% slower. While this is unfortunate, this case almost never occurs in 
practice, and the losses are certainly offset by the gains we'll see below.
# Also, note that for large lists, the difference would be *much* smaller, 
since the time spent in (1) gets smaller like 1/log(n).
# So basically, we only pay a penalty for non-type-homogeneous small lists.

# OK, now for the cases that actually occur in practice:

# What kind of gains do we get for floats?
python-dev/python -m perf timeit -s "import random; l=[random.uniform(-1,1) for 
_ in range(0,100)]" "sorted(l)" --rigorous
python-ref/python -m perf timeit -s "import random; l=[random.uniform(-1,1) for 
_ in range(0,100)]" "sorted(l)" --rigorous
# Median +- std dev: 3.63 us +- 0.20 us
# Median +- std dev: 8.81 us +- 0.37 us
# Wow! 59% faster! And if we used a large list, we would've gotten even better 
numbers.

# What kind of gains do we get for latin strings?
python-dev/python -m perf timeit -s "import random; 
l=[str(random.uniform(-1,1)) for _ in range(0,100)]" "sorted(l)" --rigorous
python-ref/python -m perf timeit -s "import random; 
l=[str(random.uniform(-1,1)) for _ in range(0,100)]" "sorted(l)" --rigorous
# Median +- std dev: 9.51 us +- 0.28 us
# Median +- std dev: 15.9 us +- 0.7 us
# 40% faster! 

# What kind of gains do we get for non-latin strings (which I imagine aren't 
that common to sort in practice anyway)
python-dev/python -m perf timeit -s "import random; 
l=[str(random.uniform(-1,1))+'\u' for _ in range(0,100)]" "sorted(l)" 
--rigorous
python-ref/python -m perf timeit -s