Rewrite cached_method in Cython

[simon-king-jena]

Broadening the original description of the ticket:

The aim is to provide a Cython version of the cached_method decorator. There are three benefits:

Speed (see timings in the comments)

Using cached methods in Cython code.

3. Parent and element methods of categories

Let me elaborate on the last point:

In order to make full use of the parent and element methods of a category, it should be possible to define a cached method in the category, so that any object of that category inherits it with caching.

Currently, it fails as follows:

sage: class MyCategory(Category):
....:     def super_categories(self):
....:         return [Objects()]
....:     class ParentMethods:
....:         @cached_method
....:         def f(self, x):
....:             return x^2
....:
sage: cython("""from sage.structure.parent cimport Parent
....: cdef class MyClass(Parent): pass
....: """)
sage: O = MyClass(category=MyCategory())
sage: O.f(4)
16
sage: O.f(x) is O.f(x)
False

So, the method is inherited, but not cached.

Apply:

1. attachment: 11115_flat.patch
2. attachment: trac_11115_docfix.patch

Note that, if you want to remove the patches after testing them, you need to do

rm $SAGE_ROOT/devel/sage/build/sage/misc/cachefunc.*
rm $SAGE_ROOT/devel/sage/build/*/sage/misc/cachefunc.*

Otherwise, sage -br would not work.

Depends on #9138
Depends on #11900

CC: @nthiery

Component: misc

Keywords: category cython cache

Author: Simon King

Reviewer: Nicolas M. Thiéry, Andrey Novoseltsev, Volker Braun

Merged: sage-5.0.beta0

Issue created by migration from https://trac.sagemath.org/ticket/11115

[simon-king-jena]

comment:1

The reason is as follows (compare #8611):

The cached method f has a getter method, that returns a CachedMethodCaller and tries to assign it to O as an attribute. That assignment fails. Hence, whenever f is called again, a new instance of the CachedMethodCaller is created. Note that before #8611, that was always the case (not very efficient).

Moreover, the cached method would try to cache its return values in a dictionary assigned to O - again, it fails. So, caching can not work.

My suggestion is as follows.

We want, in particular, that caching works for the base classes Element and Parent. I propose to provide them with a public cdef method __cached_methods (a dictionary), that is used by the getter method of the cached method to store the resulting CachedMethodCaller, if storing it as an attribute fails.

Concerning the cache for storing the return values of f: It can not be stored in a dict as an attribute of O. But by #8611, there is a dict O.f.cache that is used for storing anyway.

So, in a nutshell, it simply works (and I already have a patch that only remains to be documented).

I tried to extend that approach to SageObject (from which both Parent and Element inherit), but providing SageObject with cdef attributes will not work, since in some places there is a double inheritance, e.g., from SageObject and list.

[simon-king-jena]

comment:2

Replying to @simon-king-jena:

So, in a nutshell, it simply works (and I already have a patch that only remains to be documented).

... and documentation is hard, in particular for building the reference manual. See #9976.

The idea is:

• Modify doc/common/builder.py so that it uses the utilities from sage.misc.sageinspect rather than the utilities from the inspect module, and modify the utilities from sage.misc.sageinspect so that they work on classes and methods (currently, they only work on class instances). That's Decorated functions/methods have generic signature in documentation #9976.
• Use Cython for cached functions and methods -- it relies on Decorated functions/methods have generic signature in documentation #9976, since otherwise the doc won't build correctly.

I guess I will be able to submit patches to both tickets tomorrow.

[simon-king-jena]

Author: Simon King

[simon-king-jena]

comment:3

It took a bit longer than I originally expected, but I think it was worth it.

New Features

• An instance of a class deriving from Parent or Element can inherit a cached_method from its category, without breaking the cache, even if it does not allow attribute assignment.

• The cached_method decorator can, to some extent, be used in Cython code.

• Cached_method is a lot faster now. In fact, using the cached_method decorator on a Python class is faster than a hand-written cache for a Python method, provided that the arguments are given by name and not by position.

Examples

Python

The following code defines a category, and a Parent class that has a method with a hand-written cache and a corresponding cached method inherited from the category:

from sage.all import cached_method, Category, Objects, Parent

class MyCategory(Category):
    def super_categories(self):
        return [Objects()]
    class ParentMethods:
        @cached_method
        def cached_by_category(self, x=100, y=-1):
            return x*y

class MyPythonClass(Parent):
    def __init__(self):
        self._cache = {}
        Parent.__init__(self, category=MyCategory())
    def cached_by_python(self, x=100, y=-1):
        try:
            return self._cache[x,y]
        except KeyError:
            out = self._cache[x,y] = x*y
        return out

We do some sanity tests, and then show that the cached method is faster than the hand-written cache, unless we provide arguments by name:

sage: O = MyPythonClass()
sage: O.cached_by_category() is O.cached_by_category(100) is O.cached_by_category(x=100) is O.cached_by_category(100,-1)
True
sage: O.cached_by_python(y=1) == O.cached_by_category(y=1)
True
sage: O.cached_by_python() == O.cached_by_category()
True
sage: O.cached_by_python() is O.cached_by_python(100) is O.cached_by_python(x=100) is O.cached_by_python(100,-1)
True

Here are timings for the hand-knitted cache:

sage: timeit("O.cached_by_python()", number=10^6)
1000000 loops, best of 3: 630 ns per loop
sage: timeit("O.cached_by_python(100)", number=10^6)
1000000 loops, best of 3: 970 ns per loop
sage: timeit("O.cached_by_python(y=-1)", number=10^6)
1000000 loops, best of 3: 1.1 µs per loop
sage: timeit("O.cached_by_python(100,-1)", number=10^6)
1000000 loops, best of 3: 1.31 µs per loop

and here are the corresponding timings for the cached method inherited from the category:

sage: timeit("O.cached_by_category()", number=10^6)
1000000 loops, best of 3: 314 ns per loop
sage: timeit("O.cached_by_category(100)", number=10^6)
1000000 loops, best of 3: 954 ns per loop
sage: timeit("O.cached_by_category(y=-1)", number=10^6)
1000000 loops, best of 3: 1.93 µs per loop
sage: timeit("O.cached_by_category(100,-1)", number=10^6)
1000000 loops, best of 3: 1.06 µs per loop

Cython

You can not use arbitrary decorators in Cython. But it is now possible to wrap a Cython function by the cached_method and assign it as a method - one needs to explicitly provide its name, though. In addition, we provide a hand-written cache programmed in Cython.

from sage.structure.parent cimport Parent
from sage.all import cached_method

cpdef test_func(self,x=100, y=-1):
    return x*y

cdef class MyCythonClass(Parent):
    cdef dict _cache
    def __init__(self, category):
        self._cache={}
        Parent.__init__(self,category=category)
    cached_by_decorator = cached_method(test_func, name="cached_by_decorator")
    cpdef cached_by_cython(self,x=100,y=-1):
        try:
            return self._cache[x,y]
        except KeyError:
            out = self._cache[x,y] = x*y
        return out

It is a Parent class, and thus it can inherit parent methods from a category. Without the patch, the cache of an inherited cached_method would break, but now it is fine:

sage: C = MyCythonClass(MyCategory())
sage: C.cached_by_category(y=-1) is C.cached_by_category(100,-1)
True
sage: C.cached_by_decorator(y=-1) is C.cached_by_decorator(100,-1)
True
sage: C.cached_by_decorator(y=-1) == C.cached_by_category(100,-1)
True

The trick is that I introduced an attribute __cached_methods for Parent and Element, in which a cached method can be stored. The cache is (since #8611) stored as an attribute of the bound cached method.

While it is nice that cached_method works at all in Cython, the performance is not as good as I wish. Here are the times for the hand-knitted cache written in Cython:

sage: timeit("C.cached_by_cython()", number=10^6)
1000000 loops, best of 3: 242 ns per loop
sage: timeit("C.cached_by_cython(100)", number=10^6)
1000000 loops, best of 3: 538 ns per loop
sage: timeit("C.cached_by_cython(y=-1)", number=10^6)
1000000 loops, best of 3: 750 ns per loop
sage: timeit("C.cached_by_cython(100,-1)", number=10^6)
1000000 loops, best of 3: 882 ns per loop

Here for the cached_method inherited from the category:

sage: timeit("C.cached_by_category()", number=10^6)
1000000 loops, best of 3: 754 ns per loop
sage: timeit("C.cached_by_category(100)", number=10^6)
1000000 loops, best of 3: 1.62 µs per loop
sage: timeit("C.cached_by_category(y=-1)", number=10^6)
1000000 loops, best of 3: 2.77 µs per loop
sage: timeit("C.cached_by_category(100,-1)", number=10^6)
1000000 loops, best of 3: 1.76 µs per loop

And here using the decorator in Cython code:

sage: timeit("C.cached_by_decorator()", number=10^6)
1000000 loops, best of 3: 421 ns per loop
sage: timeit("C.cached_by_decorator(100)", number=10^6)
1000000 loops, best of 3: 1.02 µs per loop
sage: timeit("C.cached_by_decorator(y=-1)", number=10^6)
1000000 loops, best of 3: 1.96 µs per loop
sage: timeit("C.cached_by_decorator(100,-1)", number=10^6)
1000000 loops, best of 3: 1.07 µs per loop

Conclusion

The patch provides a considerable speed-up in a case where cached_method used before, so that cached_method is not only convenient but efficient. Also, it enables to use cached_method in a broader context; here, it is not particularly efficient, but it is convenient.

We want that decorated (in particular, cached) methods appear nicely in introspection and in the reference manual. Therefore, I like to have:

Depends on #9976

[novoselt]

comment:5

Replying to @simon-king-jena:

I tried to extend that approach to SageObject (from which both Parent and Element inherit), but providing SageObject with cdef attributes will not work, since in some places there is a double inheritance, e.g., from SageObject and list.

What exactly is the problem with double inheritance? It would be nice if all SageObjects had a fast uniform cache...

[simon-king-jena]

comment:6

Replying to @novoselt:

...
What exactly is the problem with double inheritance? It would be nice if all SageObjects had a fast uniform cache...

The problem is that you can not have double inheritance from extension classes if Python does not know whether the underlying data structures are compatible. So, if you have

cdef class SageObject:
    pass

(which is currently the case) then it is fine, such as here:

sage: cython('cdef class MySimpleObject: pass')
sage: class C(list,MySimpleObject): pass
....: 

But you get an error if you want to put more structure in it

sage: cython('''cdef class MyObject:
....:     cdef dict __cached_methods
....: ''')
sage: class C(list,MyObject): pass
....: 
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)

/mnt/local/king/SAGE/broken/devel/sage-main/<ipython console> in <module>()

TypeError: Error when calling the metaclass bases
    multiple bases have instance lay-out conflict

[simon-king-jena]

comment:7

Here is another data point:

sage: class MyClass:
....:     def __init__(self, v):
....:         self.__v = v
....:     def v(self):
....:         return self.__v
....:     @cached_method
....:     def cached_v(self):
....:         return self.__v
....:     def derived_from_underscore(self):
....:         x = self.__v^2
....:     def derived_from_cache(self):
....:         x = self.cached_v()^2
....:     
sage: O = MyClass(100)
sage: O.v()
100
sage: O.cached_v()
100
sage: timeit('O.v()')
625 loops, best of 3: 599 ns per loop
sage: timeit('O.cached_v()')
625 loops, best of 3: 425 ns per loop

There are methods that are frequently called and just return a double-underscore attribute. It would be faster to achieve the same with a cached method! I guess this is because of the name mangling that takes place for double-underscore attributes.

However, that only holds when calling a method. Inside of a method, the double-underscore seems to be quicker:

sage: timeit('O.derived_from_underscore()')
625 loops, best of 3: 1.65 µs per loop
sage: timeit('O.derived_from_cache()')
625 loops, best of 3: 1.98 µs per loop

I think it would be worth trying to use this trick: Little methods returning a double-underscore attribute appear all over the place. See #9138 for one example.

[simon-king-jena]

comment:8

There is one problem: The startup time increases.

I suspect this is because I extended the __getattr__ methods of parents and elements, so that it became slower -- slightly, I thought, but apparently noticeable. The original reason for doing so was an attempt to make a cached method available by attribute access, rather than by means of the __get__ methods of the CachedMethod class. I have to think of something better.

[simon-king-jena]

comment:9

I did some tests. I reverted the __getattr__ methods, so that the only change was that CachedMethod was not a Python but a Cython class. But I still saw an increased startup time.

That is strange. Is it the case that loading a Cython class takes longer than loading a Python class.

[simon-king-jena]

comment:10

One more idea: Currently, a cached method will modify its own __doc__ attribute, and some care is taken that it gets the correct one. Is it really needed to store the documentation? After all, it can easily be retrieved from the wrapped function or method!

Certainly it does not happen very frequently that the documentation of a method (cached or not) is requested: It is when the documentation is built, and it is when the user wants to learn something.

So, computing and storing the documentation during initialisation of a cached method may be a waste of time and also a waste of memory. Instead, I suggest that the documentation is only computed in the method self._sage_doc_(). I am now testing if that helps, startuptimewise.

[simon-king-jena]

comment:11

I think the problem with the startup time is solved. Indeed, it turned out that the time was wasted by creating doc strings for cached methods.

Next, I'll do some more tests. If it can be confirmed that a Python method returning a double-underscore attribute is slower than a cached_method that does the same, then I will try to speed Sage up in general, by using cached methods extensively. I wonder what will come out...

Still:

Depends on #9976

[simon-king-jena]

comment:12

In order to be on the safe side, I made some timings for the patches from #9138 (on top of #9944), and I'd like to repeat these timings here, with this patch applied additionally.

$ ./sage -startuptime
...
== Slowest (including children) ==
1.244 sage.all (None)
0.280 sage.schemes.all (sage.all)
0.243 sage.misc.all (sage.all)
0.162 elliptic_curves.all (sage.schemes.all)
...

So, there is no slow-down, compared with the timings from an unpatched Sage on the same machine, as reported on #9138.

Here is an arithmetical example:

sage: B.<t> = PolynomialRing(Integers(125))
sage: R = monsky_washnitzer.SpecialCubicQuotientRing(t^3 - t + B(1/4))
sage: x, T = R.gens()
sage: timeit('x*T')
625 loops, best of 3: 893 µs per loop

That is about the same as with the patches from #9944 and #9138, but slower than with an unpatched Sage.

I found that one can use the improved cached_methods to considerably speed up the arithmetics. Namely, in the multiplication, the method modulus() from sage.rings.polynomial.polynomial_ring is called repeatedly. The modulus() method returns ´self.basering().characteristic()`. When I put that method under a cached_method decorator, the timing looks much better:

sage: B.<t> = PolynomialRing(Integers(125))
sage: R = monsky_washnitzer.SpecialCubicQuotientRing(t^3 - t + B(1/4))
sage: x, T = R.gens()
sage: timeit('x*T')
625 loops, best of 3: 253 µs per loop

That is much faster than without patches, which is 501 µs!!.

Currently, I try to find some places where using a cached_method might be beneficial. As I have demonstrated in previous posts, there are chances to speed methods up that do nothing more but "return self.__some_argument".

But independent of that possible second patch, I think the first patch can be reviewed.

[simon-king-jena]

comment:13

I improved the performance of accessing the cache even further.

It is quite common to have methods that do not take arguments but whose return value should be cached. Typical example is the set of generators of a multivariate polynomial ring. Since sage-4.7.alpha5, it is a cached method.

Obviously, if a method takes no arguments, then caching the single value is much easier than storing the results in a dictionary for different arguments. I implemented this special case in a class CachedMethodCallerNoArgs. It is automatically used if @cached_method is a applied to a method without arguments. In particular, one does not need to do changes in the code.

Here is the performance. Bot I.groebner_basis and I.gens are cached methods (you need to take sage-4.7.alpha5 for the example):

sage: P.<a,b,c,d> = QQ[]
sage: I = P*[a,b]
sage: I.gens()
[a, b]
sage: I.groebner_basis()
[a, b]
sage: type(I.gens)
<type 'sage.misc.cachefunc.CachedMethodCallerNoArgs'>
sage: type(I.groebner_basis)
<type 'sage.misc.cachefunc.CachedMethodCaller'>
sage: timeit('I.gens()',number=10^6)
1000000 loops, best of 3: 170 ns per loop
sage: timeit('I.groebner_basis()',number=10^6)
1000000 loops, best of 3: 250 ns per loop

That is much faster than with an unpatched sage-4.7.alpha5:

sage: P.<a,b,c,d> = QQ[]
sage: I = P*[a,b]
sage: I.groebner_basis()
[a, b]
sage: I.gens()
[a, b]
sage: timeit('I.gens()',number=10^6)
1000000 loops, best of 3: 699 ns per loop
sage: timeit('I.groebner_basis()',number=10^6)
1000000 loops, best of 3: 746 ns per loop

To give you an idea of how fast 170 ns or 250 ns are:

sage: class MyClass:
....:     def __init__(self):
....:         self._v = 10
....:         self.__v = 10
....:     def m0(self):
....:         return 10
....:     def m1(self):
....:         return self._v
....:     def m2(self):
....:         return self.__v
....:     
sage: O = MyClass()
sage: timeit('O.m0()')
625 loops, best of 3: 1.01 µs per loop
sage: timeit('O.m1()')
625 loops, best of 3: 622 ns per loop
sage: timeit('O.m2()')
625 loops, best of 3: 621 ns per loop

Note that the cache is pickled -- see examples in the doc strings.

There is one further extension. There is a class sage.misc.cachefunc.ClearCacheOnPickle, whose purpose is quite nice: If you have a class that inherits from clearCacheOnPickle then the cached values will not be pickled.

That is to say: Let X be an instance of ClearCacheOnPickle and assume that its pickling is implemented using the __get_newargs__ and __get_state__ mantra. Then, the cache of any cached method of loads(dumps(X)) will be empty (but of course the cache of X is preserved).

The idea existed, but it did not work for me. So, I re-implemented it essentially from scratch, using the original ideas. Also, I provided doc tests for ClearCacheOnPickle; there had been none before.

On top of sage-4.7.alpha5, I have the patches from #10296, #9944, #9138 and #9976, and then all doc tests pass with the patch from here. But there should only be one dependency, namely of #9976, which provides introspection to interactive Cython code.

Depends on #9976

[simon-king-jena]

comment:14

I just updated the patch, because I noticed the following: If you have an old pickle of an object with a cached method then of course the pickle will contain the cached value. If you unpickle then it may be that an old CachedMethodCaller becomes a new CachedMethodCallerNoArgs.

It would thus be nice if CachedMethodCallerNoArgs could retrieve the cache value of an old pickled CachedMethodCaller. This is implemented in the new patch.

What I did to test it:

1. Without the patch applied, do

sage: P.<a,b,c,d> = QQ[]
sage: I = P*[a,b]
sage: I.gens()  # this is in order to fill the cache - it is a CachedMethodCaller
sage: save(I,'pickletest')

2. With the patch applied, do

sage: I = load('pickletest')
sage: I.gens.cache   # this is now a CachedMethodCallerNoArgs
[a, b]

So, the cache is already filled after unpickling.

[simon-king-jena]

comment:15

While trying to fix doc tests, I noticed that there are too many non-initialised rings left that are not covered by the patch from #9138. I think it is more clean to fix it there, not here. Since #9138 needs work, this needs work as well.

[simon-king-jena]

Work Issues: Wait for #9138

[jdemeyer]

comment:179

Could you please explain this line in src/sage/misc/cachefunc.pxd?

# cache is not always of type "dict"!

It seems that the implementation assumes that cache is a dict anyway (I see lots of <dict>self.cache in the code).

[simon-king-jena]

comment:180

Replying to @jdemeyer:

Could you please explain this line in src/sage/misc/cachefunc.pxd?

# cache is not always of type "dict"!

That's why:

sage: from weakref import WeakValueDictionary
sage: W = WeakValueDictionary()
sage: isinstance(W, dict)
False

We use weak value dictionaries for weak_cached_function.

It seems that the implementation assumes that cache is a dict anyway (I see lots of <dict>self.cache in the code).

But certainly not in weak_cached_function.

[jdemeyer]

comment:181

Replying to @simon-king-jena:

It seems that the implementation assumes that cache is a dict anyway (I see lots of <dict>self.cache in the code).

But certainly not in weak_cached_function.

I think that's a bad design with all the <dict> casts. I would have prefered something more like:

class BaseCachedFunction(object):
    pass

class CachedFunction(BaseCachedFunction):
    cdef dict cache

class WeakCachedFunction(BaseCachedFunction):
    cdef WeakValueDictionary cache

This is like the classes for dense/sparse vectors.

[simon-king-jena]

comment:182

As it seems, there will be a new ticket on cached methods soon, because of the sad fact that removing a cython source file from the Sage library does not only result in problems with introspection of cached methods, but the cached methods can't even be called. So, I suppose the design flaw can be addressed there, too.

[jdemeyer]

comment:183

Replying to @simon-king-jena:

As it seems, there will be a new ticket on cached methods soon, because of the sad fact that removing a cython source file from the Sage library does not only result in problems with introspection of cached methods, but the cached methods can't even be called. So, I suppose the design flaw can be addressed there, too.

Unless #17814 really requires major refactoring anyway, I wouldn't do it on the same ticket.

Also, I certainly don't want to force you to "fix" this. It works as it is.

[simon-king-jena]

comment:184

Replying to @jdemeyer:

Unless #17814 really requires major refactoring anyway, I wouldn't do it on the same ticket.

Actually, it currently seems that this would better be addressed by changing sage.misc.sageinspect.

[simon-king-jena]

comment:185

Hm. Fixing sageinspect won't be easy. I currently have absolutely no clue how to read off the number of arguments (or even the names of the arguments) of a function that is defined in a Cython file. Those functions don't seem to have any attributes holding useful information.

Has someone else an idea? If not, then I don't see what we can do. We do want a special cached method implementation for methods without arguments, and thus we need to determine the number of arguments of the to-be-wrapped method. If that doesn't work without reading the sources, what could we possibly do?

[jdemeyer]

comment:186

What's the purpose of this opaque block of code?

            if args:
                lenargs = len(args)
                nargs = self._argument_fixer._nargs
                if self._inst_in_key:
                    if lenargs>=nargs:
                        k = (self._instance,(args,()))
                    else:
                        k = (self._instance,(<tuple>args+(<tuple>self._argument_fixer._default_tuple)[-nargs+lenargs:],()))
                else:
                    if lenargs>=nargs:
                        k = (args,())
                    else:
                        k = (<tuple>args+(<tuple>self._argument_fixer._default_tuple)[-nargs+lenargs:],())