classification
Title: Faster total_ordering
Type: performance Stage: patch review
Components: Library (Lib) Versions: Python 3.5
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: ncoghlan, python-dev, rhettinger, serhiy.storchaka
Priority: normal Keywords: patch

Created on 2014-12-30 09:22 by serhiy.storchaka, last changed 2015-01-06 09:05 by serhiy.storchaka. This issue is now closed.

Files
File name Uploaded Description Edit
total_ordering_faster.patch serhiy.storchaka, 2014-12-30 09:22 review
total_ordering_bench.py serhiy.storchaka, 2014-12-30 09:22
total_ordering_relative_bench.py ncoghlan, 2014-12-31 06:39 Timing comparison to explicit ordering methods
total_ordering_faster_2.patch serhiy.storchaka, 2014-12-31 09:26 review
total_ordering.diff rhettinger, 2015-01-04 05:49 Spell-out all twelve variants
total_ordering2.diff rhettinger, 2015-01-05 06:22 Revised Py3.4 patch with better docstrings
Messages (13)
msg233196 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2014-12-30 09:22
Proposed patch makes comparation method generated by the total_ordering decorator faster up to 20%.

Benchmark results:

      Unpatched Patched
a < b   2.46      2.45
b < a   2.48      2.49
a >= b  4.86      4.16
b >= a  5.1       4.16
a <= b  4.93      4.15
b <= a  7.31      5.98
a > b   5.25      4.38
b > a   8.11      7.04

It also adds few additional attributes to generated methods.
msg233228 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2014-12-31 05:55
This looks like a nice, relatively simple improvement in both speed and introspection support, so +1 from me.

Something I've wondered since we changed total_ordering to handle NotImplemented correctly is whether it would be worth exposing more of the *components* of rich boolean comparison operations through the operator module. Currently it isn't possible to access the individual steps, which is why handling NotImplemented incurred such a large performance hit relative to the previous implementation that didn't worry about it (but also potentially hit RecursionError if the underlying comparison operation returned NotImplemented).
msg233229 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2014-12-31 06:39
I tweaked Serhiy's benchmark script to also include the timing relative to spelling out all four ordered comparison methods.

For an unpatched debug build of trunk, I get the following:

$ ../py3k/python total_ordering_relative_bench.py 
a < b   1.643 1.605 x0.98
b < a   1.611 1.611 x1.00
a >= b  1.599 3.539 x2.21
b >= a  1.607 3.579 x2.23
a <= b  1.600 3.677 x2.30
b <= a  1.601 5.599 x3.50
a > b   1.600 3.624 x2.26
b > a   1.612 6.465 x4.01

With Serhiy's change applied I get:

$ ../py3k/python total_ordering_relative_bench.py 
a < b   1.599 1.602 x1.00
b < a   1.607 1.609 x1.00
a >= b  1.602 2.802 x1.75
b >= a  1.605 2.804 x1.75
a <= b  1.737 2.842 x1.64
b <= a  1.607 4.835 x3.01
a > b   1.667 2.821 x1.69
b > a   1.597 5.557 x3.48
msg233233 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2014-12-31 09:26
Side effect of improving introspection is that generated unbounded methods are pickleable now. Updated patch contains a test for this.
msg233284 - (view) Author: Roundup Robot (python-dev) Date: 2015-01-01 13:28
New changeset 4e85df8b3ea6 by Serhiy Storchaka in branch 'default':
Issue #23132: Improve performance and introspection support of comparison
https://hg.python.org/cpython/rev/4e85df8b3ea6
msg233389 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2015-01-04 05:49
Serhiy, this is a really nice idea.  By removing the additional layer of indirection, the code is more intelligible, runs faster, and the tracebacks make more sense when the user's root comparison raises an exception.

Since there are only twelve functions involved, I don't think the function templates give us much of a payoff.  Instead, it would be better to just precompute the 12 functions rather than have 5 templates.

I've attached a patch relative to Python 3.4.  Ideally, I would like this backported to 3.4 to fix the regression in performance and intelligibility.

One further possible change is to localize the NotImplemented global variable.  This will reduce the overhead of NotImplemented checking to almost nothing and almost completely restore the performance of earlier versions.
msg233404 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2015-01-04 09:20
While I like the readability of Raymond's version, I think the main pay-off we're getting from the template based version is that each decorator invocation is creating *new* function objects.

