Changes between Initial Version and Version 3 of Ticket #11115


Ignore:
Timestamp:
04/10/11 01:44:26 (3 years ago)
Author:
SimonKing
Comment:

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

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #11115

    • Property Status changed from new to needs_review
    • Property Authors changed from to Simon King
  • Ticket #11115 – Description

    initial v3  
    2222 
    2323So, the method is inherited, but not cached. 
     24 
     25Also, cached_method could be a lot faster. 
     26 
     27Depends on #9976