On Tue, May 31, 2011 at 1:23 AM, Robert Bradshaw
<[email protected]> wrote:
> On Tue, May 31, 2011 at 12:23 AM, Simon King <[email protected]> wrote:
>> Hi Robert,
>>
>> Thank you for resuming this thread.
>>
>> On 31 Mai, 08:13, Robert Bradshaw <[email protected]>
>> 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.
Or perhaps you're referring to the total startup memory? We create
lots of Parents at startup, but (relatively) few elements (compared to
typical use).
In any case, I like the current solution best.
> 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 [email protected]
To unsubscribe from this group, send an email to
[email protected]
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
