remove naive hash from SageObject #18246

videlec · 2015-04-18T10:44:24Z

Hashing is a critical function in Python. In several places, objects do use the generic __hash__ from SageObject or a badly implemented one that makes everything slow. For example:

Huge speed up for hash of quadratic number field elements #18215 for quadratic number field elements (in relation with polyhedra Great speedup in polytopes construction with generic backend #18241)
Constructing Cayley graphs is slow #18239 for permutation group elements

See also #19016 for a ticket with the same purpose (with Element instead of SageObject).

CC: @nathanncohen

Component: coercion

Author: Vincent Delecroix

Branch/Commit: 5627a1d

Reviewer: Volker Braun, Nils Bruin

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

The text was updated successfully, but these errors were encountered:

videlec · 2015-04-18T11:00:21Z

Commit: a7aa08f

videlec · 2015-04-18T11:00:21Z

New commits:

`a7aa08f`	Trac 18246: remove `__hash__` from Sage object

videlec · 2015-04-18T11:00:21Z

Branch: public/18246

nathanncohen · 2015-04-18T12:31:18Z

comment:3

sage: hash(SageObject())
8751828132417

I am fixing it.

nathanncohen · 2015-04-18T12:34:59Z

comment:4

As expected everything breaks. What do we do?

sagetrac-git · 2015-04-18T12:35:56Z

Changed commit from a7aa08f to 6b9f883

sagetrac-git · 2015-04-18T12:35:56Z

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

`6b9f883`	`trac #18246: raise NotImplementedError`

videlec · 2015-04-18T12:56:16Z

comment:6

You should raise a TypeError if you want to raise something. Otherwise it breaks too much stuff (in particular cached_method, cached_function)

nathanncohen · 2015-04-18T12:59:54Z

comment:7

TypeError ? Well, why not...

sagetrac-git · 2015-04-18T13:01:11Z

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

`2869bc2`	`trac #18246: raise TypeError`

sagetrac-git · 2015-04-18T13:01:11Z

Changed commit from 6b9f883 to 2869bc2

sagetrac-git · 2015-04-18T13:26:26Z

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

`631e5c1`	`Trac 18236: more explicit TypeError message`
`61b0fce`	`Trac 18246: make all test pass in sage/rings`

sagetrac-git · 2015-04-18T13:26:26Z

Changed commit from 2869bc2 to 61b0fce

videlec · 2015-04-18T13:27:38Z

comment:10

Most of the time, it is very easy to fix. But I had to implement a lot

def __hash__(self):
    return id(self)

which I guess is close from the default Python implementation.

sagetrac-git · 2015-08-12T15:59:59Z

Changed commit from 61b0fce to 5a1e636

sagetrac-git · 2015-08-12T15:59:59Z

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

`46a1f74`	Trac 18246: remove `__hash__` from Sage object
`4e53eee`	`Trac 18246: fix polynomial term order`
`2282b78`	Trac 18246: fix `__hash__` in rings
`9f4ea07`	Trac 18246: fix `__hash__` in plot
`a4e58eb`	Trac 18246: fix `__hash__` in geometry
`5a1e636`	Trac 18246: fix `__hash__` in combinat

videlec · 2015-08-12T16:02:23Z

comment:12

Let us see how much patchbot is happy...

sagetrac-git · 2015-08-12T17:17:11Z

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

`d53c30e`	Trac 18246: fix `__hash__` in algebras
`518c3c2`	Trac 18246: fix `__hash__` in homology
`72c50be`	Fix 18246: fix `__hash__` in quadratic_forms

sagetrac-git · 2015-08-12T17:17:11Z

Changed commit from 5a1e636 to 72c50be

sagetrac-git · 2015-08-12T17:17:51Z

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

`8641677`	Trac 18246: fix `__hash__` in quadratic_forms

sagetrac-git · 2015-08-12T17:17:51Z

Changed commit from 72c50be to 8641677

videlec · 2015-08-12T17:18:12Z

Author: Vincent Delecroix

vbraun · 2015-08-20T20:34:43Z

Changed commit from 4d8ec2a to none

vbraun · 2015-08-20T20:34:43Z

comment:37

Fails on ARM

sage -t --long src/sage/combinat/rigged_configurations/rigged_configurations.py
**********************************************************************
File "src/sage/combinat/rigged_configurations/rigged_configurations.py", line 252, in sage.combinat.rigged_configurations.rigged_configurations.RiggedConfigurations
Failed example:
    RC.list()
Expected:
    [
    <BLANKLINE>
                                             0[ ]0
    (/)  (/)      (/)      -1[ ]-1  -1[ ]-1
                                             -1[ ]-1
    (/)  -1[ ]-1  0[ ]0    0[ ]0    1[ ]1    -1[ ]-1
    <BLANKLINE>
    (/)  (/)      -1[ ]-1  (/)      -1[ ]-1  0[ ]0
       ,        ,        ,        ,        ,
    ]
