Support __richcmp__ in Python classes

[jdemeyer]

Sage has a lot of functionality to deal with "rich comparisons" using __richcmp__ in Cython or _richcmp_ in Python or Cython for subclasses of Element. However, we are still missing rich comparison support for Python classes which are not subclasses from Element.

A good example of this is RealSet in src/sage/sets/real_set.py. Currently, comparison is implemented using __cmp__. Changing this to Python 3 comparisons would normally require 6 methods (__eq__, __ne__, __lt__, __le__, __gt__, __ge__). It would be convenient to support this with just one __richcmp__ method like in Cython.

This ticket proposes:

1. Add a decorator richcmp_method which adds support for __richcmp__ to a Python class.

2. Implement RealSet.__richcmp__ using this.

Depends on #23103

CC: @fchapoton @tscrim @embray

Component: python3

Author: Jeroen Demeyer

Branch/Commit: 4d1021b

Reviewer: Travis Scrimshaw, Erik Bray

Issue created by migration from https://trac.sagemath.org/ticket/23102

[tscrim]

comment:2

What about using @total_ordering to reduce the number of rich comparison methods? I know this is an abuse of terminology, but it does mean we only need to define __eq__ and __lt__. However, I generally do like the idea of having a consistent API.

[jdemeyer]

Branch: u/jdemeyer/ticket/23102

[jdemeyer]

comment:5

Replying to @tscrim:

What about using @total_ordering to reduce the number of rich comparison methods?

1. @total_ordering reduces the number of rich comparison methods from 6 to 2. This ticket reduces it from 6 to 1.

2. @total_ordering is less efficient (if you only have == and <, you might need two calls to determine <=)

---

New commits:

256bf19	Move richcmp stuff to new file richcmp.pyx
b591b78	Support `__richcmp__` in Python classes
47f97ec	Implement RealSet comparisons using __richcmp__

[jdemeyer]

Commit: 47f97ec

[jdemeyer]

Dependencies: #23103

[fchapoton]

comment:8

Note that from #22828, there is

def richcmp_by_eq_and_lt(left, right, op):

in

src/sage/rings/asymptotic/misc.py

that should also be moved to the common new place.

[jdemeyer]

comment:9

Replying to @fchapoton:

Note that from #22828, there is

def richcmp_by_eq_and_lt(left, right, op):

in

src/sage/rings/asymptotic/misc.py

that should also be moved to the common new place.

Makes sense. I created #23109 for that.

[tscrim]

comment:10

Typo in richcmp_method: mtehod. Have you run some timings to compare how this works versus direct implementation versus @total_ordering in Python classes? I can do this, but not for 2-3 days because I will be traveling.

[jdemeyer]

comment:11

Replying to @tscrim:

Have you run some timings to compare how this works versus direct implementation versus @total_ordering in Python classes? I can do this, but not for 2-3 days because I will be traveling.

I just did that, see attachment: cmp-timing.py

First of all, for a plain equality check (@total_ordering is not involved in this), the timing is almost the same for __eq__ and __richcmp__, the latter being just slightly slower:

sage: load("cmp-timing.py")
sage: timeit('A1 == A2', number=1000000, repeat=100)
1000000 loops, best of 100: 281 ns per loop
sage: timeit('B1 == B2', number=1000000, repeat=100)
1000000 loops, best of 100: 293 ns per loop

Now, comparisons involving @total_ordering take almost twice or three times as much time:

sage: load("cmp-timing.py")
sage: timeit('A1 > A2', number=1000000, repeat=20)   # calls A2.__lt__(A1)
1000000 loops, best of 20: 557 ns per loop
sage: timeit('B1 > B2', number=1000000, repeat=20)
1000000 loops, best of 20: 292 ns per loop

sage: load("cmp-timing.py")
sage: timeit('A2 <= A1', number=1000000, repeat=20)  # Calls A2.__lt__(A1) and A2.__eq__(A1)
1000000 loops, best of 20: 820 ns per loop
sage: timeit('B2 <= B1', number=1000000, repeat=20)
1000000 loops, best of 20: 293 ns per loop

As one might expect, the time is roughly linear in the number of Python method calls.

[jdemeyer]

Attachment: cmp-timing.py.gz

Small script to test timing

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:12

