Cached Functions and Methods¶
AUTHORS:
 William Stein: initial version, (inspired by conversation with Justin Walker)
 Mike Hansen: added doctests and made it work with class methods.
 Willem Jan Palenstijn: add CachedMethodCaller for binding cached methods to instances.
 Tom Boothby: added DiskCachedFunction.
 Simon King: improved performance, more doctests, cython version, CachedMethodCallerNoArgs, weak cached function, cached special methods.
 Julian Rueth (20140319, 20140509, 20140512): added
key
parameter, allow caching for unhashable elements, addeddo_pickle
parameter
EXAMPLES:
By trac ticket #11115, cached functions and methods are now also available in Cython code. The following examples cover various ways of usage.
Python functions:
sage: @cached_function
....: def test_pfunc(x):
....: '''
....: Some documentation
....: '''
....: return x
sage: test_pfunc(5) is test_pfunc(5)
True
In some cases, one would only want to keep the result in cache as long
as there is any other reference to the result. By trac ticket #12215, this is
enabled for UniqueRepresentation
,
which is used to create unique parents: If an algebraic structure, such
as a finite field, is only temporarily used, then it will not stay in
cache forever. That behaviour is implemented using weak_cached_function
,
that behaves the same as cached_function
, except that it uses a
CachedWeakValueDictionary
for storing the results.
Cython cdef functions do not allow arbitrary decorators. However, one can wrap a Cython function and turn it into a cached function, by trac ticket #11115. We need to provide the name that the wrapped method or function should have, since otherwise the name of the original function would be used:
sage: cython('''cpdef test_funct(x): return x''')
sage: wrapped_funct = cached_function(test_funct, name='wrapped_funct')
sage: wrapped_funct
Cached version of <builtin function test_funct>
sage: wrapped_funct.__name__
'wrapped_funct'
sage: wrapped_funct(5)
5
sage: wrapped_funct(5) is wrapped_funct(5)
True
We can proceed similarly for cached methods of Cython classes,
provided that they allow attribute assignment or have a public
attribute __cached_methods
of type <dict>
. Since
trac ticket #11115, this is the case for all classes inheriting from
Parent
. See below for a more explicit
example. By trac ticket #12951, cached methods of extension classes can
be defined by simply using the decorator. However, an indirect
approach is still needed for cpdef methods:
sage: cython_code = ['cpdef test_meth(self,x):',
....: ' "some doc for a wrapped cython method"',
....: ' return x',
....: 'from sage.all import cached_method',
....: 'from sage.structure.parent cimport Parent',
....: 'cdef class MyClass(Parent):',
....: ' @cached_method',
....: ' def direct_method(self, x):',
....: ' "Some doc for direct method"',
....: ' return 2*x',
....: ' wrapped_method = cached_method(test_meth,name="wrapped_method")']
sage: cython(os.linesep.join(cython_code))
sage: O = MyClass()
sage: O.direct_method
Cached version of <method 'direct_method' of '...MyClass' objects>
sage: O.wrapped_method
Cached version of <builtin function test_meth>
sage: O.wrapped_method.__name__
'wrapped_method'
sage: O.wrapped_method(5)
5
sage: O.wrapped_method(5) is O.wrapped_method(5)
True
sage: O.direct_method(5)
10
sage: O.direct_method(5) is O.direct_method(5)
True
In some cases, one would only want to keep the result in cache as long
as there is any other reference to the result. By trac ticket #12215, this is
enabled for UniqueRepresentation
,
which is used to create unique parents: If an algebraic structure, such
as a finite field, is only temporarily used, then it will not stay in
cache forever. That behaviour is implemented using weak_cached_function
,
that behaves the same as cached_function
, except that it uses a
CachedWeakValueDictionary
for storing the results.
By trac ticket #11115, even if a parent does not allow attribute assignment, it can inherit a cached method from the parent class of a category (previously, the cache would have been broken):
sage: cython_code = ["from sage.all import cached_method, cached_in_parent_method, Category, Objects",
....: "class MyCategory(Category):",
....: " @cached_method",
....: " def super_categories(self):",
....: " return [Objects()]",
....: " class ElementMethods:",
....: " @cached_method",
....: " def element_cache_test(self):",
....: " return self",
....: " @cached_in_parent_method",
....: " def element_via_parent_test(self):",
....: " return self",
....: " class ParentMethods:",
....: " @cached_method",
....: " def one(self):",
....: " return self.element_class(self,1)",
....: " @cached_method",
....: " def invert(self, x):",
....: " return x"]
sage: cython('\n'.join(cython_code))
sage: C = MyCategory()
In order to keep the memory footprint of elements small, it was
decided to not support the same freedom of using cached methods
for elements: If an instance of a class derived from
Element
does not allow attribute
assignment, then a cached method inherited from the category of
its parent will break, as in the class MyBrokenElement
below.
However, there is a class ElementWithCachedMethod
that has generally a slower attribute access, but fully supports
cached methods. We remark, however, that cached methods are
much faster if attribute access works. So, we expect that
ElementWithCachedMethod
will
hardly by used.
sage: cython_code = ["from sage.structure.element cimport Element, ElementWithCachedMethod", "from cpython.object cimport PyObject_RichCompare",
....: "cdef class MyBrokenElement(Element):",
....: " cdef public object x",
....: " def __init__(self,P,x):",
....: " self.x=x",
....: " Element.__init__(self,P)",
....: " def __neg__(self):",
....: " return MyBrokenElement(self.parent(),self.x)",
....: " def _repr_(self):",
....: " return '<%s>'%self.x",
....: " def __hash__(self):",
....: " return hash(self.x)",
....: " cpdef _richcmp_(left, right, int op):",
....: " return PyObject_RichCompare(left.x, right.x, op)",
....: " def raw_test(self):",
....: " return self",
....: "cdef class MyElement(ElementWithCachedMethod):",
....: " cdef public object x",
....: " def __init__(self,P,x):",
....: " self.x=x",
....: " ElementWithCachedMethod.__init__(self,P)",
....: " def __neg__(self):",
....: " return MyElement(self.parent(),self.x)",
....: " def _repr_(self):",
....: " return '<%s>'%self.x",
....: " def __hash__(self):",
....: " return hash(self.x)",
....: " cpdef _richcmp_(left, right, int op):",
....: " return PyObject_RichCompare(left.x, right.x, op)",
....: " def raw_test(self):",
....: " return self",
....: "from sage.structure.parent cimport Parent",
....: "cdef class MyParent(Parent):",
....: " Element = MyElement"]
sage: cython('\n'.join(cython_code))
sage: P = MyParent(category=C)
sage: ebroken = MyBrokenElement(P,5)
sage: e = MyElement(P,5)
The cached methods inherited by the parent works:
sage: P.one()
<1>
sage: P.one() is P.one()
True
sage: P.invert(e)
<5>
sage: P.invert(e) is P.invert(e)
True
The cached methods inherited by MyElement
works:
sage: e.element_cache_test()
<5>
sage: e.element_cache_test() is e.element_cache_test()
True
sage: e.element_via_parent_test()
<5>
sage: e.element_via_parent_test() is e.element_via_parent_test()
True
The other element class can only inherit a cached_in_parent_method
, since
the cache is stored in the parent. In fact, equal elements share the cache,
even if they are of different types:
sage: e == ebroken
True
sage: type(e) == type(ebroken)
False
sage: ebroken.element_via_parent_test() is e.element_via_parent_test()
True
However, the cache of the other inherited method breaks, although the method as such works:
sage: ebroken.element_cache_test()
<5>
sage: ebroken.element_cache_test() is ebroken.element_cache_test()
False
The cache can be emptied:
sage: a = test_pfunc(5)
sage: test_pfunc.clear_cache()
sage: a is test_pfunc(5)
False
sage: a = P.one()
sage: P.one.clear_cache()
sage: a is P.one()
False
Since e
and ebroken
share the cache, when we empty it for one element
it is empty for the other as well:
sage: b = ebroken.element_via_parent_test()
sage: e.element_via_parent_test.clear_cache()
sage: b is ebroken.element_via_parent_test()
False
Introspection works:
sage: from sage.misc.edit_module import file_and_line
sage: from sage.misc.sageinspect import sage_getdoc, sage_getfile, sage_getsource
sage: print(sage_getdoc(test_pfunc))
Some documentation
sage: print(sage_getdoc(O.wrapped_method))
some doc for a wrapped cython method
sage: print(sage_getdoc(O.direct_method))
Some doc for direct method
sage: print(sage_getsource(O.wrapped_method))
cpdef test_meth(self,x):
"some doc for a wrapped cython method"
return x
sage: print(sage_getsource(O.direct_method))
def direct_method(self, x):
"Some doc for direct method"
return 2*x
It is a very common special case to cache a method that has no
arguments. In that special case, the time needed to access the cache
can be drastically reduced by using a special implementation. The
cached method decorator automatically determines which implementation
ought to be chosen. A typical example is
sage.rings.polynomial.multi_polynomial_ideal.MPolynomialIdeal.gens()
(no arguments) versus
sage.rings.polynomial.multi_polynomial_ideal.MPolynomialIdeal.groebner_basis()
(several arguments):
sage: P.<a,b,c,d> = QQ[]
sage: I = P*[a,b]
sage: I.gens()
[a, b]
sage: I.gens() is I.gens()
True
sage: I.groebner_basis()
[a, b]
sage: I.groebner_basis() is I.groebner_basis()
True
sage: type(I.gens)
<type 'sage.misc.cachefunc.CachedMethodCallerNoArgs'>
sage: type(I.groebner_basis)
<type 'sage.misc.cachefunc.CachedMethodCaller'>
By trac ticket #12951, the cached_method decorator is also supported on nonc(p)def
methods of extension classes, as long as they either support attribute assignment
or have a public attribute of type <dict>
called __cached_methods
. The
latter is easy:
sage: cython_code = [
....: "from sage.misc.cachefunc import cached_method",
....: "cdef class MyClass:",
....: " cdef public dict __cached_methods",
....: " @cached_method",
....: " def f(self, a,b):",
....: " return a*b"]
sage: cython(os.linesep.join(cython_code))
sage: P = MyClass()
sage: P.f(2,3)
6
sage: P.f(2,3) is P.f(2,3)
True
Providing attribute access is a bit more tricky, since it is needed that
an attribute inherited by the instance from its class can be overridden
on the instance. That is why providing a __getattr__
would not be
enough in the following example:
sage: cython_code = [
....: "from sage.misc.cachefunc import cached_method",
....: "cdef class MyOtherClass:",
....: " cdef dict D",
....: " def __init__(self):",
....: " self.D = {}",
....: " def __setattr__(self, n,v):",
....: " self.D[n] = v",
....: " def __getattribute__(self, n):",
....: " try:",
....: " return self.D[n]",
....: " except KeyError:",
....: " pass",
....: " return getattr(type(self),n).__get__(self)",
....: " @cached_method",
....: " def f(self, a,b):",
....: " return a+b"]
sage: cython(os.linesep.join(cython_code))
sage: Q = MyOtherClass()
sage: Q.f(2,3)
5
sage: Q.f(2,3) is Q.f(2,3)
True
Note that supporting attribute access is somehow faster than the easier method:
sage: timeit("a = P.f(2,3)") # random
625 loops, best of 3: 1.3 µs per loop
sage: timeit("a = Q.f(2,3)") # random
625 loops, best of 3: 931 ns per loop
Some immutable objects (such as \(p\)adic numbers) cannot implement a
reasonable hash function because their ==
operator has been
modified to return True
for objects which might behave differently
in some computations:
sage: K.<a> = Qq(9)
sage: b = a.add_bigoh(1)
sage: c = a + 3
sage: b
a + O(3)
sage: c
a + 3 + O(3^20)
sage: b == c
True
sage: b == a
True
sage: c == a
False
If such objects defined a nontrivial hash function, this would break
caching in many places. However, such objects should still be usable
in caches. This can be achieved by defining an appropriate method
_cache_key
:
sage: hash(b)
Traceback (most recent call last):
...
TypeError: unhashable type: 'sage.rings.padics.qadic_flint_CR.qAdicCappedRelativeElement'
sage: @cached_method
....: def f(x): return x == a
sage: f(b)
True
sage: f(c) # if b and c were hashable, this would return True
False
sage: b._cache_key()
(..., ((0, 1),), 0, 1)
sage: c._cache_key()
(..., ((0, 1), (1,)), 0, 20)
Note
This attribute will only be accessed if the object itself is not hashable.
An implementation must make sure that for elements a
and b
,
if a != b
, then also a._cache_key() != b._cache_key()
.
In practice this means that the _cache_key
should always include
the parent as its first argument:
sage: S.<a> = Qq(4)
sage: d = a.add_bigoh(1)
sage: b._cache_key() == d._cache_key() # this would be True if the parents were not included
False

