#11794: Optional cythonised cached hash for Python classes
----------------------------------+--------------------------
Reporter: SimonKing | Owner: jason
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-6.4
Component: misc | Resolution:
Keywords: | Merged in:
Authors: Simon King | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: #11115, #11791 | Stopgaps:
----------------------------------+--------------------------
Description changed by chapoton:
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.
>
> Apply [attachment:trac11794_fast_hash_metaclass.patch]
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]
--
--
Ticket URL: <http://trac.sagemath.org/ticket/11794#comment:20>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
