Opened 5 years ago

Closed 4 years ago

#19108 closed enhancement (wontfix)

Implement Python 3 style comparison in the coercion framework

Reported by: ohanar Owned by:
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: coercion Keywords:
Cc: jdemeyer Merged in:
Authors: Reviewers: Jeroen Demeyer
Report Upstream: N/A Work issues:
Branch: u/ohanar/python3stylecomparison (Commits) Commit: 168fafb347a6afbdc96cae5bc27a4bea1c22f2e9
Dependencies: Stopgaps:

Description (last modified by 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.

Change History (12)

comment:1 Changed 5 years ago by ohanar

  • Status changed from new to needs_review

comment:2 Changed 5 years ago by 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.

comment:3 in reply to: ↑ description ; follow-up: Changed 5 years ago by 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.

comment:4 follow-up: Changed 5 years ago by jdemeyer

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

comment:5 in reply to: ↑ 3 Changed 5 years ago by 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.

comment:6 in reply to: ↑ 4 ; follow-up: Changed 5 years ago by 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.

comment:7 Changed 5 years ago by 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).

comment:8 in reply to: ↑ 6 Changed 5 years ago by 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.

comment:9 Changed 5 years ago by ohanar

  • Description modified (diff)
  • Status changed from needs_review to needs_work

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.

comment:10 Changed 4 years ago by 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.

Last edited 4 years ago by jdemeyer (previous) (diff)

comment:11 Changed 4 years ago by jdemeyer

  • Authors R. Andrew Ohana deleted
  • Milestone changed from sage-6.9 to sage-duplicate/invalid/wontfix
  • Reviewers set to Jeroen Demeyer
  • Status changed from needs_work to positive_review

comment:12 Changed 4 years ago by embray

  • Resolution set to wontfix
  • Status changed from positive_review to closed

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

Note: See TracTickets for help on using tickets.