class
sage.misc.cachefunc.
CacheDict
¶ Bases:
dict

class
sage.misc.cachefunc.
CachedFunction
¶ Bases:
object
Create a cached version of a function, which only recomputes values it hasn’t already computed. Synonyme:
cached_function
INPUT:
f
– a functionname
– (optional string) name that the cached version off
should be provided withkey
– (optional callable) takes the input and returns a key for the cache, typically one would use this to normalize inputdo_pickle
– (optional boolean) whether or not the contents of the cache should be included when pickling this function; the default is not to include them.
If
f
is a function, do eitherg = CachedFunction(f)
org = cached_function(f)
to make a cached version off
, or put@cached_function
right before the definition off
(i.e., use Python decorators):@cached_function def f(...): ....
The inputs to the function must be hashable or they must define
sage.structure.sage_object.SageObject._cache_key()
.EXAMPLES:
sage: @cached_function ....: def mul(x, y=2): ....: return x*y sage: mul(3) 6
We demonstrate that the result is cached, and that, moreover, the cache takes into account the various ways of providing default arguments:
sage: mul(3) is mul(3,2) True sage: mul(3,y=2) is mul(3,2) True
The user can clear the cache:
sage: a = mul(4) sage: mul.clear_cache() sage: a is mul(4) False
It is also possible to explicitly override the cache with a different value:
sage: mul.set_cache('foo',5) sage: mul(5,2) 'foo'
The parameter
key
can be used to ignore parameters for caching. In this example we ignore the parameteralgorithm
:sage: @cached_function(key=lambda x,y,algorithm: (x,y)) ....: def mul(x, y, algorithm="default"): ....: return x*y sage: mul(1,1,algorithm="default") is mul(1,1,algorithm="algorithm") is mul(1,1) is mul(1,1,'default') True

