Re: Timing of looping operators
- To: mathgroup at smc.vnet.net
- Subject: [mg62426] Re: [mg62416] Timing of looping operators
- From: Sseziwa Mukasa <mukasa at jeol.com>
- Date: Thu, 24 Nov 2005 06:33:24 -0500 (EST)
- References: <200511230931.EAA20248@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
On Nov 23, 2005, at 4:31 AM, dh wrote:
> Hello,
> The Mathematica gospel tells you that you should NOT use loops because
> it is inefficient.
> Well consider the following examples and their times:
>
> n=10^6;
> d=Table[i,{i,n}];
> fun[x_]:=x;
>
> a) Timing[fun & /@ d;] needs 0.8 sec
> b) Timing[Scan[fun, d]] needs 1 second
> c) Timing[Do[f[i], {i, n}];] needs 0.7 sec
>
> a) applies the function and creates a new list. b) does not create
> a new
> list -- but it is slower! And finally c) the loop is fastest!!!
>
> If you change the function to: f[x_]:=x^2, the times are even more
> striking:
>
> 0.8, 2.4, 0.7
> it seems like in a and c the function evaluation takes negliable time
> compared to the loop construct, but not so in b.
>
> has anybody an explanation???
I don't have an explanation but a couple of observations:
- When I execute expression a more than once it takes about the same
amount of time as expression c after the first execution, the first
execution takes longest. This behavior leads me to believe that
something large is being cached which was created the first time.
- These tests are not equivalent, b and c are relatively similar in
that they do nothing but evaluate f. Expression a creates a list
which is then be discarded, my guess is the initial time penalty is
for the time to make the storage for the result. Once this memory is
allocated it can be reused whenever an object of similar size is
needed, which may explain the cache like behavior noted in my first
point.
- If you reverse the order of the timing statements so that
expression c is evaluated before a, a actually executes faster than c
and faster than if a is executed before c. Again this leads me to
believe that what we are seeing is related to Mathematica's pattern
of memory usage and is not an accurate assessment of compute time.
In short, without access to the actual implementation of Mathematica
it is impossible to definitively determine how compute and memory
resources are actually being used by these expressions. The behavior
of Scan is curious but it may mean little more than that Scan is more
complicated internally than a naive implementation: Map with no
storage allocation, would indicate. At any rate the behavior of the
expressions and the fact that the timing is dependent on the number
of times they are executed as well as the order of execution
indicates that Mathematica is optimizing the expressions, most likely
for memory usage, and thus one cannot infer much about their
computational efficiency.
I should make clear that I executed all of the Timing statements in
one cell. I'm sure the behavior would be yet again different if I
executed each in its own cell.
Regards,
Ssezi
- References:
- Timing of looping operators
- From: dh <dh@metrohm.ch>
- Timing of looping operators