Opened 6 years ago
Closed 5 years ago
#18246 closed defect (fixed)
remove naive __hash__ from SageObject
Reported by:  vdelecroix  Owned by:  

Priority:  major  Milestone:  sage6.9 
Component:  coercion  Keywords:  
Cc:  ncohen  Merged in:  
Authors:  Vincent Delecroix  Reviewers:  Volker Braun, Nils Bruin 
Report Upstream:  N/A  Work issues:  
Branch:  5627a1d (Commits)  Commit:  5627a1dc936fa159765904f3e0025fdcfd4be232 
Dependencies:  Stopgaps: 
Description (last modified by )
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:
 #18215 for quadratic number field elements (in relation with polyhedra #18241)
 #18239 for permutation group elements
See also #19016 for a ticket with the same purpose (with Element
instead of SageObject
).
Change History (50)
comment:1 Changed 6 years ago by
 Branch set to public/18246
 Commit set to a7aa08f9a30c97fd080edb9f35c89717605bd59e
comment:2 Changed 6 years ago by
 Description modified (diff)
comment:3 Changed 6 years ago by
sage: hash(SageObject()) 8751828132417
I am fixing it.
comment:4 Changed 6 years ago by
As expected everything breaks. What do we do?
comment:5 Changed 6 years ago by
 Commit changed from a7aa08f9a30c97fd080edb9f35c89717605bd59e to 6b9f883e8e2a9f8fe369506cb56fe3bcba6e05e0
Branch pushed to git repo; I updated commit sha1. New commits:
6b9f883  trac #18246: raise NotImplementedError

comment:6 Changed 6 years ago by
You should raise a TypeError
if you want to raise something. Otherwise it breaks too much stuff (in particular cached_method
, cached_function
)
comment:7 Changed 6 years ago by
TypeError
? Well, why not...
comment:8 Changed 6 years ago by
 Commit changed from 6b9f883e8e2a9f8fe369506cb56fe3bcba6e05e0 to 2869bc2f9a15669dd9e80bd19dc06ac2c784dbf4
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
2869bc2  trac #18246: raise TypeError

comment:9 Changed 6 years ago by
 Commit changed from 2869bc2f9a15669dd9e80bd19dc06ac2c784dbf4 to 61b0fce34f4cf9607c369ebfe95c5a5837f56381
comment:10 Changed 6 years ago by
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.
comment:11 Changed 5 years ago by
 Commit changed from 61b0fce34f4cf9607c369ebfe95c5a5837f56381 to 5a1e636b7ed86d4f635adc2cf72bc270cc9e59d0
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

comment:12 Changed 5 years ago by
Let us see how much patchbot is happy...
comment:13 Changed 5 years ago by
 Commit changed from 5a1e636b7ed86d4f635adc2cf72bc270cc9e59d0 to 72c50be2cb2dff2435bf136072f9ab1cfabb2ff7
comment:14 Changed 5 years ago by
 Commit changed from 72c50be2cb2dff2435bf136072f9ab1cfabb2ff7 to 86416778fd8768bfb2fcaff42c357671e40333d6
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
8641677  Trac 18246: fix __hash__ in quadratic_forms

comment:15 Changed 5 years ago by
 Milestone changed from sage6.7 to sage6.9
 Status changed from new to needs_review
comment:16 Changed 5 years ago by
lgtm but seems to have some test failures on the patchbot
comment:17 Changed 5 years ago by
Yep. Some object have random hash because it relies on their id
... will fix that soonly.
comment:18 Changed 5 years ago by
 Commit changed from 86416778fd8768bfb2fcaff42c357671e40333d6 to 6f97f74e3c72db3c84d3e17fe751fc29fa10906a
Branch pushed to git repo; I updated commit sha1. New commits:
6f97f74  Trac 18246: fix doctests for QuadraticForm

comment:19 Changed 5 years ago by
The failing doctest in bibd.py
is a separate issue, see #19020 (but I was not able to reproduce it!).
comment:20 Changed 5 years ago by
 Reviewers set to Volker Braun
 Status changed from needs_review to positive_review
comment:21 Changed 5 years ago by
 Status changed from positive_review to needs_work
comment:22 Changed 5 years ago by
 Commit changed from 6f97f74e3c72db3c84d3e17fe751fc29fa10906a to 813231b402621c063793062fda218452895bf769
comment:23 Changed 5 years ago by
 Status changed from needs_work to needs_review
def __hash__(self): return id(self)
was a very bad idea of mine.
It is now as clean as possible... I hope.
comment:24 Changed 5 years ago by
 Description modified (diff)
 Summary changed from remove __hash__ from SageObject to remove naive __hash__ from SageObject
