#11115: Rewrite cached_method in Cython
---------------------------+------------------------------------------------
Reporter: SimonKing | Owner: jason
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-4.7
Component: misc | Keywords: category cython cache
Work_issues: | Upstream: N/A
Reviewer: | Author: Simon King
Merged: | Dependencies:
---------------------------+------------------------------------------------
Changes (by SimonKing):
* status: needs_review => needs_work
Comment:
My tests seem to indicate that (at least on my CPU) `__cached_methods` for
parents does not hurt, but `__cached_methods` for elements can yield a
slow-down. Changes in the `__getattr__` methods of parents or elements did
not yield a significant slow-down.
So, I think it is a good idea to have `__cached_methods` for parents. It
makes me wonder whether such attribute could serve an additional purpose:
If the method resolution order does not find an attribute of a parent then
it is searched in the category, by `getattr_from_other_class`. That takes
a lot of time. So, shouldn't there be a shortpath so that looking up the
same attribute becomes faster the second time?
That's to say: If a parent `P` inherits any attribute `foo` from the
category then I suggest that `P.foo` should be stored in
`P.__cached_methods["foo"]`. `__getattr__` needs to search
`P.__cached_methods` anyway, and a lookup in a dictionary should be faster
than calling `getattr_from_other_class`.
Concerning elements, it meanwhile seems better to not have
`__cached_methods` by default. But it should be possible that it is
provided by the user, so that cached methods inherited from the category
can be stored there. The `__getattr__` of elements will test whether there
is `__cached_methods` and search there.
So far, my tests indicate that the above approach is fine, speed-wise and
memory-wise. My test is:
{{{
a = get_memory_usage()
K = GF(2)
%time L = [K(i) for i in xrange(10^7)]
get_memory_usage() - a
a = get_memory_usage()
K = GF(101)
%time L = [K(i) for i in xrange(10^7)]
get_memory_usage() - a
a = get_memory_usage()
K = GF(next_prime(10^6))
%time L = [K(i) for i in xrange(10^7)]
get_memory_usage() - a
}}}
So, it is formed by three scenarios. I first give the user CPU time and
the memory consumption for sage-4.7.alpha5 plus the patches from #9976:
{{{
25.28 s, 78.49609375
25.11 s, 0.0 # so, GF(101) needs the same amount of memory than for GF(2)
88.20 s, 794.9375
}}}
Here are the same data for the current patches (i.e., with
`__cached_methods` for both parents and elements):
{{{
25.73 s, 78.49609375
25.11 s, 0.0
92.89 s, 864.21484375
}}}
And here are the same data for a (not yet posted) patch that implements
the ideas sketched above:
{{{
25.33 s, 78.49609375
24.49 s, 0.0
87.13 s, 794.93359375
}}}
I'll first catch some sleep, then I will add documentation about the use
of `__cached_methods`, and of course I also need to run doctests.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11115#comment:37>
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.