Got:
    [
    <BLANKLINE>
                                             0[ ]0  
    (/)  (/)      -1[ ]-1  -1[ ]-1  (/)             
                                             -1[ ]-1
    (/)  -1[ ]-1  0[ ]0    1[ ]1    0[ ]0    -1[ ]-1
    <BLANKLINE>
    (/)  (/)      (/)      -1[ ]-1  -1[ ]-1  0[ ]0  
       ,        ,        ,        ,        ,        
    ]
**********************************************************************
1 item had failures:
   1 of  38 in sage.combinat.rigged_configurations.rigged_configurations.RiggedConfigurations
    [239 tests, 1 failure, 250.36 s]

vbraun · 2015-08-20T20:35:58Z

Commit: 4d8ec2a

vbraun · 2015-08-20T20:35:58Z

Last 10 new commits:

`ab52a2d`	Trac 18246: fix `__hash__` in algebras
`3dfe73e`	Trac 18246: fix `__hash__` in homology
`148ad98`	Trac 18246: fix `__hash__` in quadratic_forms
`124871c`	`Trac 18246: fix doctests for QuadraticForm`
`1e59d3a`	`Trac 18246: fix some hash values on 32-bit system`
`e9a8971`	`Trac 18246: use WithEqualityById`
`072a017`	`Trac 18246: more cleanup`
`0bf7d7d`	`Trac 18246: typo`
`a722920`	`Trac 18246: fix a doctest in rigged_configurations.py`
`4d8ec2a`	`Trac 18246: refix rigged_configurations`

vbraun · 2015-08-20T20:35:58Z

Changed branch from 4d8ec2a to public/18246

tscrim · 2015-08-20T21:56:26Z

comment:39

I actually don't like these changes:

-class VectorPartitions(Parent, UniqueRepresentation):
+class VectorPartitions(UniqueRepresentation, Parent):

Why does UniqueRepresentation have to come before Parent? If this how things must be, then we should create a class URParent (or a better name), use that all over Sage to avoid this issue. (FYI: Before this ticket, there are 107 classes which use UR, Parent and 107 which use Parent, UR.)

Also can someone explain to me why are RiggedConfigurations now showing machine dependent iteration order?

nbruin · 2015-08-20T23:47:15Z

comment:40

Replying to @tscrim:

I actually don't like these changes:
-class VectorPartitions(Parent, UniqueRepresentation):
+class VectorPartitions(UniqueRepresentation, Parent):
Why does UniqueRepresentation have to come before Parent?

Because UniqueRepresentation provides a hash that is fast and appropriate and Parent doesn't:

sage: Parent.__hash__
<slot wrapper '__hash__' of 'sage.structure.category_object.CategoryObject' objects>
sage: UniqueRepresentation.__hash__
<slot wrapper '__hash__' of 'sage.misc.fast_methods.WithEqualityById' objects>

In order to get the MRO right, UniqueRepresentation needs to appear before Parent:

sage: class A(UniqueRepresentation, Parent): pass
sage: A.__hash__
<slot wrapper '__hash__' of 'sage.misc.fast_methods.WithEqualityById' objects>
sage: class B(Parent, UniqueRepresentation): pass
sage: B.__hash__
<slot wrapper '__hash__' of 'sage.structure.category_object.CategoryObject' objects>

Once all default hashes have been deleted and no classes in the MRO of Parent offer a hash function, the order doesn't matter. Until then, UniqueRepresentation has to come first.

Also can someone explain to me why are RiggedConfigurations now showing machine dependent iteration order?

The code is hard to follow, but in general, if enumeration somewhere involves a set or a dictionary, then results depend heavily on the hash used and the order in which the dictionary was constructed. I'd expect that a changed hash causes things to be enumerated in a different order (because a set or dict is storing its entries in a different order somewhere)

nbruin · 2015-09-04T06:35:01Z

comment:42

Looks good, tests pass, very desirable change. Thanks!

nbruin · 2015-09-04T06:36:09Z

Changed reviewer from Volker Braun to Volker Braun, Nils Bruin

vbraun · 2015-09-04T23:52:18Z

Changed branch from public/18246 to 4d8ec2a

vbraun · 2015-09-06T21:01:44Z

Changed branch from 4d8ec2a to public/18246

vbraun · 2015-09-06T21:01:44Z

comment:45

More random test failures:

sage -t --long src/sage/combinat/rigged_configurations/rigged_configurations.py
**********************************************************************
File "src/sage/combinat/rigged_configurations/rigged_configurations.py", line 252, in sage.combinat.rigged_configurations.rigged_configurations.RiggedConfigurations
Failed example:
    RC.list()