cache
¶

cached
(*args, **kwds)¶ Return the result from the cache if available. If the value is not cached, raise
KeyError
.EXAMPLES:
sage: @cached_function ....: def f(x): ....: return x sage: f.cached(5) Traceback (most recent call last): ... KeyError: ((5,), ()) sage: f(5) 5 sage: f.cached(5) 5

clear_cache
()¶ Clear the cache dictionary.
EXAMPLES:
sage: g = CachedFunction(number_of_partitions) sage: a = g(5) sage: g.cache {((5, 'default'), ()): 7} sage: g.clear_cache() sage: g.cache {}

f
¶

get_key
(*args, **kwds)¶ Return the key in the cache to be used when
args
andkwds
are passed in as parameters.EXAMPLES:
sage: @cached_function ....: def foo(x): ....: return x^2 sage: foo(2) 4 sage: foo.get_key(2) ((2,), ()) sage: foo.get_key(x=3) ((3,), ())
Examples for cached methods:
sage: class Foo: ....: def __init__(self, x): ....: self._x = x ....: @cached_method ....: def f(self, y, z=0): ....: return self._x * y + z sage: a = Foo(2) sage: z = a.f(37) sage: k = a.f.get_key(37); k ((37, 0), ()) sage: a.f.cache[k] is z True
Note that the method does not test whether there are too many arguments, or wrong argument names:
sage: a.f.get_key(1,2,3,x=4,y=5,z=6) ((1, 2, 3), (('x', 4), ('y', 5), ('z', 6)))
It does, however, take into account the different ways of providing named arguments, possibly with a default value:
sage: a.f.get_key(5) ((5, 0), ()) sage: a.f.get_key(y=5) ((5, 0), ()) sage: a.f.get_key(5,0) ((5, 0), ()) sage: a.f.get_key(5,z=0) ((5, 0), ()) sage: a.f.get_key(y=5,z=0) ((5, 0), ())

