Opened 4 years ago

Closed 4 years ago

#19331 closed enhancement (fixed)

Make Element.__hash__ return 0 by default

Reported by: vdelecroix Owned by:
Priority: blocker Milestone: sage-duplicate/invalid/wontfix
Component: misc Keywords:
Cc: ncohen Merged in:
Authors: Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

In #19321 a stopgap is implemented in Element that would end up with a lot of annoying messages. We propose another solution (actually we follow the initial proposition from #19016): return 0 as a default hash.

This ticket is just an alternative to #19321.

Change History (9)

comment:1 Changed 4 years ago by vdelecroix

  • Branch set to u/vdelecroix/19331
  • Status changed from new to needs_review

comment:2 Changed 4 years ago by git

  • Commit set to 64053a2645456e605061a24952568e3c5e1f51e2

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

64053a2Trac 19331: return 0 as a default hash for Element

comment:3 Changed 4 years ago by vdelecroix

The only problem seems to be about the output order... only a tiny bit of work needed to make it efficient.

comment:4 Changed 4 years ago by nbruin

Changing the runtime cost of data structures from what it should be should not be taken lightly. I don't think this change leads to acceptable behaviour (and it will be harder to find what's wrong: a hashing error is easier to debug)

class A(object):
  def __init__(self,N):
    self.N=N
  def __hash__(self):
    return 0
  def __eq__(self,other):
    return isinstance(other,A) and self.N==other.N
  def __call__(self):
    return self.N

class B(object):
  def __init__(self,N):
    self.N=N
  def __hash__(self):
    return hash(self.N)
  def __eq__(self,other):
    return isinstance(other,B) and self.N==other.N
  def __call__(self):
    return self.N

@cached_function
def T(a):
  return a()
sage: %timeit( [T(B(n)) for n in range(10000)])
100 loops, best of 3: 14.3 ms per loop
sage: %timeit( [T(A(n)) for n in range(10000)])
1 loops, best of 3: 25.8 s per loop

Or, with a smaller cache it's still bad (I've cleaned the cache):

sage: %timeit( [T(A(n)) for n in range(100)])
100 loops, best of 3: 2.22 ms per loop
sage: %timeit( [T(B(n)) for n in range(100)])
10000 loops, best of 3: 181 µs per loop

Even for a dictionary of size 10, the trivial hash still causes a 4x slowdown.

A change like this can push code that runs correctly in sage at present to a point where running it is not practical. I seriously think there may be a user out there that has an application that depends on this code. This change would break sage for him in that respect. I am strongly -1 to introducing something like that in a release candidate, just before release, because we wouldn't catch it.

comment:5 Changed 4 years ago by jdemeyer

  • Status changed from needs_review to needs_work

Many doctest failures...

comment:6 Changed 4 years ago by vbraun

  • Milestone changed from sage-6.9 to sage-6.10

comment:7 Changed 4 years ago by nbruin

  • Milestone changed from sage-6.10 to sage-duplicate/invalid/wontfix
  • Status changed from needs_work to needs_review

with #19016 merged we don't need this ticket anymore.

comment:8 Changed 4 years ago by vdelecroix

  • Authors Vincent Delecroix deleted
  • Branch u/vdelecroix/19331 deleted
  • Commit 64053a2645456e605061a24952568e3c5e1f51e2 deleted
  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to positive_review

Right!

comment:9 Changed 4 years ago by vbraun

  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.