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: sage-6.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 vdelecroix)

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 vdelecroix

  • Branch set to public/18246
  • Commit set to a7aa08f9a30c97fd080edb9f35c89717605bd59e

New commits:

a7aa08fTrac 18246: remove __hash__ from Sage object

comment:2 Changed 6 years ago by vdelecroix

  • Description modified (diff)

comment:3 Changed 6 years ago by ncohen

sage: hash(SageObject())
8751828132417

I am fixing it.

comment:4 Changed 6 years ago by ncohen

As expected everything breaks. What do we do?

comment:5 Changed 6 years ago by git

  • Commit changed from a7aa08f9a30c97fd080edb9f35c89717605bd59e to 6b9f883e8e2a9f8fe369506cb56fe3bcba6e05e0

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

6b9f883trac #18246: raise NotImplementedError

comment:6 Changed 6 years ago by vdelecroix

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 ncohen

TypeError ? Well, why not...

comment:8 Changed 6 years ago by git

  • Commit changed from 6b9f883e8e2a9f8fe369506cb56fe3bcba6e05e0 to 2869bc2f9a15669dd9e80bd19dc06ac2c784dbf4

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

2869bc2trac #18246: raise TypeError

comment:9 Changed 6 years ago by git

  • Commit changed from 2869bc2f9a15669dd9e80bd19dc06ac2c784dbf4 to 61b0fce34f4cf9607c369ebfe95c5a5837f56381

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

631e5c1Trac 18236: more explicit TypeError message
61b0fceTrac 18246: make all test pass in sage/rings

comment:10 Changed 6 years ago by vdelecroix

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 git

  • Commit changed from 61b0fce34f4cf9607c369ebfe95c5a5837f56381 to 5a1e636b7ed86d4f635adc2cf72bc270cc9e59d0

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

46a1f74Trac 18246: remove __hash__ from Sage object
4e53eeeTrac 18246: fix polynomial term order
2282b78Trac 18246: fix __hash__ in rings
9f4ea07Trac 18246: fix __hash__ in plot
a4e58ebTrac 18246: fix __hash__ in geometry
5a1e636Trac 18246: fix __hash__ in combinat

comment:12 Changed 5 years ago by vdelecroix

Let us see how much patchbot is happy...

comment:13 Changed 5 years ago by git

  • Commit changed from 5a1e636b7ed86d4f635adc2cf72bc270cc9e59d0 to 72c50be2cb2dff2435bf136072f9ab1cfabb2ff7

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

d53c30eTrac 18246: fix __hash__ in algebras
518c3c2Trac 18246: fix __hash__ in homology
72c50beFix 18246: fix __hash__ in quadratic_forms

comment:14 Changed 5 years ago by git

  • Commit changed from 72c50be2cb2dff2435bf136072f9ab1cfabb2ff7 to 86416778fd8768bfb2fcaff42c357671e40333d6

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

8641677Trac 18246: fix __hash__ in quadratic_forms

comment:15 Changed 5 years ago by vdelecroix

  • Authors set to Vincent Delecroix
  • Milestone changed from sage-6.7 to sage-6.9
  • Status changed from new to needs_review

comment:16 Changed 5 years ago by vbraun

lgtm but seems to have some test failures on the patchbot

comment:17 Changed 5 years ago by vdelecroix

Yep. Some object have random hash because it relies on their id... will fix that soonly.

comment:18 Changed 5 years ago by git

  • Commit changed from 86416778fd8768bfb2fcaff42c357671e40333d6 to 6f97f74e3c72db3c84d3e17fe751fc29fa10906a

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

6f97f74Trac 18246: fix doctests for QuadraticForm

comment:19 Changed 5 years ago by vdelecroix

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 vbraun

  • Reviewers set to Volker Braun
  • Status changed from needs_review to positive_review

comment:22 Changed 5 years ago by git

  • Commit changed from 6f97f74e3c72db3c84d3e17fe751fc29fa10906a to 813231b402621c063793062fda218452895bf769

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

d5b74acTrac 18246: fix some hash values on 32-bit system
813231bTrac 18246: hash_by_id/HashById

comment:23 Changed 5 years ago by vdelecroix

  • 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 vdelecroix

  • Description modified (diff)
  • Summary changed from remove __hash__ from SageObject to remove naive __hash__ from SageObject

comment:25 Changed 5 years ago by git

  • Commit changed from 813231b402621c063793062fda218452895bf769 to 96f4fb49902dd6c2f92d8a64e5ecf43eaf1db6d0

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