is_in_cache
(*args, **kwds)¶ Checks if the argument list is in the cache.
EXAMPLES:
sage: class Foo: ....: def __init__(self, x): ....: self._x = x ....: @cached_method ....: def f(self, z, y=0): ....: return self._x*z+y sage: a = Foo(2) sage: a.f.is_in_cache(3) False sage: a.f(3) 6 sage: a.f.is_in_cache(3,y=0) True

precompute
(arglist, num_processes=1)¶ Cache values for a number of inputs. Do the computation in parallel, and only bother to compute values that we haven’t already cached.
INPUT:
arglist
– list (or iterables) of arguments for which the method shall be precomputed.num_processes
– number of processes used byparallel()
EXAMPLES:
sage: @cached_function ....: def oddprime_factors(n): ....: l = [p for p,e in factor(n) if p != 2] ....: return len(l) sage: oddprime_factors.precompute(range(1,100), 4) sage: oddprime_factors.cache[(25,),()] 1

set_cache
(value, *args, **kwds)¶ Set the value for those args and keyword args Mind the unintuitive syntax (value first). Any idea on how to improve that welcome!
EXAMPLES:
sage: g = CachedFunction(number_of_partitions) sage: a = g(5) sage: g.cache {((5, 'default'), ()): 7} sage: g.set_cache(17, 5) sage: g.cache {((5, 'default'), ()): 17} sage: g(5) 17
sage: g(5) = 19 # todo: not implemented sage: g(5) # todo: not implemented 19

class
sage.misc.cachefunc.
CachedInParentMethod
¶ Bases:
sage.misc.cachefunc.CachedMethod
A decorator that creates a cached version of an instance method of a class.
In contrast to
CachedMethod
, the cache dictionary is an attribute of the parent of the instance to which the method belongs.ASSUMPTION:
This way of caching works only if
 the instances have a parent, and
 the instances are hashable (they are part of the cache key) or they
define
sage.structure.sage_object.SageObject._cache_key()
NOTE:
For proper behavior, the method must be a pure function (no side effects). If this decorator is used on a method, it will have identical output on equal elements. This is since the element is part of the hash key. Arguments to the method must be hashable or define
sage.structure.sage_object.SageObject._cache_key()
. The instance it is assigned to must be hashable.Examples can be found at
cachefunc
.

class
sage.misc.cachefunc.
CachedMethod
¶ Bases:
object
A decorator that creates a cached version of an instance method of a class.
Note
For proper behavior, the method must be a pure function (no side effects). Arguments to the method must be hashable or transformed into something hashable using
key
or they must definesage.structure.sage_object.SageObject._cache_key()
.EXAMPLES:
sage: class Foo(object): ....: @cached_method ....: def f(self, t, x=2): ....: print('computing') ....: return t**x sage: a = Foo()
The example shows that the actual computation takes place only once, and that the result is identical for equivalent input:
sage: res = a.f(3, 2); res computing 9 sage: a.f(t = 3, x = 2) is res True sage: a.f(3) is res True
Note, however, that the
CachedMethod
is replaced by aCachedMethodCaller
orCachedMethodCallerNoArgs
as soon as it is bound to an instance or class:sage: P.<a,b,c,d> = QQ[] sage: I = P*[a,b] sage: type(I.__class__.gens) <type 'sage.misc.cachefunc.CachedMethodCallerNoArgs'>
So, you would hardly ever see an instance of this class alive.
The parameter
key
can be used to pass a function which creates a custom cache key for inputs. In the following example, this parameter is used to ignore thealgorithm
keyword for caching:sage: class A(object): ....: def _f_normalize(self, x, algorithm): return x ....: @cached_method(key=_f_normalize) ....: def f(self, x, algorithm='default'): return x sage: a = A() sage: a.f(1, algorithm="default") is a.f(1) is a.f(1, algorithm="algorithm") True
The parameter
do_pickle
can be used to enable pickling of the cache. Usually the cache is not stored when pickling:sage: class A(object): ....: @cached_method ....: def f(self, x): return None sage: import __main__ sage: __main__.A = A sage: a = A() sage: a.f(1) sage: len(a.f.cache) 1 sage: b = loads(dumps(a)) sage: len(b.f.cache) 0
When
do_pickle
is set, the pickle contains the contents of the cache:sage: class A(object): ....: @cached_method(do_pickle=True) ....: def f(self, x): return None sage: __main__.A = A sage: a = A() sage: a.f(1) sage: len(a.f.cache) 1 sage: b = loads(dumps(a)) sage: len(b.f.cache) 1
Cached methods can not be copied like usual methods, see trac ticket #12603. Copying them can lead to very surprising results:
sage: class A: ....: @cached_method ....: def f(self): ....: return 1 sage: class B: ....: g=A.f ....: def f(self): ....: return 2 sage: b=B() sage: b.f() 2 sage: b.g() 1 sage: b.f() 1