Expected:
    [
    <BLANKLINE>
                                             0[ ]0
    (/)  (/)      (/)      -1[ ]-1  -1[ ]-1
                                             -1[ ]-1
    (/)  -1[ ]-1  0[ ]0    0[ ]0    1[ ]1    -1[ ]-1
    <BLANKLINE>
    (/)  (/)      -1[ ]-1  (/)      -1[ ]-1  0[ ]0
       ,        ,        ,        ,        ,
    ]
Got:
    [
    <BLANKLINE>
                                             0[ ]0  
    (/)  (/)      -1[ ]-1  -1[ ]-1  (/)             
                                             -1[ ]-1
    (/)  -1[ ]-1  0[ ]0    1[ ]1    0[ ]0    -1[ ]-1
    <BLANKLINE>
    (/)  (/)      (/)      -1[ ]-1  -1[ ]-1  0[ ]0  
       ,        ,        ,        ,        ,        
    ]
**********************************************************************
1 item had failures:
   1 of  38 in sage.combinat.rigged_configurations.rigged_configurations.RiggedConfigurations
    [239 tests, 1 failure, 99.45 s]

sagetrac-git · 2015-09-06T21:49:31Z

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

`1ae9393`	`merge 18246 in Sage-6.9.beta5`
`5627a1d`	`Trac 18246: fixed random output`

sagetrac-git · 2015-09-06T21:49:31Z

Changed commit from 4d8ec2a to 5627a1d

videlec · 2015-09-06T21:50:25Z

comment:49

Hoping this is the only failure...

vbraun · 2015-09-07T17:12:51Z

Changed branch from public/18246 to 5627a1d

videlec added this to the sage-6.7 milestone Apr 18, 2015

videlec added c: coercion labels Apr 18, 2015

This comment has been minimized.

Sign in to view

videlec added the s: needs review label Aug 12, 2015

videlec modified the milestones: sage-6.7, sage-6.9 Aug 12, 2015

vbraun closed this as completed Aug 14, 2015

vbraun reopened this Aug 20, 2015

videlec added the s: needs review label Sep 4, 2015

nbruin added s: positive review and removed s: needs review labels Sep 4, 2015

vbraun removed the s: positive review label Sep 4, 2015

vbraun closed this as completed Sep 4, 2015

vbraun reopened this Sep 6, 2015

videlec added s: needs review and removed s: needs review labels Sep 6, 2015

vbraun removed the s: positive review label Sep 7, 2015

vbraun closed this as completed in 4b26783 Sep 7, 2015

nathanncohen mannequin mentioned this issue Oct 28, 2015

Better hash for Element #19016

Closed

remove naive __hash__ from SageObject #18246

remove naive __hash__ from SageObject #18246

Comments

videlec commented Apr 18, 2015

videlec commented Apr 18, 2015

videlec commented Apr 18, 2015

videlec commented Apr 18, 2015

This comment has been minimized.

nathanncohen mannequin commented Apr 18, 2015

nathanncohen mannequin commented Apr 18, 2015

sagetrac-git mannequin commented Apr 18, 2015

sagetrac-git mannequin commented Apr 18, 2015

videlec commented Apr 18, 2015

nathanncohen mannequin commented Apr 18, 2015

sagetrac-git mannequin commented Apr 18, 2015

sagetrac-git mannequin commented Apr 18, 2015

sagetrac-git mannequin commented Apr 18, 2015

sagetrac-git mannequin commented Apr 18, 2015

videlec commented Apr 18, 2015

sagetrac-git mannequin commented Aug 12, 2015

sagetrac-git mannequin commented Aug 12, 2015

videlec commented Aug 12, 2015

sagetrac-git mannequin commented Aug 12, 2015

sagetrac-git mannequin commented Aug 12, 2015

sagetrac-git mannequin commented Aug 12, 2015

sagetrac-git mannequin commented Aug 12, 2015

videlec commented Aug 12, 2015

vbraun commented Aug 20, 2015

vbraun commented Aug 20, 2015

vbraun commented Aug 20, 2015

vbraun commented Aug 20, 2015

vbraun commented Aug 20, 2015

tscrim commented Aug 20, 2015

nbruin commented Aug 20, 2015

nbruin commented Sep 4, 2015

nbruin commented Sep 4, 2015

vbraun commented Sep 4, 2015

vbraun commented Sep 6, 2015

vbraun commented Sep 6, 2015

sagetrac-git mannequin commented Sep 6, 2015

sagetrac-git mannequin commented Sep 6, 2015

videlec commented Sep 6, 2015

vbraun commented Sep 7, 2015

remove naive hash from SageObject #18246

remove naive hash from SageObject #18246