b5c9dc9Trac 18246: forgot an import in a doctest
96f4fb4Trac 18246: more cleanup

comment:26 Changed 5 years ago by vdelecroix

  • Status changed from needs_review to needs_work

Oups. I duplicated sage.misc.fast_method.WithEqualityById...

comment:27 Changed 5 years ago by git

  • Commit changed from 96f4fb49902dd6c2f92d8a64e5ecf43eaf1db6d0 to d723750739d60bcd653697dc658eec1f52123801

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

bcc23ceTrac 18246: use WithEqualityById
d723750Trac 18246: more cleanup

comment:28 Changed 5 years ago by git

  • Commit changed from d723750739d60bcd653697dc658eec1f52123801 to cbb42e1935a97a10191a1ca93be939fd275c7ab7

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

5e4b7b9Trac 18246: use WithEqualityById
cbb42e1Trac 18246: more cleanup

comment:29 Changed 5 years ago by vdelecroix

  • 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 ncohen

the name misc.fast_methods does not look very appropriate *for a module*.

comment:31 Changed 5 years ago by git

  • Commit changed from cbb42e1935a97a10191a1ca93be939fd275c7ab7 to 56402445284123c1045503de322324470af08e9d

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

5640244Trac 18246: typo

comment:32 Changed 5 years ago by git

  • Commit changed from 56402445284123c1045503de322324470af08e9d to a72292076043e6d73214642c981f3475c7345aef

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

e57cc4cTrac 18246: fix __hash__ in combinat
ab52a2dTrac 18246: fix __hash__ in algebras
3dfe73eTrac 18246: fix __hash__ in homology
148ad98Trac 18246: fix __hash__ in quadratic_forms
124871cTrac 18246: fix doctests for QuadraticForm
1e59d3aTrac 18246: fix some hash values on 32-bit system
e9a8971Trac 18246: use WithEqualityById
072a017Trac 18246: more cleanup
0bf7d7dTrac 18246: typo
a722920Trac 18246: fix a doctest in rigged_configurations.py

comment:33 Changed 5 years ago by vdelecroix

rebased on sage-6.9.beta2 + fix one failing doctest

comment:34 Changed 5 years ago by git

  • Commit changed from a72292076043e6d73214642c981f3475c7345aef to 4d8ec2a1282b24064f93bc8bea5fe23ec08f1750

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

4d8ec2aTrac 18246: refix rigged_configurations

comment:35 Changed 5 years ago by vdelecroix

green light :-)

comment:36 Changed 5 years ago by vbraun

  • 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 vbraun

  • 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 vbraun

  • Branch changed from 4d8ec2a1282b24064f93bc8bea5fe23ec08f1750 to public/18246
  • Commit set to 4d8ec2a1282b24064f93bc8bea5fe23ec08f1750

Last 10 new commits:

ab52a2dTrac 18246: fix __hash__ in algebras
3dfe73eTrac 18246: fix __hash__ in homology
148ad98Trac 18246: fix __hash__ in quadratic_forms
124871cTrac 18246: fix doctests for QuadraticForm
1e59d3aTrac 18246: fix some hash values on 32-bit system
e9a8971Trac 18246: use WithEqualityById
072a017Trac 18246: more cleanup
0bf7d7dTrac 18246: typo
a722920Trac 18246: fix a doctest in rigged_configurations.py
4d8ec2aTrac 18246: refix rigged_configurations

comment:39 follow-up: Changed 5 years ago by tscrim

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 nbruin

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)

comment:41 Changed 5 years ago by vdelecroix

  • Status changed from new to needs_review

comment:42 Changed 5 years ago by nbruin

  • Status changed from needs_review to positive_review

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

comment:43 Changed 5 years ago by nbruin

  • Reviewers changed from Volker Braun to Volker Braun, Nils Bruin

comment:44 Changed 5 years ago by vbraun

  • 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 vbraun

  • 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 git

  • Commit changed from 4d8ec2a1282b24064f93bc8bea5fe23ec08f1750 to 5627a1dc936fa159765904f3e0025fdcfd4be232

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

1ae9393merge 18246 in Sage-6.9.beta5
5627a1dTrac 18246: fixed random output

comment:47 Changed 5 years ago by vdelecroix

  • Status changed from new to needs_review

comment:48 Changed 5 years ago by vdelecroix

  • Status changed from needs_review to positive_review

comment:49 Changed 5 years ago by vdelecroix

Hoping this is the only failure...

comment:50 Changed 5 years ago by vbraun

  • Branch changed from public/18246 to 5627a1dc936fa159765904f3e0025fdcfd4be232
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.