class
sage.misc.cachefunc.
CachedMethodCaller
¶ Bases:
sage.misc.cachefunc.CachedFunction
Utility class that is used by
CachedMethod
to bind a cached method to an instance.Note
Since trac ticket #11115, there is a special implementation
CachedMethodCallerNoArgs
for methods that do not take arguments.EXAMPLES:
sage: class A: ....: @cached_method ....: def bar(self,x): ....: return x^2 sage: a = A() sage: a.bar Cached version of <function bar at 0x...> sage: type(a.bar) <type 'sage.misc.cachefunc.CachedMethodCaller'> sage: a.bar(2) is a.bar(x=2) True

cached
(*args, **kwds)¶ Return the result from the cache if available. If the value is not cached, raise
KeyError
.EXAMPLES:
sage: class CachedMethodTest(object): ....: @cached_method ....: def f(self, x): ....: return x sage: o = CachedMethodTest() sage: CachedMethodTest.f.cached(o, 5) Traceback (most recent call last): ... KeyError: ((5,), ()) sage: o.f.cached(5) Traceback (most recent call last): ... KeyError: ((5,), ()) sage: o.f(5) 5 sage: CachedMethodTest.f.cached(o, 5) 5 sage: o.f.cached(5) 5

precompute
(arglist, num_processes=1)¶ Cache values for a number of inputs. Do the computation in parallel, and only bother to compute values that we haven’t already cached.
INPUT:
arglist
– list (or iterables) of arguments for which the method shall be precomputed.num_processes
– number of processes used byparallel()
EXAMPLES:
sage: class Foo(object): ....: @cached_method ....: def f(self, i): ....: return i^2 sage: foo = Foo() sage: foo.f(3) 9 sage: foo.f(1) 1 sage: foo.f.precompute(range(2), 2) sage: foo.f.cache == {((0,), ()): 0, ((1,), ()): 1, ((3,), ()): 9} True


class
sage.misc.cachefunc.
CachedMethodCallerNoArgs
¶ Bases:
sage.misc.cachefunc.CachedFunction
Utility class that is used by
CachedMethod
to bind a cached method to an instance, in the case of a method that does not accept any arguments exceptself
.Note
The return value
None
would not be cached. So, if you have a method that does not accept arguments and may returnNone
after a lengthy computation, then@cached_method
should not be used.EXAMPLES:
sage: P.<a,b,c,d> = QQ[] sage: I = P*[a,b] sage: I.gens Cached version of <function gens at 0x...> sage: type(I.gens) <type 'sage.misc.cachefunc.CachedMethodCallerNoArgs'> sage: I.gens is I.gens True sage: I.gens() is I.gens() True
AUTHOR:
 Simon King (201104)

clear_cache
()¶ Clear the cache dictionary.
EXAMPLES:
sage: P.<a,b,c,d> = QQ[] sage: I = P*[a,b] sage: I.gens() [a, b] sage: I.gens.set_cache('bar') sage: I.gens() 'bar'
The cache can be emptied and thus the original value will be reconstructed:
sage: I.gens.clear_cache() sage: I.gens() [a, b]

is_in_cache
()¶ Answers whether the return value is already in the cache.
Note
Recall that a cached method without arguments can not cache the return value
None
.EXAMPLES:
sage: P.<x,y> = QQ[] sage: I = P*[x,y] sage: I.gens.is_in_cache() False sage: I.gens() [x, y] sage: I.gens.is_in_cache() True

set_cache
(value)¶ Override the cache with a specific value.
Note
None
is not suitable for a cached value. It would be interpreted as an empty cache, forcing a new computation.EXAMPLES:
sage: P.<a,b,c,d> = QQ[] sage: I = P*[a,b] sage: I.gens() [a, b] sage: I.gens.set_cache('bar') sage: I.gens() 'bar'
The cache can be emptied and thus the original value will be reconstructed:
sage: I.gens.clear_cache() sage: I.gens() [a, b]
The attempt to assign
None
to the cache fails:sage: I.gens.set_cache(None) sage: I.gens() [a, b]

class
sage.misc.cachefunc.
CachedMethodPickle
(inst, name, cache=None)¶ Bases:
object
This class helps to unpickle cached methods.
Note
Since trac ticket #8611, a cached method is an attribute of the instance (provided that it has a
__dict__
). Hence, when pickling the instance, it would be attempted to pickle that attribute as well, but this is a problem, since functions can not be pickled, currently. Therefore, we replace the actual cached method by a place holder, that kills itself as soon as any attribute is requested. Then, the original cached attribute is reinstated. But the cached values are in fact saved (if \(do_pickle\) is set.)EXAMPLES:
sage: R.<x, y, z> = PolynomialRing(QQ, 3) sage: I = R*(x^3 + y^3 + z^3,x^4y^4) sage: I.groebner_basis() [y^5*z^3  1/4*x^2*z^6 + 1/2*x*y*z^6 + 1/4*y^2*z^6, x^2*y*z^3  x*y^2*z^3 + 2*y^3*z^3 + z^6, x*y^3 + y^4 + x*z^3, x^3 + y^3 + z^3] sage: I.groebner_basis Cached version of <function groebner_basis at 0x...>
We now pickle and unpickle the ideal. The cached method
groebner_basis
is replaced by a placeholder:sage: J = loads(dumps(I)) sage: J.groebner_basis Pickle of the cached method "groebner_basis"
But as soon as any other attribute is requested from the placeholder, it replaces itself by the cached method, and the entries of the cache are actually preserved:
sage: J.groebner_basis.is_in_cache() True sage: J.groebner_basis Cached version of <function groebner_basis at 0x...> sage: J.groebner_basis() == I.groebner_basis() True
AUTHOR:
 Simon King (201101)

