Opened 8 years ago

Closed 5 years ago

#8119 closed defect (fixed)

Rename change the hash value of some objects

Reported by: hivert Owned by: tbd
Priority: major Milestone: sage-5.0
Component: misc Keywords:
Cc: jason, SimonKing Merged in: sage-5.0.rc0
Authors: Robert Bradshaw Reviewers: Florent Hivert, Nicolas M. Thiéry, Nicolas Borie
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by hivert)

For many objects the hash value is computed from __repr__. This is a bad idea since renaming the object change its hash value.

sage: bla = PolynomialRing(ZZ,"x")
sage: hash(bla)
-1525918542791298668
sage: bla.rename("toto")
sage: hash(bla)
2314052222105390764

Apply Only:

  1. 8119-parent-hash-final.patch

Attachments (6)

8119-parent-hash.patch (2.6 KB) - added by robertwb 8 years ago.
8119-parent-hash-review.patch (4.1 KB) - added by hivert 7 years ago.
8119-parent-hash.2.patch (2.6 KB) - added by robertwb 6 years ago.
8119-parent-hash.3.patch (2.7 KB) - added by hivert 6 years ago.
8119-parent-hash-final-fix32.patch (6.6 KB) - added by nthiery 6 years ago.
8119-parent-hash-final.patch (6.6 KB) - added by hivert 5 years ago.

Download all attachments as: .zip

Change History (36)

comment:1 Changed 8 years ago by robertwb

For immutable objects, like Parents, the default hash could store the value used the first time it is computed. This doesn't solve the problem of

sage: bla = PolynomialRing(ZZ,"x")
sage: hash(bla['t'])
-1733828288
sage: bla.rename("toto")
sage: hash(bla['t'])
-1924319844

Changed 8 years ago by robertwb

comment:2 follow-up: Changed 8 years ago by robertwb

  • Milestone set to sage-4.3.4
  • Status changed from new to needs_review

This is a partial fix (that won't work for SageObject? in general, unless we enforce that mutable objects maintain their own hash, and I don't think we want to put an extra field on all Elements), but resolves the most important case. It's also a performance gain.

comment:3 in reply to: ↑ 2 ; follow-up: Changed 8 years ago by hivert

Hi Robert,

I've one question related to this and I like to have the confirmation from an expert. After your patch, upon pickling/unpickling the hash value can change because it is not pickled and neither is the name, right ? As far as I manage to test this is not harmful to pickle a dict containing a renamed parent. Indeed, trying to read cPickle.c, I understood that the dict is reconstructed from it's items and thus even if the hash changed the element is inserted correctly in the dict during unpickling. Can you confirm this ?

If this is not both this patch and #8120 are broken.

Also, after this, do you still need #8506 ?

Florent

comment:4 in reply to: ↑ 3 Changed 8 years ago by robertwb

Replying to hivert:

Hi Robert,

I've one question related to this and I like to have the confirmation from an expert. After your patch, upon pickling/unpickling the hash value can change because it is not pickled and neither is the name, right ? As far as I manage to test this is not harmful to pickle a dict containing a renamed parent. Indeed, trying to read cPickle.c, I understood that the dict is reconstructed from it's items and thus even if the hash changed the element is inserted correctly in the dict during unpickling. Can you confirm this ?

That is correct. Hashes in general are not guaranteed to be consistent from run to run, all that really matters is that they satisfy (to the best they can) the equality constraints.

If this is not both this patch and #8120 are broken.

Also, after this, do you still need #8506 ?

Yes, #8506 is still important--in my case I'm reducing a curve mod many, many primes, doing just a bit of stuff on each before throwing them away. I suppose eventually caching the hash value would eventually be a win, but that's a separate optimization.

comment:5 Changed 8 years ago by jason

  • Cc jason added

comment:6 follow-up: Changed 7 years ago by jason

hivert: do you want to review this ticket?

comment:7 in reply to: ↑ 6 ; follow-up: Changed 7 years ago by hivert

  • Reviewers set to Florent Hivert
  • Status changed from needs_review to needs_work

hivert: do you want to review this ticket?

Sure ! I completely forgot about this one. Sorry !

They are a few place where we should remove the bad implementation using __repr__ since they all inherits from CategoryObject:

popcorn-*ge-combinat/sage $ grep "hash(self.__repr__())" **/*.py*
groups/group.pyx:        return hash(self.__repr__())
modules/module.pyx:        return hash(self.__repr__())
modules/module.pyx:        return hash(self.__repr__())
rings/polynomial/multi_polynomial_libsingular.pyx:        return hash(self.__repr__())
rings/ring.pyx:        return hash(self.__repr__())
structure/sage_object.pyx:        return hash(self.__repr__())

I don't have time to do it right now. I'll do it soon if you don't beat me.

comment:8 in reply to: ↑ 7 Changed 7 years ago by hivert

  • Description modified (diff)
  • Status changed from needs_work to needs_review

They are a few place where we should remove the bad implementation using __repr__ since they all inherits from CategoryObject:

I just added a review patch which removes the wrong hash methods.

Please review. I'm ok with the original patch, so if my review patch is ok you can put a positive review on my behalf.

Changed 7 years ago by hivert

comment:9 Changed 6 years ago by nthiery

  • Authors set to Robert Bradshaw
  • Reviewers changed from Florent Hivert to Florent Hivert, Nicolas M. Thiéry
  • Status changed from needs_review to needs_work

Florent's review patch looks good. However consistant should be written consistent in the first patch. I also did not yet set a positive review because of the ongoing discussion on sage-devel. Please feel free to go ahead and set a positive review once the typo is fixed and if it is decided that the PolynomialRing? issue shall be fixed in a follow up patch.

Cheers,

Nicolas

Changed 6 years ago by robertwb

comment:10 Changed 6 years ago by robertwb

  • Status changed from needs_work to positive_review

Fixed the typo, I don't think the issue with sparse PolynomialRing? #11231 should hold this ticket up any longer (it's had a patch sitting on it for over a year...)

comment:11 Changed 6 years ago by jdemeyer

  • Description modified (diff)
  • Milestone changed from sage-4.7 to sage-4.7.1

I'm assuming the "apply" should be changed...

comment:12 Changed 6 years ago by jdemeyer

  • Status changed from positive_review to needs_work

Please change the commit message of 8119-parent-hash.2.patch (use hg qrefresh -e for that).

Changed 6 years ago by hivert

comment:13 Changed 6 years ago by hivert

  • Description modified (diff)
  • Status changed from needs_work to needs_review

I just re-uploaded roberts patch with a correct log message. I'm not sure I'm allowed to put a positive review though.

Florent

comment:14 follow-up: Changed 6 years ago by nthiery

  • Status changed from needs_review to needs_work

Bonjour Florent!

I am not sure the log message for 8119-parent-hash-review.patch is proper. While you are at it, I'd suggest to just fold it in the other patch. The review history does not bring much information here, so having a single patch will give a better overview to the future reader.

I'll set a positive review right after.

comment:15 in reply to: ↑ 14 Changed 6 years ago by hivert

  • Description modified (diff)

I'd suggest to just fold it in the other patch.

Done.

comment:16 Changed 6 years ago by hivert

  • Status changed from needs_work to needs_review

comment:17 Changed 6 years ago by nthiery

  • Status changed from needs_review to positive_review

Thanks!

It seems the buildbot is getting confused about which patch to apply though.

comment:18 Changed 6 years ago by robertwb

Apply 8119-parent-hash-final.patch

Granted, the patchbot doesn't bother testing positively reviewed tickets (not that anything it's concerned with changed). Thanks for getting to this for me.

comment:19 Changed 6 years ago by jdemeyer

  • Status changed from positive_review to needs_work
  • Work issues set to fix on 32-bit

Some of these doctests should be differentiated on 32-bit systems (in particular, all the results of hash()).

comment:20 Changed 6 years ago by jdemeyer

*bump*

comment:21 Changed 6 years ago by nborie

  • Description modified (diff)
  • Status changed from needs_work to needs_review

comment:22 Changed 6 years ago by hivert

  • Reviewers changed from Florent Hivert, Nicolas M. Thiéry to Florent Hivert, Nicolas M. Thiéry, Nicolas Borie
  • Status changed from needs_review to positive_review
  • Work issues fix on 32-bit deleted

comment:23 follow-up: Changed 6 years ago by jdemeyer

  • Status changed from positive_review to needs_work

On boxen (Linux x86_64), I get:

sage -t  -force_lib devel/sage/sage/structure/category_object.pyx
**********************************************************************
File "/padic/scratch/jdemeyer/merger/sage-5.0.beta14/devel/sage-main/sage/structure/category_object.pyx", line 757:
    sage: hash(bla)
Expected:
    -1525918542791298668
Got:
    -5279516879544852222
**********************************************************************
File "/padic/scratch/jdemeyer/merger/sage-5.0.beta14/devel/sage-main/sage/structure/category_object.pyx", line 761:
    sage: hash(bla)
Expected:
    -1525918542791298668
Got:
    -5279516879544852222
**********************************************************************

Changed 6 years ago by nthiery

comment:24 in reply to: ↑ 23 Changed 6 years ago by nthiery

Replying to jdemeyer:

On boxen (Linux x86_64), I get:

sage -t  -force_lib devel/sage/sage/structure/category_object.pyx
**********************************************************************
File "/padic/scratch/jdemeyer/merger/sage-5.0.beta14/devel/sage-main/sage/structure/category_object.pyx", line 757:
    sage: hash(bla)
Expected:
    -1525918542791298668
Got:
    -5279516879544852222
**********************************************************************
File "/padic/scratch/jdemeyer/merger/sage-5.0.beta14/devel/sage-main/sage/structure/category_object.pyx", line 761:
    sage: hash(bla)
Expected:
    -1525918542791298668
Got:
    -5279516879544852222
**********************************************************************

Weird, I get here the same result as you on boxen, both with 4.8 and 5.0.beta8. I don't know how a wrong return value ended up in the patch.

Oh well, I updated the patch to expect the result obtained on boxen.

comment:25 Changed 6 years ago by nthiery

  • Status changed from needs_work to needs_review

comment:26 Changed 6 years ago by davidloeffler

Apply 8119-parent-hash-final-fix32.patch

(for patchbot)

comment:27 Changed 5 years ago by SimonKing

  • Cc SimonKing added

Changed 5 years ago by hivert

comment:28 Changed 5 years ago by hivert

  • Description modified (diff)
  • Status changed from needs_review to positive_review

Hi there,

I'm setting a positive review here but I uploaded a new patch removing a trailling whitespace which bothered the patchbot. The only difference between 8119-parent-hash-final-fix32.patch and 8119-parent-hash-final.patch is the trailling space (and of course Mercurials header), so I don't think a new review is needed.

Florent

comment:29 Changed 5 years ago by nthiery

Thanks for the final review!

comment:30 Changed 5 years ago by jdemeyer

  • Merged in set to sage-5.0.rc0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.