#4731: Repeated computation involving Maxima is getting slower and slower
-------------------------+--------------------------------------------------
Reporter: SimonKing | Owner: mabshoff
Type: defect | Status: new
Priority: major | Milestone: sage-4.1.2
Component: performance | Keywords: maxima timing repeated computation
Reviewer: | Author:
Merged: |
-------------------------+--------------------------------------------------
Description changed by was:
Old description:
> It may happen that a computation does not always take the same time when
> it is done the first or the tenth time, if Maxima is involved. The
> example below is short and rather drastic. However, much worse happened
> to me in some application, when the time dropped by a much bigger factor.
>
> The strange time-under-repetition behaviour can be triggered by the
> following short code:
> {{{
> sage: class Foo:
> ....: def __init__(self,n,L):
> ....: self.n = n
> ....: self.l = int(log(n,10))+1
> ....: self.L = [X%n for X in L]
> ....: def __str__(self):
> ....: return "["+" ".join([str(X).rjust(self.l) for X in
> self.L])+"]"
> ....: def __copy__(self):
> ....: OUT = Foo(self.n,copy(self.L))
> ....: return OUT
> ....: def __mul__(self,r):
> ....: OUT = self.__copy__()
> ....: OUT.L = [(X*r)%OUT.n for X in OUT.L]
> ....: return OUT
> ....:
> sage: M=Foo(97,[1,13,100,23098])
> sage: timeit('N=M*13')
> 25 loops, best of 3: 9.66 ms per loop
> sage: timeit('N=M*13')
> 25 loops, best of 3: 13.3 ms per loop
> sage: timeit('N=M*13')
> 25 loops, best of 3: 14.3 ms per loop
> sage: timeit('N=M*13')
> 25 loops, best of 3: 12.2 ms per loop
> sage: timeit('N=M*13')
> 25 loops, best of 3: 17.3 ms per loop
> sage: timeit('N=M*13')
> 25 loops, best of 3: 16 ms per loop
> sage: timeit('N=M*13')
> 25 loops, best of 3: 17.8 ms per loop
> sage: timeit('N=M*13')
> 25 loops, best of 3: 19.3 ms per loop
> sage: timeit('N=M*13')
> 25 loops, best of 3: 20.7 ms per loop
> }}}
>
> So, on average, the computation becomes slower and slower.
>
> This strange behaviour is due to the line `self.l = int(log(n,10))+1`.
> Replacing it by a different (though equivalent) line, we get:
> {{{
> sage: class Foo:
> ....: def __init__(self,n,L):
> ....: self.n = n
> ....: self.l = len(str(n))
> ....: self.L = [X%n for X in L]
> ....: def __str__(self):
> ....: return "["+" ".join([str(X).rjust(self.l) for X in
> self.L])+"]"
> ....: def __copy__(self):
> ....: OUT = Foo(self.n,copy(self.L))
> ....: return OUT
> ....: def __mul__(self,r):
> ....: OUT = self.__copy__()
> ....: OUT.L = [(X*r)%OUT.n for X in OUT.L]
> ....: return OUT
> ....:
> sage: M=Foo(97,[1,13,100,23098])
> sage: timeit('N=M*13')
> 625 loops, best of 3: 19.2 µs per loop
> sage: timeit('N=M*13')
> 625 loops, best of 3: 19.2 µs per loop
> sage: timeit('N=M*13')
> 625 loops, best of 3: 19.2 µs per loop
> sage: timeit('N=M*13')
> 625 loops, best of 3: 19.3 µs per loop
> sage: timeit('N=M*13')
> 625 loops, best of 3: 19.3 µs per loop
> sage: timeit('N=M*13')
> 625 loops, best of 3: 19.3 µs per loop
> }}}
>
> It is not the point that now it is faster. The point is that now the
> computation time is constant under repetition.
>
> Sorry, I am not sure what "Component" I shall assign. Hopefully calculus
> is ok?
New description:
It may happen that a computation does not always take the same time when
it is done the first or the tenth time, if Maxima is involved. The example
below is short and rather drastic. However, much worse happened to me in
some application, when the time dropped by a much bigger factor.
The strange time-under-repetition behaviour can be triggered by the
following short code:
{{{
class Foo:
def __init__(self,n,L):
self.n = n
self.l = int(log(n,10))+1
self.L = [X%n for X in L]
def __str__(self):
return "["+" ".join([str(X).rjust(self.l) for X in self.L])+"]"
def __copy__(self):
OUT = Foo(self.n,copy(self.L))
return OUT
def __mul__(self,r):
OUT = self.__copy__()
OUT.L = [(X*r)%OUT.n for X in OUT.L]
return OUT
}}}
Then
{{{
sage: M=Foo(97,[1,13,100,23098])
sage: timeit('N=M*13')
25 loops, best of 3: 9.66 ms per loop
sage: timeit('N=M*13')
25 loops, best of 3: 13.3 ms per loop
sage: timeit('N=M*13')
25 loops, best of 3: 14.3 ms per loop
sage: timeit('N=M*13')
25 loops, best of 3: 12.2 ms per loop
sage: timeit('N=M*13')
25 loops, best of 3: 17.3 ms per loop
sage: timeit('N=M*13')
25 loops, best of 3: 16 ms per loop
sage: timeit('N=M*13')
25 loops, best of 3: 17.8 ms per loop
sage: timeit('N=M*13')
25 loops, best of 3: 19.3 ms per loop
sage: timeit('N=M*13')
25 loops, best of 3: 20.7 ms per loop
}}}
So, on average, the computation becomes slower and slower.
This strange behaviour is due to the line `self.l = int(log(n,10))+1`.
Replacing it by a different (though equivalent) line, we get:
{{{
sage: class Foo:
....: def __init__(self,n,L):
....: self.n = n
....: self.l = len(str(n))
....: self.L = [X%n for X in L]
....: def __str__(self):
....: return "["+" ".join([str(X).rjust(self.l) for X in
self.L])+"]"
....: def __copy__(self):
....: OUT = Foo(self.n,copy(self.L))
....: return OUT
....: def __mul__(self,r):
....: OUT = self.__copy__()
....: OUT.L = [(X*r)%OUT.n for X in OUT.L]
....: return OUT
....:
sage: M=Foo(97,[1,13,100,23098])
sage: timeit('N=M*13')
625 loops, best of 3: 19.2 µs per loop
sage: timeit('N=M*13')
625 loops, best of 3: 19.2 µs per loop
sage: timeit('N=M*13')
625 loops, best of 3: 19.2 µs per loop
sage: timeit('N=M*13')
625 loops, best of 3: 19.3 µs per loop
sage: timeit('N=M*13')
625 loops, best of 3: 19.3 µs per loop
sage: timeit('N=M*13')
625 loops, best of 3: 19.3 µs per loop
}}}
It is not the point that now it is faster. The point is that now the
computation time is constant under repetition.
Sorry, I am not sure what "Component" I shall assign. Hopefully calculus
is ok?
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/4731#comment:5>
Sage <http://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
-~----------~----~----~----~------~----~------~--~---