class
sage.misc.cachefunc.
CachedSpecialMethod
¶ Bases:
sage.misc.cachefunc.CachedMethod
Cached version of special python methods.
IMPLEMENTATION:
For new style classes
C
, it is not possible to override a special method, such as__hash__
, in the__dict__
of an instancec
ofC
, because Python will for efficiency reasons always use what is provided by the class, not by the instance.By consequence, if
__hash__
would be wrapped by usingCachedMethod
, thenhash(c)
will accessC.__hash__
and bind it toc
, which means that the__get__
method ofCachedMethod
will be called. But there, we assume that Python has already inspected__dict__
, and thus aCachedMethodCaller
will be created over and over again.Here, the
__get__
method will explicitly access the__dict__
, so thathash(c)
will rely on a singleCachedMethodCaller
stored in the__dict__
.EXAMPLES:
sage: class C: ....: @cached_method ....: def __hash__(self): ....: print("compute hash") ....: return int(5) ....: sage: c = C() sage: type(C.__hash__) <type 'sage.misc.cachefunc.CachedMethodCallerNoArgs'>
The hash is computed only once, subsequent calls will use the value from the cache. This was implemented in trac ticket #12601.
sage: hash(c) # indirect doctest compute hash 5 sage: hash(c) 5

class
sage.misc.cachefunc.
DiskCachedFunction
(f, dir, memory_cache=False, key=None)¶ Bases:
sage.misc.cachefunc.CachedFunction
Works similar to CachedFunction, but instead, we keep the cache on disk (optionally, we keep it in memory too).
EXAMPLES:
sage: from sage.misc.cachefunc import DiskCachedFunction sage: dir = tmp_dir() sage: factor = DiskCachedFunction(factor, dir, memory_cache=True) sage: f = factor(2775); f 3 * 5^2 * 37 sage: f is factor(2775) True

class
sage.misc.cachefunc.
FileCache
(dir, prefix='', memory_cache=False)¶ Bases:
object
FileCache
is a dictionarylike class which stores keys and values on disk. The keys take the form of a tuple(A,K)
A
is a tuple of objectst
where eacht
is an exact object which is uniquely identified by a short string.K
is a tuple of tuples(s,v)
wheres
is a valid variable name andv
is an exact object which is uniquely identified by a short string with letters [azAZ09._]
The primary use case is the
DiskCachedFunction
. Ifmemory_cache == True
, we maintain a cache of objects seen during this session in memory – but we don’t load them from disk until necessary. The keys and values are stored in a pair of files:prefixargstring.key.sobj
contains thekey
only,prefixargstring.sobj
contains the tuple(key,val)
where
self[key] == val
.Note
We assume that each
FileCache
lives in its own directory. Use extreme caution if you wish to break that assumption.
clear
()¶ Clear all key, value pairs from self and unlink the associated files from the file cache.
EXAMPLES:
sage: from sage.misc.cachefunc import FileCache sage: dir = tmp_dir() sage: FC1 = FileCache(dir, memory_cache=False, prefix='foo') sage: FC2 = FileCache(dir, memory_cache=False, prefix='foo') sage: k1 = ((), (('a', 1),)) sage: t1 = randint(0, 1000) sage: k2 = ((), (('b', 1),)) sage: t2 = randint(0, 1000) sage: FC1[k1] = t1 sage: FC2[k2] = t2 sage: FC2.clear() sage: k1 in FC1 False sage: k2 in FC1 False

file_list
()¶ Return the list of files corresponding to
self
.EXAMPLES:
sage: from sage.misc.cachefunc import FileCache sage: dir = tmp_dir() sage: FC = FileCache(dir, memory_cache = True, prefix='t') sage: FC[((),())] = 1 sage: FC[((1,2),())] = 2 sage: FC[((1,),(('a',1),))] = 3 sage: for f in sorted(FC.file_list()): print(f[len(dir):]) t.key.sobj t.sobj t1_2.key.sobj t1_2.sobj ta1.1.key.sobj ta1.1.sobj

items
()¶ Return a list of tuples
(k,v)
whereself[k] = v
.EXAMPLES:
sage: from sage.misc.cachefunc import FileCache sage: dir = tmp_dir() sage: FC = FileCache(dir, memory_cache = False) sage: FC[((),())] = 1 sage: FC[((1,2),())] = 2 sage: FC[((1,),(('a',1),))] = 3 sage: I = FC.items() sage: I.sort(); I [(((), ()), 1), (((1,), (('a', 1),)), 3), (((1, 2), ()), 2)]

keys
()¶ Return a list of keys
k
whereself[k]
is defined.EXAMPLES:
sage: from sage.misc.cachefunc import FileCache sage: dir = tmp_dir() sage: FC = FileCache(dir, memory_cache = False) sage: FC[((),())] = 1 sage: FC[((1,2),())] = 2 sage: FC[((1,),(('a',1),))] = 3 sage: K = FC.keys() sage: K.sort(); K [((), ()), ((1,), (('a', 1),)), ((1, 2), ())]

values
()¶ Return a list of values that are stored in
self
.EXAMPLES:
sage: from sage.misc.cachefunc import FileCache sage: dir = tmp_dir() sage: FC = FileCache(dir, memory_cache = False) sage: FC[((),())] = 1 sage: FC[((1,2),())] = 2 sage: FC[((1,),(('a',1),))] = 3 sage: FC[((),(('a',1),))] = 4 sage: v = FC.values() sage: v.sort(); v [1, 2, 3, 4]

