Where should cached_method put its cache?
Simon King
IMHO, the cached_... decorators are currently too slow. It seems to me
that too much time is spent for looking up the cache (calling the
method get_cache()).
I'd like to invest some work in it, but I need some info:
The cache can be
* a dictionary self.cache of the decorated function (this is for
CachedFunction),
* a dictionary-like instance self.cache of class FileCache (this is
for DiskCachedFunction),
* a dictionary that is an attribute of the instance to which the
cached method is bound (this is for CachedMethod), or
* a dictionary that is an attribute of the parent of the instance to
which the cached method is bound (this is for CachedInParentMethod).
Sometimes, looking up the cache requires two calls (get_cache() and
_get_instance_cache()). Moreover, C extension types don't provide a
__dict__ attribute, which is a problem for CachedMethod and
CachedInParentMethod.
The cache in the case of CachedFunction and DiskCachedFunction is, of
course, easy to find: It is self.cache, where "self" is a
CachedFunction (or DiskCachedFunction) instance.
Let us now consider CachedMethod.
Let x be an instance that has a cached method (or cached in parent
method) foo. The __get__ method of CachedMethod turns x.foo into an
instance of CachedMethodCaller, that is specific to x. Now, I wonder
why the method is not cached in an attribute of the CachedMethodCaller
instance.
Or explicitly: What is the advantage of caching x.foo in x._cache__foo
rather than in x.foo.cache? The disadvantage is that the string
"_cache__foo" must be created and then x.__dict__["_cache__foo"] must
be obtained, which costs time.
Even in the case of CachedInParentMethod, there could still be an
attribute x.foo.cache, that points to an attribute of x.parent().
Hence, there would only be one cache (namely in x.parent()), while
elements of x.parent() only provide pointers to it, which is both
cheap and fast, if I am not mistaken.
Best regards,
Simon
Nicolas M. Thiery
Sorry for my late answer; I missed this e-mail in the sage-devel flow ...
On Fri, Jan 07, 2011 at 10:58:49AM -0800, Simon King wrote:
> IMHO, the cached_... decorators are currently too slow. It seems to
> me that too much time is spent for looking up the cache (calling the
> method get_cache()).
There is a consensus on that :-)
There are several reasons to cache the results in x rather than in the
method foo:
(a) You don't need to calculate the hash of x to retrieve something
from the cache; that can be important for large objects (with a
costly hash function) with methods taking small arguments as
input.
(b) The cache is automatically pickled with the object
(c) It makes it easy to clear / invalidate the cache of a particular object
(d) If the object goes of scope and is wiped from memory, then the
same occurs to its cache (a desirable feature; otherwise you would
probably be using CachedInParent).
The same apply for CachedInParent: if the parent goes out of
scope, then so does the cache. Otherwise you would probably be
using a cached function.
Note that there is also a little technical hurdle:
sage: class bla:
....: @cached_method
....: def f(): pass
sage: x = bla()
sage: x.f.cache = 1
sage: x.f.cache
------------------------------------------------------------
Traceback (most recent call last):
File "<ipython console>", line 1, in <module>
AttributeError: 'CachedMethodCaller' object has no attribute 'cache'
That's because x.f is a new object each time; the following works:
sage: xf = x.f
sage: xf.cache = 1
sage: xf.cache
1
Of course, that could be worked around by taking over the management
of assignment to x.f.cache using, e.g., a property.
A further note about (c): in fact, I would really like to have all the
cache be grouped in a single attribute x._cache, using x._cache["foo"]
or even x._cache.foo rather than x._cache_foo. Advantages:
- it's easier to clear/invalidate all the cache at once
- less pollution of the name space
- objects that need fast caching could have x._cache (or maybe even
x._cache.foo) as a Cython attribute
There is one issue that needs to be discussed as well: if we change
the location where the cache is stored in objects, then any currently
pickled object will loose its cache. Do we care? I doubt anyone in the
Sage-Combinat crowd cares at this point (we don't have large pickle
jars of objects, especially with relevant cache). But someone else could!
Cheers,
Nicolas
--
Nicolas M. Thi�ry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/
Robert Bradshaw
<Nicolas...@u-psud.fr> wrote:
> Hi Simon!
>
> Sorry for my late answer; I missed this e-mail in the sage-devel flow ...
>
> On Fri, Jan 07, 2011 at 10:58:49AM -0800, Simon King wrote:
>> IMHO, the cached_... decorators are currently too slow. It seems to
>> me that too much time is spent for looking up the cache (calling the
>> method get_cache()).
>
> There is a consensus on that :-)
Yep. It's sad when sometimes it's quicker to not cache non-trivial
computations.
+1 to all of the above, I think a cached result should be put on the
object itself itself.
That's a really nice idea.
> There is one issue that needs to be discussed as well: if we change
> the location where the cache is stored in objects, then any currently
> pickled object will loose its cache. Do we care? I doubt anyone in the
> Sage-Combinat crowd cares at this point (we don't have large pickle
> jars of objects, especially with relevant cache). But someone else could!
I think caches are, by nature, potentially ephemeral, so it's OK to
get back fully-intact objects without their caches. Of coures, someone
may be counting on the fact that they've computed this before
pickling--if so they should speak up now.
- Robert
Nicolas M. Thiery
Oh wow, I had completely missed all the activity on #8611!
This issue had been such an itch since at least one year if not
two. Congrats for getting this done, and so nicely! Thanks to the
reviewers as well. I can't wait for 4.6.2 now!
You are my hero of the day :-)
Cheers,
Nicolas
PS:
Definitely +1 on caching is_subcategory.
The comments in this thread are now for a later ticket.
Out of curiosity: does #8611 keep backward compatibility for the cache
of old pickles?
Simon King
On 28 Jan., 11:41, "Nicolas M. Thiery" <Nicolas.Thi...@u-psud.fr>
wrote:
thread are actually solved in #8611.
> Out of curiosity: does #8611 keep backward compatibility for the cache
> of old pickles?
cached_in_parent_method is similar):
If you have
class FOO:
@cached_method
def bar(self,*args,**kwds):
return something
and x = FOO() then calling x.bar() creates an argument x._cache__bar,
which is a dictionary storing the computed values of x.bar(). That's
the same with or without #8611
The news is:
* x.bar is now THE SAME instance each time you call it. I know that it
used to be different, and that was one of the reasons for it being so
slow.
* Since x.bar is permanently there, it makes sense to have x.bar.cache
as well.
"As well" means:
* If x._cache__bar was successfully created then x.bar.cache simply is
a shortpath (from the point of view of the cached method) to access
the cache -- that's another reason why #8611 provides a speed-up.
* x.bar.cache is simply a second pointer to x._cache__bar. In
particular, old pickles (which store x._cache__bar) won't break (I
just tested).
* If x._cache__bar can't be created (AttributeError), then still
x.bar.cache is there, and caching is now possible in some cases where
it would have failed.
I think that's the answer for now. But I think I will go through your
above comments and show how it is addressed by #8611.
Cheers,
Simon
Simon King
On 28 Jan., 11:02, "Nicolas M. Thiery" <Nicolas.Thi...@u-psud.fr>
wrote:
> method foo:
>
> (a) You don't need to calculate the hash of x to retrieve something
> from the cache; that can be important for large objects (with a
> costly hash function) with methods taking small arguments as
> input.
values from x.bar.cache. So, that's no problem
Example with #8611:
sage: P.<x,y> = GF(5)[]
sage: I = P*[P.gen()]
sage: I.groebner_basis is I.groebner_basis
True #NEW: That used to be False!
sage: I.groebner_basis()
[x]
sage: I._cache__groebner_basis
{(('',), ()): [x]}
sage: I._cache__groebner_basis is I.groebner_basis.cache
True
So, the result of Gröbner basis computation is stored in the same
location and using the same keys as before, namely
I._cache__groebner_basis. But in addition, there is a second pointer
I.groebner_basis.cache to it.
> (b) The cache is automatically pickled with the object
dictionary still exists.
> (c) It makes it easy to clear / invalidate the cache of a particular object
sage: J = P*[P.gen()]
sage: J.groebner_basis()
[x]
sage: J._cache__groebner_basis
{(('',), ()): [x]}
sage: I._cache__groebner_basis
{(('',), ()): [x]}
sage: I.groebner_basis.clear_cache()
sage: J._cache__groebner_basis
{(('',), ()): [x]}
sage: I._cache__groebner_basis
{}
Perhaps you misunderstood what it means when I say that the cache is
stored in the cached method: It is NOT a cache that is shared by all
instances of the cached method!
> (d) If the object goes of scope and is wiped from memory, then the
> same occurs to its cache (a desirable feature; otherwise you would
> probably be using CachedInParent).
holds for J.groebner_basis. And when J.groebner_basis vanishes, then
so does J.groebner_basis.cache
> Note that there is also a little technical hurdle:
>
> sage: class bla:
> ....: @cached_method
> ....: def f(): pass
> sage: x = bla()
> sage: x.f.cache = 1
> sage: x.f.cache
> ------------------------------------------------------------
> Traceback (most recent call last):
> File "<ipython console>", line 1, in <module>
> AttributeError: 'CachedMethodCaller' object has no attribute 'cache'
>
> That's because x.f is a new object each time;
Now, a cached method inserts itself as a usual attribute, and:
sage: I.groebner_basis is I.groebner_basis
True
sage: I.groebner_basis is J.groebner_basis
False
Of course, if you like to break things, you may do
sage: I.groebner_basis.cache[('magma',),()] = NotImplemented
sage: I.groebner_basis('magma')
NotImplemented
> A further note about (c): in fact, I would really like to have all the
> cache be grouped in a single attribute x._cache, using x._cache["foo"]
> or even x._cache.foo rather than x._cache_foo. Advantages:
>
> - it's easier to clear/invalidate all the cache at once
But, to be honest, clearing *all* caches at once rather than a single
one is a feature that I did not have in mind.
> - less pollution of the name space
By the way, it *is* in a single dictionary:
sage: I.groebner_basis.cache is I.__dict__['_cache__groebner_basis']
True
> - objects that need fast caching could have x._cache (or maybe even
> x._cache.foo) as a Cython attribute
Python class and a Python method:
Put the following in a file cachetest.pyx:
from sage.all import cached_method
class FOO:
@cached_method
def bar(self, x, y=3):
return x*y
Then do
sage: attach cachetest.pyx
Compiling ./cachetest.pyx...
AttributeError: 'builtin_function_or_method' object has no attribute
'func_defaults'
Unfortunately, that didn't change with #8611.
But of course, I'd appreciate if there could be a cached_method
implementation for Cython!
> There is one issue that needs to be discussed as well: if we change
> the location where the cache is stored in objects, then any currently
> pickled object will loose its cache. Do we care?
As I pointed out above, the location of the cache did not change, but
the accessibility of the cache was simplified. So, one can do:
WITHOUT #8611
sage: P.<x,y> = GF(5)[]
sage: I = P*[P.gen()]
sage: I.groebner_basis()
[x]
sage: save(I,'tmp')
WITH #8611 (starting a new session)
sage: J = load('tmp.sobj')
sage: J.groebner_basis.cache
{(('',), ()): [x]}
Hence, pickles do not break, the cache (stored with the old version)
is still there.
So, I think that #8611 does address most points that you raise here.
Best regards,
Simon
Simon King
On 28 Jan., 11:14, Robert Bradshaw <rober...@math.washington.edu>
wrote:
> computations.
Setting:
sage: class A:
....: @cached_method
....: def bar(self,x):
....: return x
....: @cached_in_parent_method
....: def barP(self,x):
....: return x
....: def parent(self):
....: return self
....:
sage: a = A()
WITHOUT #8611, we get:
# The non-critical path:
sage: time for x in range(10^6): b=a.bar(x)
CPU times: user 24.97 s, sys: 0.16 s, total: 25.13 s
Wall time: 25.13 s
sage: time for x in range(10^6): b=a.barP(x)
CPU times: user 41.03 s, sys: 0.13 s, total: 41.16 s
Wall time: 41.17 s
# The critical path (now the values are cached):
sage: time for x in range(10^6): b=a.bar(x)
CPU times: user 16.45 s, sys: 0.02 s, total: 16.47 s
Wall time: 16.47 s
sage: time for x in range(10^6): b=a.barP(x)
CPU times: user 20.47 s, sys: 0.02 s, total: 20.50 s
Wall time: 20.50 s
#########################
WITH #8611, we get:
# The non-critical path:
sage: time for x in range(10^6): b=a.bar(x)
CPU times: user 11.40 s, sys: 0.08 s, total: 11.48 s
Wall time: 11.48 s
sage: time for x in range(10^6): b=a.barP(x)
CPU times: user 27.89 s, sys: 0.12 s, total: 28.01 s
Wall time: 28.02 s
# The critical path (now the values are cached):
sage: time for x in range(10^6): b=a.bar(x)
CPU times: user 3.09 s, sys: 0.01 s, total: 3.10 s
Wall time: 3.10 s
sage: time for x in range(10^6): b=a.barP(x)
CPU times: user 5.25 s, sys: 0.02 s, total: 5.26 s
Wall time: 5.26 s
Hence, due to the optimisation of accessing the cache, it is now
quicker to compute the values *and* store them in the cache (the non-
critical path) than it used to be to only get the cached values that
have been computed before (the critical path).
> +1 to all of the above, I think a cached result should be put on the
> object itself itself.
object itself.
> > - objects that need fast caching could have x._cache (or maybe even
> > x._cache.foo) as a Cython attribute
>
> That's a really nice idea.
> I think caches are, by nature, potentially ephemeral, so it's OK to
> get back fully-intact objects without their caches. Of coures, someone
> may be counting on the fact that they've computed this before
> pickling--if so they should speak up now.
is not documented, and I wasn't able to make it work in an example.
But I think the idea is nice: You have one decorator for methods whose
cache should be pickled, and another one where this should not be the
case.
But now that I think about it: It should be easy on top of #8611.
Namely, I.groebner_basis.cache is pickled because I.__dict__ is
pickled and contains I._cache__groebner_basis. Hence, if one modifies
the decorator a little, it should be possible to have the cache in
x.bar.cache, but NOT in x.__dict__['_cache__bar']. In that way, the
cache would not be pickled.
Syntax suggestion:
class FOO:
@cached_method
def bar(self,...):
...
@cached_method(clear=True)
def foo_bar(self,...):
...
Then, when pickling an instance X of FOO, the cache of X.bar would be
pickled, but not the cache of X.foo_bar.
Best regards,
Simon
Simon King
> Hi Robert,
>
> On 28 Jan., 11:14, Robert Bradshaw <rober...@math.washington.edu>
> wrote:
>
> > Yep. It's sad when sometimes it's quicker to not cache non-trivial
> > computations.
>
> Indeed it was. Here is an example from the ticket:
> quicker to compute the values *and* store them in the cache (the non-
> critical path) than it used to be to only get the cached values that
> have been computed before (the critical path).
speed-up is visible.