That creation of new function objects is what allows Serhiy's patch to set __module__ and __qualname__ for each method implementation based on the class being defined.

The two approaches could be combined by moving the explicit definitions into factory functions that always created new function objects and set their introspection attributes appropriately. For example (untested code):

    def _fix_introspection(module, cls_qualname):
        def update_metadata(f):
            f.__qualname__ = "%s.%s" % (cls_qualname, f.__name__)
            f.__module__ = module
            return f
        return update_metadata

    def _derive_from_lt(module, cls_qualname):
        _NotImplemented = NotImplemented

        @_fix_introspection(module, cls_qualname)
        def __gt__(self, other):
            op_result = self.__lt__(other)
            if op_result is _NotImplemented:
                return _NotImplemented
            return not op_result and self != other

        @_fix_introspection(module, cls_qualname)
        def __le__(self, other):
            op_result = self.__lt__(other)
            return op_result or self == other

        @_fix_introspection(module, cls_qualname)
        def __ge__(self, other):
            op_result = self.__lt__(other)
            if op_result is _NotImplemented:
                return _NotImplemented
            return not op_result

        return __lt__, __gt__, __ge__
msg233406 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2015-01-04 09:39
Oops, at least one error in my example: the return tuple should be "__gt__, __le__, __ge__".
msg233412 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2015-01-04 10:56
I don't see "creating new functions" as an advantage.  ABCs don't do this, nor does any other subclassing.   It seems like an attempt to create a false illusion about where the code resides.  This feels like feature creep with no real advantage that anyone cares about.  

In the non-templating version, the code is simple and it is clear where it came-from (i.e. a code inspector can find it).

IMO, the factory functions just make it harder to grok this code.  Please resist the urge invent new magic and stick with the simplest Python that gets the job done.
msg233417 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2015-01-04 14:04
The convert mapping is redundant, function name can be calculated from root and opname. __name__ and __doc__ can be assigned at import time.
msg233419 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2015-01-04 14:19
The metadata adjustments in Serhiy's patch had me thinking in terms of functools.wraps, but that rationale doesn't actually apply here (since the functions are only used in one place, and have a distinctive name rather than a generic one).

I'd also missed that the conversion to standalone module level functions inherently provides the same pickle compatibility benefit that Serhiy's patch did.

Accordingly, I agree that my suggested factory functions would make the code more complex for no benefit.
msg233504 - (view) Author: Roundup Robot (python-dev) Date: 2015-01-06 06:00
New changeset 09b0da38ce8d by Raymond Hettinger in branch '3.4':
Issue #23132: Mitigate regression in speed and clarity in functools.total_ordering.
https://hg.python.org/cpython/rev/09b0da38ce8d
msg233510 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2015-01-06 09:05
May be implement your idea about local NotImplemented? And it would be good to 
add explaining comments in _le_from_lt() and _ge_from_gt() as in your original 
suggestion.
History
Date User Action Args
2015-01-06 09:05:33serhiy.storchakasetmessages: + msg233510
2015-01-06 06:22:55rhettingersetstatus: open -> closed
resolution: fixed
2015-01-06 06:00:42python-devsetmessages: + msg233504
2015-01-05 06:22:13rhettingersetfiles: + total_ordering2.diff
2015-01-04 14:19:08ncoghlansetmessages: + msg233419
2015-01-04 14:04:48serhiy.storchakasetmessages: + msg233417
2015-01-04 10:56:51rhettingersetassignee: rhettinger
messages: + msg233412
2015-01-04 09:39:54ncoghlansetmessages: + msg233406
2015-01-04 09:20:25ncoghlansetmessages: + msg233404
2015-01-04 05:49:32rhettingersetfiles: + total_ordering.diff

messages: + msg233389
2015-01-04 05:39:22rhettingersetmessages: - msg233383
2015-01-04 02:39:12rhettingersetmessages: + msg233383
2015-01-01 13:28:36python-devsetnosy: + python-dev
messages: + msg233284
2014-12-31 09:26:37serhiy.storchakasetfiles: + total_ordering_faster_2.patch

messages: + msg233233
2014-12-31 06:39:45ncoghlansetfiles: + total_ordering_relative_bench.py

messages: + msg233229
2014-12-31 05:55:55ncoghlansetmessages: + msg233228
2014-12-30 09:22:58serhiy.storchakasetfiles: + total_ordering_bench.py
2014-12-30 09:22:09serhiy.storchakacreate