On Tue, May 31, 2011 at 12:23 AM, Simon King <simon.k...@uni-jena.de> wrote:
> Hi Robert,
>
> Thank you for resuming this thread.
>
> On 31 Mai, 08:13, Robert Bradshaw <rober...@math.washington.edu>
> wrote:
>> > So, the additional memory usage seems affordable to me.
>>
>> Elements of small finite fields are cached, so this test doesn't
>> really show anything.
>>
>> sage: GF(2)(1) is GF(2)(-1)
>> True
>
> I see.
>
> I am trying to sum up what the few participants of the discussion
> agreed upon.
>
> * By default, a cached method or a lazy attribute tries to use
> attribute assignment in order to make itself work. That's probably the
> fastest what one can do, and it is how things already worked before
> #11115.
>
> * If attribute assignment fails (that may happen for extension
> classes) then it is tried to store stuff in an attribute
> __cached_methods. That's new in #11115.
>
> * The __cached_methods attribute is added to parents. The rationale is
> that (1) cached methods seem to be most frequently used for parents
> (not for elements), (2) parents are big anyway, so that an additional
> attribute should not count so much. Note that the stuff stored in
> __cached_method would otherwise be stored via attribute assignment,
> and the new attribute will be None if attribute assignment is possible
> -- hence, there should be no memory problem.
>
> * In contrast to what I had originally planned, the patches from
> #11115 do *not* add __cached_methods to
> sage.structure.element.Element. That means: One can still use cached
> methods and lazy attributes on elements that accept attribute
> assignment; but on other elements, cached methods and lazy attributes
> are not supported.
>
> * If one wants cached methods on an element class that for some reason
> can not accept general attribute assignment, #11115 adds a new
> subclass of Element, called ElementWithCachedMethod. It provides the
> __cached_methods attribute.
>
> By consequence, both cached methods and lazy attributes work for *all*
> parents and *most* elements, and there is the big speed up for cached
> methods. Just to avoid misunderstanding: The speed-up is not related
> with the existence of __cached_methods.
>
>> > But I guess I
>> > should try to find out why the element creation became slower for
>> > GF(2), while it became faster for GF(101), and again slower for
>> > GF(next_prime(10^6)) (see example on the ticket).
>>
>> Noise?
>
> Perhaps.
>
>> I think the increased memory usage is a bigger issue than performance
>> (it can impact the latter, but in hard-to-measure ways).
>
> I did not notice a big increase in memory consumption.
This is because you were testing with finite fields that create all
their elements ahead of time and re-use them.
sage: M = matrix(InfinitePolynomialRing(QQ), 100, 100, range(10000))
sage: get_memory_usage()
228.75
sage: max(a.max_index() for a in M.list()) # a cached method
-1
sage: get_memory_usage()
265.00390625
> But perhaps you
> can find a test case where this would be a problem?
I can't think of one off the top of my head, but this is a problem in
general (as explained so well by nbruin in on the ticket).
>> In fact, some objects (e.g. matrices) already have a "cache" dict,
>> this could be done at a higher level.
>
> Yep, I guess the purpose of __cached_methods is similar. Originally, I
> only intended to use it for cached methods, but then I also used it to
> make inherited lazy attributes (such as element_class) work on
> extension classes.
>
>> Creating a new element means existing class hierarchies will have to
>> be changed (e.g. RingElement) to take advantage of this, but that may
>> be what's required.
>
> By "new element" you mean a new class such as ElementWithCachedMethod?
> The patches from #11115 do not change the class hierarchy for things
> like RingElement -- they offer ElementWithCachedMethod, but it is
> currently not more than an offer.
>
>> Also, blindly marking all self-only methods as cached is a huge change
>> in the time-memory performance tradeoff.
>
> Yep. Meanwhile I found that it makes more sense to add the
> @cached_method decorator only to carefully chosen small frequently
> used methods, such as modulus() of finite fields, and in some cases
> caching gen() has a positive effect.
+1 to thoughtful use. It's a wonderful decorator. (Actually, I wanted
it at work for something just yesterday, but I was using Java :(.
>> Some things may be
>> better to re-compute rather than store (especially if they're biggish
>> and cheap).
>
> In what sense do you mean "better"?
That depends on how much time you have vs. how much memory you have.
As another example, it'd be a waste to cache parent() or the degree of
a univariate polynomial.
> TIME-WISE, a cached method post-#11115 even beats a method that does
> no computation at all:
>
> sage: class MyClass:
> ....: def __init__(self,m):
> ....: self.__modulus = m
> ....: def modulus(self):
> ....: return self.__modulus
> ....: @cached_method
> ....: def c_modulus(self):
> ....: return self.__modulus
> ....: def one(self):
> ....: return 1
> ....: @cached_method
> ....: def c_one(self):
> ....: return 1
> ....:
> sage: O = MyClass(5)
> sage: timeit('O.modulus()', number=10^7)
> 10000000 loops, best of 3: 247 ns per loop
> sage: timeit('O.c_modulus()', number=10^7)
> 10000000 loops, best of 3: 106 ns per loop
> sage: timeit('O.one()', number=10^7)
> 10000000 loops, best of 3: 419 ns per loop
> sage: timeit('O.c_one()', number=10^7)
> 10000000 loops, best of 3: 106 ns per loop
That's because MyClass is implemented in Python, and cached_method in
Cython :).
> Or do you mean "better memory-wise"? That may be true, if the result
> of a method is big and not often used.
Yes.
> However, there frequently are methods that look like
> def bla(self):
> try:
> return self.__bla
> except AttributeError:
> do some lengthy computation
> self.__bla = result
> return result
>
> Those should be replaced by
> @cached_method
> def bla(self):
> do some lengthy computation
> return result
>
> That's both shorter and faster.
I agree completely, I was more referring to marking all methods by default.
>> If your'e setting up a generic infrastructure, perhaps the
>> default could be enabled/disabled with a flag (and with statement
>> context).
>
> I don't understand that. Can you give me an example?
You'd have a "maybe_cache" decorator that would decide to cache based
on a global flag. Then you'd do
with aggressive_caching():
[some calculation that uses maybe_cache decorated methods
[here, all caches are cleared and memory reclaimed]
Probably not worth it, and things will get garbage collected when
you're done with them.
- Robert
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
