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

[Tim Peters]

Tim Peters <tim at python.org> 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 <report at bugs.python.org>
<https://bugs.python.org/issue28685>
_______________________________________