#11115: Allow for extension classes to inherit cached methods from their
category
---------------------------+------------------------------------------------
Reporter: SimonKing | Owner: jason
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.7
Component: misc | Keywords: category cython cache
Author: Simon King | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
---------------------------+------------------------------------------------
Changes (by newvalueoldvalue):
* status: new => needs_review
* author: => Simon King
Old description:
> 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.
New description:
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.
Also, cached_method could be a lot faster.
Depends on #9976
--
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
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11115#comment:3>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