class
sage.misc.cachefunc.
GloballyCachedMethodCaller
¶ Bases:
sage.misc.cachefunc.CachedMethodCaller
Implementation of cached methods in case that the cache is not stored in the instance, but in some global object. In particular, it is used to implement
CachedInParentMethod
.The only difference is that the instance is used as part of the key.

class
sage.misc.cachefunc.
NonpicklingDict
¶ Bases:
dict
A special dict which does not pickle its contents.
EXAMPLES:
sage: from sage.misc.cachefunc import NonpicklingDict sage: d = NonpicklingDict() sage: d[0] = 0 sage: loads(dumps(d)) {}

class
sage.misc.cachefunc.
WeakCachedFunction
¶ Bases:
sage.misc.cachefunc.CachedFunction
A version of
CachedFunction
using weak references on the values.If
f
is a function, do eitherg = weak_cached_function(f)
to make a cached version off
, or put@weak_cached_function
right before the definition off
(i.e., use Python decorators):@weak_cached_function def f(...): ...
As an exception meant to improve performance, the most recently computed values are strongly referenced. The number of strongly cached values can be controlled by the
cache
keyword.EXAMPLES:
sage: from sage.misc.cachefunc import weak_cached_function sage: class A: pass sage: @weak_cached_function(cache=0) ....: def f(): ....: print("doing a computation") ....: return A() sage: a = f() doing a computation
The result is cached:
sage: b = f() sage: a is b True
However, if there are no strong references left, the result is deleted, and thus a new computation takes place:
sage: del a sage: del b sage: a = f() doing a computation
Above, we used the
cache=0
keyword. With a larger value, the most recently computed values are cached anyway, even if they are not referenced:sage: @weak_cached_function(cache=3) ....: def f(x): ....: print("doing a computation for x={}".format(x)) ....: return A() sage: a = f(1); del a doing a computation for x=1 sage: a = f(2), f(1); del a doing a computation for x=2 sage: a = f(3), f(1); del a doing a computation for x=3 sage: a = f(4), f(1); del a doing a computation for x=4 doing a computation for x=1 sage: a = f(5), f(1); del a doing a computation for x=5
The parameter
key
can be used to ignore parameters for caching. In this example we ignore the parameteralgorithm
:sage: @weak_cached_function(key=lambda x,algorithm: x) ....: def mod_ring(x, algorithm="default"): ....: return IntegerModRing(x) sage: mod_ring(1,algorithm="default") is mod_ring(1,algorithm="algorithm") is mod_ring(1) is mod_ring(1,'default') True

sage.misc.cachefunc.
cache_key
(o)¶ Helper function to return a hashable key for
o
which can be used for caching.This function is intended for objects which are not hashable such as \(p\)adic numbers. The difference from calling an object’s
_cache_key
method directly, is that it also works for tuples and unpacks them recursively (if necessary, i.e., if they are not hashable).EXAMPLES:
sage: from sage.misc.cachefunc import cache_key sage: K.<u> = Qq(9) sage: a = K(1); a 1 + O(3^20) sage: cache_key(a) (..., ((1,),), 0, 20)
This function works if
o
is a tuple. In this case it unpacks its entries recursively:sage: o = (1, 2, (3, a)) sage: cache_key(o) (1, 2, (3, (..., ((1,),), 0, 20)))
Note that tuples are only partially unpacked if some of its entries are hashable:
sage: o = (1/2, a) sage: cache_key(o) (1/2, (..., ((1,),), 0, 20))

sage.misc.cachefunc.
cached_function
(self, *args, **kwds)¶ Create a cached version of a function, which only recomputes values it hasn’t already computed. Synonyme:
cached_function
INPUT:
f
– a functionname
– (optional string) name that the cached version off
should be provided withkey
– (optional callable) takes the input and returns a key for the cache, typically one would use this to normalize inputdo_pickle
– (optional boolean) whether or not the contents of the cache should be included when pickling this function; the default is not to include them.
If
f
is a function, do eitherg = CachedFunction(f)
org = cached_function(f)
to make a cached version off
, or put@cached_function
right before the definition off
(i.e., use Python decorators):@cached_function def f(...): ....
The inputs to the function must be hashable or they must define
sage.structure.sage_object.SageObject._cache_key()
.EXAMPLES:
sage: @cached_function ....: def mul(x, y=2): ....: return x*y sage: mul(3) 6
We demonstrate that the result is cached, and that, moreover, the cache takes into account the various ways of providing default arguments:
sage: mul(3) is mul(3,2) True sage: mul(3,y=2) is mul(3,2) True
The user can clear the cache:
sage: a = mul(4) sage: mul.clear_cache() sage: a is mul(4) False
It is also possible to explicitly override the cache with a different value:
sage: mul.set_cache('foo',5) sage: mul(5,2) 'foo'
The parameter
key
can be used to ignore parameters for caching. In this example we ignore the parameteralgorithm
:sage: @cached_function(key=lambda x,y,algorithm: (x,y)) ....: def mul(x, y, algorithm="default"): ....: return x*y sage: mul(1,1,algorithm="default") is mul(1,1,algorithm="algorithm") is mul(1,1) is mul(1,1,'default') True

sage.misc.cachefunc.
cached_in_parent_method
(self, inst, *args, **kwds)¶ A decorator that creates a cached version of an instance method of a class.
In contrast to
CachedMethod
, the cache dictionary is an attribute of the parent of the instance to which the method belongs.ASSUMPTION:
This way of caching works only if
 the instances have a parent, and
 the instances are hashable (they are part of the cache key) or they