comment:25 Changed 5 years ago by
 Commit changed from 813231b402621c063793062fda218452895bf769 to 96f4fb49902dd6c2f92d8a64e5ecf43eaf1db6d0
comment:26 Changed 5 years ago by
 Status changed from needs_review to needs_work
Oups. I duplicated sage.misc.fast_method.WithEqualityById
...
comment:27 Changed 5 years ago by
 Commit changed from 96f4fb49902dd6c2f92d8a64e5ecf43eaf1db6d0 to d723750739d60bcd653697dc658eec1f52123801
comment:28 Changed 5 years ago by
 Commit changed from d723750739d60bcd653697dc658eec1f52123801 to cbb42e1935a97a10191a1ca93be939fd275c7ab7
comment:29 Changed 5 years ago by
 Status changed from needs_work to needs_review
I used WithEqualityById
instead. But the place misc.fast_methods
does not look very appropriate for it.
comment:30 Changed 5 years ago by
the name misc.fast_methods
does not look very appropriate *for a module*.
comment:31 Changed 5 years ago by
 Commit changed from cbb42e1935a97a10191a1ca93be939fd275c7ab7 to 56402445284123c1045503de322324470af08e9d
Branch pushed to git repo; I updated commit sha1. New commits:
5640244  Trac 18246: typo

comment:32 Changed 5 years ago by
 Commit changed from 56402445284123c1045503de322324470af08e9d to a72292076043e6d73214642c981f3475c7345aef
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
e57cc4c  Trac 18246: fix __hash__ in combinat

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 32bit 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

comment:33 Changed 5 years ago by
rebased on sage6.9.beta2 + fix one failing doctest
comment:34 Changed 5 years ago by
 Commit changed from a72292076043e6d73214642c981f3475c7345aef to 4d8ec2a1282b24064f93bc8bea5fe23ec08f1750
Branch pushed to git repo; I updated commit sha1. New commits:
4d8ec2a  Trac 18246: refix rigged_configurations

comment:35 Changed 5 years ago by
green light :)
comment:36 Changed 5 years ago by
 Branch changed from public/18246 to 4d8ec2a1282b24064f93bc8bea5fe23ec08f1750
 Resolution set to fixed
 Status changed from needs_review to closed
comment:37 Changed 5 years ago by
 Commit 4d8ec2a1282b24064f93bc8bea5fe23ec08f1750 deleted
 Resolution fixed deleted
 Status changed from closed to new
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]
comment:38 Changed 5 years ago by
 Branch changed from 4d8ec2a1282b24064f93bc8bea5fe23ec08f1750 to public/18246
 Commit set to 4d8ec2a1282b24064f93bc8bea5fe23ec08f1750
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 32bit 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

comment:39 followup: ↓ 40 Changed 5 years ago by
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?
comment:40 in reply to: ↑ 39 Changed 5 years ago by
Replying to tscrim:
I actually don't like these changes:
class VectorPartitions(Parent, UniqueRepresentation): +class VectorPartitions(UniqueRepresentation, Parent):Why does
UniqueRepresentation
have to come beforeParent
?
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)
comment:41 Changed 5 years ago by
 Status changed from new to needs_review
comment:42 Changed 5 years ago by
 Status changed from needs_review to positive_review
Looks good, tests pass, very desirable change. Thanks!
comment:43 Changed 5 years ago by
 Reviewers changed from Volker Braun to Volker Braun, Nils Bruin
comment:44 Changed 5 years ago by
 Branch changed from public/18246 to 4d8ec2a1282b24064f93bc8bea5fe23ec08f1750
 Resolution set to fixed
 Status changed from positive_review to closed
comment:45 Changed 5 years ago by
 Branch changed from 4d8ec2a1282b24064f93bc8bea5fe23ec08f1750 to public/18246
 Resolution fixed deleted
 Status changed from closed to new
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]
comment:46 Changed 5 years ago by
 Commit changed from 4d8ec2a1282b24064f93bc8bea5fe23ec08f1750 to 5627a1dc936fa159765904f3e0025fdcfd4be232
comment:47 Changed 5 years ago by
 Status changed from new to needs_review
comment:48 Changed 5 years ago by
 Status changed from needs_review to positive_review
comment:49 Changed 5 years ago by
Hoping this is the only failure...
comment:50 Changed 5 years ago by
 Branch changed from public/18246 to 5627a1dc936fa159765904f3e0025fdcfd4be232
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
Trac 18246: remove __hash__ from Sage object