Thank you for running those timings. That is more than enough to convince me. If tests pass, you can set a positive review on my behalf. Sleepy time for me now. :)

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

acfd0aa

Typo

[sagetrac-git]

Changed commit from 47f97ec to acfd0aa

[vbraun]

Changed branch from u/jdemeyer/ticket/23102 to acfd0aa

[vbraun]

Changed commit from acfd0aa to none

[vbraun]

comment:16

This happened randomly:

sage -t --long src/sage/sets/real_set.py
**********************************************************************
File "src/sage/sets/real_set.py", line 701, in sage.sets.real_set.RealSet.__richcmp__
Failed example:
    cmp(I1, I2)
Expected:
    1
Got:
    -1
**********************************************************************
File "src/sage/sets/real_set.py", line 703, in sage.sets.real_set.RealSet.__richcmp__
Failed example:
    sorted([I1, I2])
Expected:
    [(0, 5], (1, 3]]
Got:
    [(1, 3], (0, 5]]
**********************************************************************
1 item had failures:
   2 of   6 in sage.sets.real_set.RealSet.__richcmp__
    [203 tests, 2 failures, 0.55 s]

[jdemeyer]

comment:17

Confirmed. It seems that the category framework gets in the way. Commenting out this line fixes the problem

Parent.__init__(self, category = Sets())

[embray]

comment:36

As an aside, I wonder if there's ever been a proposal to actually support __richcmp__ in user-defined classes (in a manner similar to this, such that it would automatically implment the individual comparison methods). And if it has been proposed I wonder why it was rejected. I'm going to search around a bit for answers...

[embray]

comment:37

A close reading of PEP-207 reveals:

The choice of six special methods was made over a single (e.g. __richcmp__) method to allow the dispatching on the opcode to be performed at the level of the C implementation rather than the user-defined method.

which makes perfect sense. But, if as Sage demonstrates, there's a usecase for a single user-defined __richcmp__ I don't see why it shouldn't be an option...

[tscrim]

comment:38

As Jeroen and Erik said, I felt it could be merged into Sage and further changes could be handled on followup tickets.

---

New commits:

b591b78	Support `__richcmp__` in Python classes
47f97ec	Implement RealSet comparisons using __richcmp__
acfd0aa	Typo

[tscrim]

Commit: acfd0aa

[tscrim]

Changed branch from f52d5c3 to u/jdemeyer/ticket/23102

[jdemeyer]

comment:39

I'll work on it right now.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

49b6f76	Support `__richcmp__` in Python classes
d343d9d	Implement RealSet comparisons using __richcmp__
3aac3cc	Typo
86e9fcf	Install slot wrappers for rich comparison methods

[sagetrac-git]

Changed commit from acfd0aa to 86e9fcf

[jdemeyer]

comment:41

Travis: you put back the wrong branch. This is the original branch, rebased to 8.0.beta11.

[tscrim]

comment:42

Ah, sorry; I had thought u/jdemeyer/acfd0aaea4de51b64c21fdd1a7a8d6e9174448de was just a trac formatting error.

[jdemeyer]

comment:43

Replying to @embray:

if type(slotwrapper) != PyWrapperDescr_Type:

Good point. It didn't occur to me to use the C/API for this. Python doesn't expose this type anywhere AFAIK, but the C/API does.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

4d1021b

Further fixes and tests for richcmp_method

[sagetrac-git]

Changed commit from 86e9fcf to 4d1021b

[jdemeyer]

comment:45

I think this addresses all Erik's concerns.

[jdemeyer]

Changed reviewer from Travis Scrimshaw to Travis Scrimshaw, Erik Bray

[embray]

comment:46

Replying to @jdemeyer:

Replying to @embray:

if type(slotwrapper) != PyWrapperDescr_Type:

Good point. It didn't occur to me to use the C/API for this. Python doesn't expose this type anywhere AFAIK, but the C/API does.

You can get at it in Python, for example, with type(bytes.__lt__), but in Cython you might as well just use the type directly since it's exposed by the C API.

[fchapoton]

comment:47

is this ready to go ?

[jdemeyer]

comment:48

Erik?

[embray]

comment:49

Yep, perfect--thanks.

[vbraun]

Changed branch from u/jdemeyer/ticket/23102 to 4d1021b