Opened 9 years ago

Closed 3 years ago

#10130 closed enhancement (wontfix)

Revamp __hash__, __cmp__ and __richcmp__

Reported by: roed Owned by: robertwb
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: coercion Keywords:
Cc: robertwb, nthiery Merged in:
Authors: Reviewers: Jeroen Demeyer
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by jdemeyer)

There are a number of confusing and non-optimal features of the way Sage currently handles hashing and comparison.

  • Because of Python, if you override one of these functions, you must redefine the others as well. This is easy to forget and confuses new users. For Cython classes, this can be fixed in #18329.
  • hashes of parents are used extensively in the coercion framework, so speed is quite important. But since parents are usually written in Python, the current model will always have at least a dictionary lookup (for example, in finding a cached self.__hash). And often parents don't override the default hashing code and they fall back to slow __repr__ methods. Fixed by #715???

Attachments (1)

10130_basic.patch (2.5 KB) - added by roed 9 years ago.
A few hash changes. WARNING: changes parent.pxd, so rebuilding will be slow.

Download all attachments as: .zip

Change History (17)

comment:1 Changed 9 years ago by roed

I don't know the best way to resolve these issues, but here are some ideas.

  • Have cpdef'd functions _hash_, _cmp_ and _richcmp_ that users will override.
  • For parents, add an attribute "cdef public long __hash". I don't know if this should be set to self._hash_() during the parent's __init__ method, or set to -1 and then reset upon the first call to __hash__.
  • For SageObject, have the default behavior of _hash_() be to return hash(repr(self)). For parents, have the default value of hash depend on self.construction()?
  • For elements, don't cache the hash by default.
  • Have the results of ==, <, etc, depend on _richcmp_. By default, have _richcmp_ determined by a total ordering implemented by _cmp_. So if you want to have partial ordering, or a different partial and total ordering, you need to implement both _cmp_ and _richcmp_.
  • For parents, _cmp_ checks first for pointer equality. If non-equal, it compares the hashes. If those are nonequal, returns the cmp of the hashes. Otherwise, returns the cmp of the pointers.
  • Elements would have no default _cmp_, but would instead raise an error.

comment:2 Changed 9 years ago by roed

Also, in Python 2.6, you can set A.hash = None, to indicate that an object is not hashable. We should probably do this for the various immutable types in Sage, rather than raising a type error. I don't know if this works currently (I can't do it from the command line on a mutable matrix for example).

Changed 9 years ago by roed

A few hash changes. WARNING: changes parent.pxd, so rebuilding will be slow.

comment:3 Changed 9 years ago by roed

As an example of the speed gains possible, this patch resolves #9886.

comment:4 Changed 9 years ago by nthiery

Just a quick note: for parents that use UniqueRepresentation?, the hash is given by the id of the object; one can't be much faster (except that UniqueRepresentation? is not Cython'ed yet):

   F = CombinatorialFreeModule(QQ,QQ)
   sage: F.__hash__()
   98169392
   sage: id(F)
   98169392

Other than that, I am all for improvements in this direction, because at this stage I am still confused about what I should do when I want to implement a partially ordered set in Python. Besides it would be best if it was possible to implement such partial orders in categories (remember that element methods defined in categories are overridden by methods defined in concrete classes like Element).

comment:5 Changed 7 years ago by tscrim

  • Cc nthiery added

Nicolas T. and I somewhat came across the second point in working on #13605. In particular, I have changed Partition to inherit from Element, use the rich comparisons, and removed the __cmp__() method. Thus calling things like

sage: sorted(Partitions(5), cmp)

raise the "BUG - comparsion not implemented" exception. This holds for any subclass of Element which does not implement a __cmp__() and does not fall back on the rich comparisons as regular python objects would.

comment:6 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:7 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:8 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:9 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:10 Changed 5 years ago by mmezzarobba

Related: #17890.

comment:11 Changed 5 years ago by jdemeyer

The second item is fixed by #17890 and I guess the third is fixed #715. The first is pure Python behaviour, which I don't see an obvious solution for...

comment:12 Changed 5 years ago by jdemeyer

  • Description modified (diff)

comment:13 Changed 4 years ago by jdemeyer

  • Description modified (diff)

comment:14 Changed 3 years ago by jdemeyer

  • Milestone changed from sage-6.4 to sage-duplicate/invalid/wontfix
  • Reviewers set to Jeroen Demeyer
  • Status changed from new to needs_review

This is a too general ticket. And most of this is actually fixed.

comment:15 Changed 3 years ago by jdemeyer

  • Status changed from needs_review to positive_review

comment:16 Changed 3 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.