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]

Description changed:

--- 
+++ 
@@ -23,3 +23,7 @@
 
 So, the method is inherited, but not cached.
 
+Also, cached_method could be a lot faster.
+
+Depends on #9976
+

[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

[simon-king-jena]

Description changed:

--- 
+++ 
@@ -1,3 +1,17 @@
+Broadening the original description of the ticket:
+
+The aim is to provide a Cython version of the cached_method decorator. There are three benefits:
+
+1)
+Speed (see timings in the comments)
+
+2)
+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:
@@ -23,7 +37,6 @@
 
 So, the method is inherited, but not cached.
 
-Also, cached_method could be a lot faster.
 
 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...