define
sage.structure.sage_object.SageObject._cache_key()
NOTE:
For proper behavior, the method must be a pure function (no side effects). If this decorator is used on a method, it will have identical output on equal elements. This is since the element is part of the hash key. Arguments to the method must be hashable or define
sage.structure.sage_object.SageObject._cache_key()
. The instance it is assigned to must be hashable.Examples can be found at
cachefunc
.

sage.misc.cachefunc.
cached_method
(f, name=None, key=None, do_pickle=None)¶ A decorator for cached methods.
EXAMPLES:
In the following examples, one can see how a cached method works in application. Below, we demonstrate what is done behind the scenes:
sage: class C: ....: @cached_method ....: def __hash__(self): ....: print("compute hash") ....: return int(5) ....: @cached_method ....: def f(self, x): ....: print("computing cached method") ....: return x*2 sage: c = C() sage: type(C.__hash__) <type 'sage.misc.cachefunc.CachedMethodCallerNoArgs'> sage: hash(c) compute hash 5
When calling a cached method for the second time with the same arguments, the value is gotten from the cache, so that a new computation is not needed:
sage: hash(c) 5 sage: c.f(4) computing cached method 8 sage: c.f(4) is c.f(4) True
Different instances have distinct caches:
sage: d = C() sage: d.f(4) is c.f(4) computing cached method False sage: d.f.clear_cache() sage: c.f(4) 8 sage: d.f(4) computing cached method 8
Using cached methods for the hash and other special methods was implemented in trac ticket #12601, by means of
CachedSpecialMethod
. We show that it is used behind the scenes:sage: cached_method(c.__hash__) <sage.misc.cachefunc.CachedSpecialMethod object at ...> sage: cached_method(c.f) <sage.misc.cachefunc.CachedMethod object at ...>
The parameter
do_pickle
can be used if the contents of the cache should be stored in a pickle of the cached method. This can be dangerous with special methods such as__hash__
:sage: class C: ....: @cached_method(do_pickle=True) ....: def __hash__(self): ....: return id(self) sage: import __main__ sage: __main__.C = C sage: c = C() sage: hash(c) # random output sage: d = loads(dumps(c)) sage: hash(d) == hash(c) True
However, the contents of a method’s cache are not pickled unless
do_pickle
is set:sage: class C: ....: @cached_method ....: def __hash__(self): ....: return id(self) sage: __main__.C = C sage: c = C() sage: hash(c) # random output sage: d = loads(dumps(c)) sage: hash(d) == hash(c) False

sage.misc.cachefunc.
dict_key
(o)¶ Return a key to cache object
o
in a dict.This is different from
cache_key
since thecache_key
might get confused with the key of a hashable object. Therefore, such keys includeunhashable_key
which acts as a unique marker which is certainly not stored in the dictionary otherwise.EXAMPLES:
sage: from sage.misc.cachefunc import dict_key sage: dict_key(42) 42 sage: K.<u> = Qq(9) sage: dict_key(u) (<object object at ...>, (..., 20))

class
sage.misc.cachefunc.
disk_cached_function
(dir, memory_cache=False, key=None)¶ Decorator for
DiskCachedFunction
.EXAMPLES:
sage: dir = tmp_dir() sage: @disk_cached_function(dir) ....: def foo(x): return next_prime(2^x)%x sage: x = foo(200);x 11 sage: @disk_cached_function(dir) ....: def foo(x): return 1/x sage: foo(200) 11 sage: foo.clear_cache() sage: foo(200) 1/200

sage.misc.cachefunc.
weak_cached_function
(self, *args, **kwds)¶ A version of
CachedFunction
using weak references on the values.If
f
is a function, do eitherg = weak_cached_function(f)
to make a cached version off
, or put@weak_cached_function
right before the definition off
(i.e., use Python decorators):@weak_cached_function def f(...): ...
As an exception meant to improve performance, the most recently computed values are strongly referenced. The number of strongly cached values can be controlled by the
cache
keyword.EXAMPLES:
sage: from sage.misc.cachefunc import weak_cached_function sage: class A: pass sage: @weak_cached_function(cache=0) ....: def f(): ....: print("doing a computation") ....: return A() sage: a = f() doing a computation
The result is cached:
sage: b = f() sage: a is b True
However, if there are no strong references left, the result is deleted, and thus a new computation takes place:
sage: del a sage: del b sage: a = f() doing a computation
Above, we used the
cache=0
keyword. With a larger value, the most recently computed values are cached anyway, even if they are not referenced:sage: @weak_cached_function(cache=3) ....: def f(x): ....: print("doing a computation for x={}".format(x)) ....: return A() sage: a = f(1); del a doing a computation for x=1 sage: a = f(2), f(1); del a doing a computation for x=2 sage: a = f(3), f(1); del a doing a computation for x=3 sage: a = f(4), f(1); del a doing a computation for x=4 doing a computation for x=1 sage: a = f(5), f(1); del a doing a computation for x=5
The parameter
key
can be used to ignore parameters for caching. In this example we ignore the parameteralgorithm
:sage: @weak_cached_function(key=lambda x,algorithm: x) ....: def mod_ring(x, algorithm="default"): ....: return IntegerModRing(x) sage: mod_ring(1,algorithm="default") is mod_ring(1,algorithm="algorithm") is mod_ring(1) is mod_ring(1,'default') True