Sage: Ticket #10130: Revamp __hash__, __cmp__ and __richcmp__
https://trac.sagemath.org/ticket/10130
<p>
There are a number of confusing and non-optimal features of the way Sage currently handles hashing and comparison.
</p>
<ul><li>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 <a class="closed ticket" href="https://trac.sagemath.org/ticket/18329" title="#18329: enhancement: Inherit __richcmp__ and __cmp__ in subclasses of Element (closed: fixed)">#18329</a>.
</li></ul><ul><li>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 <code>self.__hash</code>). And often parents don't override the default hashing code and they fall back to slow <code>__repr__</code> methods. Fixed by <a class="closed ticket" href="https://trac.sagemath.org/ticket/715" title="#715: defect: Parents probably not reclaimed due to too much caching (closed: fixed)">#715</a>???
</li></ul>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/10130
Trac 1.2David RoeFri, 15 Oct 2010 07:09:23 GMT
https://trac.sagemath.org/ticket/10130#comment:1
https://trac.sagemath.org/ticket/10130#comment:1
<p>
I don't know the best way to resolve these issues, but here are some ideas.
</p>
<ul><li>Have cpdef'd functions <code>_hash_</code>, <code>_cmp_</code> and <code>_richcmp_</code> that users will override.
</li><li>For parents, add an attribute "cdef public long <code>__hash</code>". I don't know if this should be set to self._hash_() during the parent's <code>__init__</code> method, or set to -1 and then reset upon the first call to <code>__hash__</code>.
</li><li>For <code>SageObject</code>, have the default behavior of <code>_hash_()</code> be to return <code>hash(repr(self))</code>. For parents, have the default value of hash depend on <code>self.construction()</code>?
</li><li>For elements, don't cache the hash by default.
</li><li>Have the results of ==, <, etc, depend on <code>_richcmp_</code>. By default, have <code>_richcmp_</code> determined by a total ordering implemented by <code>_cmp_</code>. So if you want to have partial ordering, or a different partial and total ordering, you need to implement both <code>_cmp_</code> and <code>_richcmp_</code>.
</li><li>For parents, <code>_cmp_</code> 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.
</li><li>Elements would have no default <code>_cmp_</code>, but would instead raise an error.
</li></ul>
TicketDavid RoeFri, 15 Oct 2010 07:37:42 GMT
https://trac.sagemath.org/ticket/10130#comment:2
https://trac.sagemath.org/ticket/10130#comment:2
<p>
Also, in Python 2.6, you can set A.<span class="underline">hash</span> = 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).
</p>
TicketDavid RoeFri, 15 Oct 2010 07:39:53 GMTattachment set
https://trac.sagemath.org/ticket/10130
https://trac.sagemath.org/ticket/10130
<ul>
<li><strong>attachment</strong>
set to <em>10130_basic.patch</em>
</li>
</ul>
<p>
A few hash changes. WARNING: changes parent.pxd, so rebuilding will be slow.
</p>
TicketDavid RoeFri, 15 Oct 2010 07:41:27 GMT
https://trac.sagemath.org/ticket/10130#comment:3
https://trac.sagemath.org/ticket/10130#comment:3
<p>
As an example of the speed gains possible, this patch resolves <a class="closed ticket" href="https://trac.sagemath.org/ticket/9886" title="#9886: defect: slow coercion from integer mod ring to integer ring, part 2 (closed: duplicate)">#9886</a>.
</p>
TicketNicolas M. ThiéryMon, 28 Mar 2011 13:14:39 GMT
https://trac.sagemath.org/ticket/10130#comment:4
https://trac.sagemath.org/ticket/10130#comment:4
<p>
Just a quick note: for parents that use <a class="missing wiki">UniqueRepresentation?</a>, the hash is given by the id of the object; one can't be much faster (except that <a class="missing wiki">UniqueRepresentation?</a> is not Cython'ed yet):
</p>
<pre class="wiki">
F = CombinatorialFreeModule(QQ,QQ)
sage: F.__hash__()
98169392
sage: id(F)
98169392
</pre><p>
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).
</p>
TicketTravis ScrimshawTue, 05 Feb 2013 15:01:38 GMTcc changed
https://trac.sagemath.org/ticket/10130#comment:5
https://trac.sagemath.org/ticket/10130#comment:5
<ul>
<li><strong>cc</strong>
<em>Nicolas M. Thiéry</em> added
</li>
</ul>
<p>
Nicolas T. and I somewhat came across the second point in working on <a class="closed ticket" href="https://trac.sagemath.org/ticket/13605" title="#13605: enhancement: Partition options and cleanup partitions documentation (closed: fixed)">#13605</a>. In particular, I have changed <code>Partition</code> to inherit from <code>Element</code>, use the rich comparisons, and removed the <code>__cmp__()</code> method. Thus calling things like
</p>
<pre class="wiki">sage: sorted(Partitions(5), cmp)
</pre><p>
raise the "BUG - comparsion not implemented" exception. This holds for any subclass of <code>Element</code> which does not implement a <code>__cmp__()</code> and does not fall back on the rich comparisons as regular python objects would.
</p>
TicketJeroen DemeyerTue, 13 Aug 2013 15:35:53 GMTmilestone changed
https://trac.sagemath.org/ticket/10130#comment:6
https://trac.sagemath.org/ticket/10130#comment:6
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.11</em> to <em>sage-5.12</em>
</li>
</ul>
TicketFor batch modificationsThu, 30 Jan 2014 21:20:52 GMTmilestone changed
https://trac.sagemath.org/ticket/10130#comment:7
https://trac.sagemath.org/ticket/10130#comment:7
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.1</em> to <em>sage-6.2</em>
</li>
</ul>
TicketFor batch modificationsTue, 06 May 2014 15:20:58 GMTmilestone changed
https://trac.sagemath.org/ticket/10130#comment:8
https://trac.sagemath.org/ticket/10130#comment:8
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.2</em> to <em>sage-6.3</em>
</li>
</ul>
TicketFor batch modificationsSun, 10 Aug 2014 16:51:03 GMTmilestone changed
https://trac.sagemath.org/ticket/10130#comment:9
https://trac.sagemath.org/ticket/10130#comment:9
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.3</em> to <em>sage-6.4</em>
</li>
</ul>
TicketMarc MezzarobbaWed, 04 Mar 2015 15:52:33 GMT
https://trac.sagemath.org/ticket/10130#comment:10
https://trac.sagemath.org/ticket/10130#comment:10
<p>
Related: <a class="closed ticket" href="https://trac.sagemath.org/ticket/17890" title="#17890: enhancement: Remove _(rich)cmp_c_impl (closed: fixed)">#17890</a>.
</p>
TicketJeroen DemeyerWed, 04 Mar 2015 16:35:03 GMT
https://trac.sagemath.org/ticket/10130#comment:11
https://trac.sagemath.org/ticket/10130#comment:11
<p>
The second item is fixed by <a class="closed ticket" href="https://trac.sagemath.org/ticket/17890" title="#17890: enhancement: Remove _(rich)cmp_c_impl (closed: fixed)">#17890</a> and I guess the third is fixed <a class="closed ticket" href="https://trac.sagemath.org/ticket/715" title="#715: defect: Parents probably not reclaimed due to too much caching (closed: fixed)">#715</a>. The first is pure Python behaviour, which I don't see an obvious solution for...
</p>
TicketJeroen DemeyerWed, 04 Mar 2015 16:36:05 GMTdescription changed
https://trac.sagemath.org/ticket/10130#comment:12
https://trac.sagemath.org/ticket/10130#comment:12
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/10130?action=diff&version=12">diff</a>)
</li>
</ul>
TicketJeroen DemeyerWed, 29 Apr 2015 15:18:18 GMTdescription changed
https://trac.sagemath.org/ticket/10130#comment:13
https://trac.sagemath.org/ticket/10130#comment:13
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/10130?action=diff&version=13">diff</a>)
</li>
</ul>
TicketJeroen DemeyerFri, 29 Jul 2016 11:26:51 GMTstatus, milestone changed; reviewer set
https://trac.sagemath.org/ticket/10130#comment:14
https://trac.sagemath.org/ticket/10130#comment:14
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Jeroen Demeyer</em>
</li>
<li><strong>milestone</strong>
changed from <em>sage-6.4</em> to <em>sage-duplicate/invalid/wontfix</em>
</li>
</ul>
<p>
This is a too general ticket. And most of this is actually fixed.
</p>
TicketJeroen DemeyerFri, 29 Jul 2016 11:26:59 GMTstatus changed
https://trac.sagemath.org/ticket/10130#comment:15
https://trac.sagemath.org/ticket/10130#comment:15
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
TicketErik BrayTue, 30 Aug 2016 13:32:25 GMTstatus changed; resolution set
https://trac.sagemath.org/ticket/10130#comment:16
https://trac.sagemath.org/ticket/10130#comment:16
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>wontfix</em>
</li>
</ul>
<p>
Determined to be invalid/duplicate/wontfix (closing as "wontfix" as a catch-all resolution).
</p>
Ticket