Implement Python 3 style comparison in the coercion framework

[ohanar]

Currently to implement comparison for an element, you either need to implement _cmp_ or _richcmp_. For developers accustom to Python 3's method of implementing each comparison operator, we should have _lt_, _le_, etc.

[ohanar]

I'm open to feedback on implementation details. In particular, this could also naturally go into the category framework, however I was afraid of the performance penalty of doing that.

[jdemeyer]

Replying to ohanar:

Additionally, for most elements where comparison makes sense, there is the overwhelming notion that such a comparison is a partial order.

Why do you think that? I would guess that comparison is in most cases a total order, with partial orders being the exception.

There is also #18305, which tries to solve the same problem in a different way.

[jdemeyer]

I don't understand why the Parent becomes involved at all. That needs more justification.

[ohanar]

Replying to jdemeyer:

Replying to ohanar:

Additionally, for most elements where comparison makes sense, there is the overwhelming notion that such a comparison is a partial order.

Why do you think that? I would guess that comparison is in most cases a total order, with partial orders being the exception.

Sets are a common example (e.g. ideals, set and integer partitions, etc) of where you have a partial order but not a total order.

It doesn't really matter though, it would just add one extra rule (namely that you can deduce _eq_ from _lt_ and _gt_), which wouldn't really make it any easier or harder to implement either a total order or partial order.

There is also #18305, which tries to solve the same problem in a different way.

It solves part of the problem (not the partial/total ordering thing), and I think it is a bit more confusing for new developers who have a python 3 background (since they have to learn about _richcmp_). In some sense the two approaches are complementary.

[ohanar]

Replying to jdemeyer:

I don't understand why the Parent becomes involved at all. That needs more justification.

It is for caching the partial/total order resolution. Otherwise, each time you compare two elements, the default _richcmp_ method would need to determine which comparison operators are implemented by the underlying element and then how to use those to give an answer for the requested comparison operator.

I'm rebuilding this branch at the moment and once I'll do that I'll do some performance tests between enabling/disabling the cache.

[ohanar]

Ok, some very quick performance tests, using the following class:

class MyElt(Element):
    def _le_(self, other):
        return True
P = Parent()
e = MyElt(P)

With caching enabled I get the following:

sage: timeit('e <= e', number=10**7, repeat=10)
10000000 loops, best of 10: 301 ns per loop
sage: timeit('e == e', number=10**7, repeat=10)
10000000 loops, best of 10: 427 ns per loop

Without caching I get the following:

sage: timeit('e <= e', number=10**7, repeat=10)
10000000 loops, best of 10: 494 ns per loop
sage: timeit('e == e', number=10**7, repeat=10)
10000000 loops, best of 10: 636 ns per loop

Given that I've only implemented _le_, the equality operator will call the _le_ method twice, so from both examples we can see that the call to that function takes around 130-140 ns. Hence, the actual raw time before we get to calling the element's _le_ goes up from around 160-170 ns when caching on the parent to around 360-370 ns when not caching on the parent.

Granted, I didn't do any real changes to the partial/total order resolution other than just disabling caching, so you could improve the non-cached situation a bit, but my guess is that you would only get it down to around 300 ns or so depending on the operator that is asked for and the operators the element class provides (obviously, if you asked for an operator that the underlying element class provides, then you could short circuit much faster, and get close to the uncached performance).

[jdemeyer]

Replying to ohanar:

Replying to jdemeyer:

I don't understand why the Parent becomes involved at all. That needs more justification.

It is for caching the partial/total order resolution.

Why do you assume that every element with the same parent uses the same comparison functions?

If you want caching, it should be on the type() of the Element, not the parent.

[ohanar]

Yes, you are right.

Thinking about it a bit more, I think it would make better sense to split off the partial/total order stuff into metaclasses, I'll split those into another ticket when I get around it.

[jdemeyer]

This looks like an over-engineered solution to the problem of implementing comparison for plain Python classes.

A better solution would be to add better support for _richmp_. This is what I did in #21128.

[embray]

Determined to be invalid/duplicate/wontfix (closing as "wontfix" as a catch-all resolution).