#11794: Optional cythonised cached hash for Python classes
---------------------------+------------------------------------------------
Reporter: SimonKing | Owner: jason
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.7.2
Component: misc | Keywords:
Work_issues: | Upstream: N/A
Reviewer: | Author: Simon King
Merged: | Dependencies: #11115, #11791
---------------------------+------------------------------------------------
Old description:
> By default, the hash of an instance is obtained from the string
> representation. It would be computed over and over again, which is slow:
> {{{
> sage: from sage.structure.parent import Parent
> sage: P = Parent()
> sage: P.__hash__??
> Type: method-wrapper
> Base Class: <type 'method-wrapper'>
> String Form: <method-wrapper '__hash__' of
> sage.structure.parent.Parent object at 0x53809b0>
> Namespace: Interactive
> Definition: P.__hash__(self)
> Source:
> def __hash__(self):
> return hash(self.__repr__())
> sage: timeit("hash(P)")
> 625 loops, best of 3: 19.4 µs per loop
> }}}
>
> Of course, a solution is to cache the hash once it is computed. This is
> done, for instance, in polynomial rings, and it is much faster:
> {{{
> sage: P.<x> = QQ[]
> sage: P.__hash__??
> Type: instancemethod
> Base Class: <type 'instancemethod'>
> String Form: <bound method PolynomialRing_field_with_category.__hash__
> of Univariate Polynomial Ring in x over Rational Field>
> Namespace: Interactive
> File:
> /mnt/local/king/SAGE/sandbox/sage-4.7.2.alpha2/local/lib/python2.6/site-
> packages/sage/rings/polynomial/polynomial_ring.py
> Definition: P.__hash__(self)
> Source:
> def __hash__(self):
> # should be faster than just relying on the string representation
> try:
> return self._cached_hash
> except AttributeError:
> pass
> h = self._cached_hash =
> hash((self.base_ring(),self.variable_name()))
> return h
> sage: timeit("hash(P)")
> 625 loops, best of 3: 3.08 µs per loop
> }}}
>
> Even more speed is possible if the hash method is written in Cython.
>
> However, it would probably be unfeasible to rewrite all of Sage such that
> the hash is inherited from a cdef'd class, and also it may not be wanted
> to cache the hash.
>
> What I am proposing here is a metaclass, that provides the option to add
> a cached cythonised hash method to any class.
New description:
By default, the hash of an instance is obtained from the string
representation. It would be computed over and over again, which is slow:
{{{
sage: from sage.structure.parent import Parent
sage: P = Parent()
sage: P.__hash__??
Type: method-wrapper
Base Class: <type 'method-wrapper'>
String Form: <method-wrapper '__hash__' of sage.structure.parent.Parent
object at 0x53809b0>
Namespace: Interactive
Definition: P.__hash__(self)
Source:
def __hash__(self):
return hash(self.__repr__())
sage: timeit("hash(P)")
625 loops, best of 3: 19.4 µs per loop
}}}
Of course, a solution is to cache the hash once it is computed. This is
done, for instance, in polynomial rings, and it is much faster:
{{{
sage: P.<x> = QQ[]
sage: P.__hash__??
Type: instancemethod
Base Class: <type 'instancemethod'>
String Form: <bound method PolynomialRing_field_with_category.__hash__
of Univariate Polynomial Ring in x over Rational Field>
Namespace: Interactive
File:
/mnt/local/king/SAGE/sandbox/sage-4.7.2.alpha2/local/lib/python2.6/site-
packages/sage/rings/polynomial/polynomial_ring.py
Definition: P.__hash__(self)
Source:
def __hash__(self):
# should be faster than just relying on the string representation
try:
return self._cached_hash
except AttributeError:
pass
h = self._cached_hash =
hash((self.base_ring(),self.variable_name()))
return h
sage: timeit("hash(P)")
625 loops, best of 3: 3.08 µs per loop
}}}
Even more speed is possible if the hash method is written in Cython.
However, it would probably be unfeasible to rewrite all of Sage such that
the hash is inherited from a cdef'd class, and also it may not be wanted
to cache the hash.
What I am proposing here is a metaclass, that provides the option to add a
cached cythonised hash method to any class.
Apply [attachment:trac11794_fast_hash_metaclass.patch]
--
Comment(by SimonKing):
For the patchbot:
Apply trac11794_fast_hash_metaclass.patch
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11794#comment:3>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
