Mathematica - Timing of looping operators

Author

Timing of looping operators

2005-11-23, 3:59 am

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???

Daniel

Hermann Schmitt

2005-11-23, 7:59 am

Hello Daniel,
loops are normally more efficient then recursive function calls, because in
function calls more temporary variables have to be created.
In my oo system I first tried recursive function calls, but then changed to
loops.
Hermann Schmitt
----- Original Message -----
From: "dh" <dh@metrohm.ch>
Subject: Timing of looping operators

> 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???
>
> Daniel
>

Pratik Desai

2005-11-24, 7:59 am

Sseziwa Mukasa

2005-11-24, 7:59 am

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

carlos@colorado.edu

2005-11-24, 7:59 am

In my experience Do is noticeably faster than For
in loops that do relatively little in the body. If the body does a
lot of computation, the difference is not important.

The advantage of For over Do is immediate translation to C,
C++, Java, ... when Mathematica is used as a
development prototype tool.

Jean-Marc Gulliet

2005-11-24, 7:59 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
====
must be fun[i]
>
> 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???
>
> Daniel
>
Hi Daniel,

in (c) your function must be fun[i0 rather than f[i]. Here what I get in
bot cases (identity and square): the loop is systematically the
slowest... and pure functions are the fastest, which is no surprise
according to Mathematica gospel :-)

In[1]:=
n = 10^6;
d = Table[i, {i, n}];
fun[x_] := x;

In[4]:=
Timing[(#1 & ) /@ d; ]

Out[4]=
{0.109 Second,Null}

In[5]:=
Timing[Scan[#1 & , d]; ]

Out[5]=
{0.781 Second,Null}

In[6]:=
Timing[Scan[fun, d]; ]

Out[6]=
{0.954 Second,Null}

In[7]:=
Timing[fun /@ d; ]

Out[7]=
{0.968 Second,Null}

In[8]:=
Timing[Do[fun[i], {i, n}]; ]

Out[8]=
{1.188 Second,Null}

In[9]:=
fun2[x_] := x^2;

In[10]:=
Timing[(#1^2 & ) /@ d; ]

Out[10]=
{2.172 Second,Null}

In[11]:=
Timing[Scan[#1^2 & , d]; ]

Out[11]=
{2.094 Second,Null}

In[12]:=
Timing[Scan[fun2, d]; ]

Out[12]=
{2.359 Second,Null}

In[13]:=
Timing[fun2 /@ d; ]

Out[13]=
{2.328 Second,Null}

In[14]:=
Timing[Do[fun2[i], {i, n}]; ]

Out[14]=
{2.609 Second,Null}

In[15]:=
$Version

Out[15]=
5.2 for Microsoft Windows (June 20, 2005)

Best regards,
/J.M.

carlos@colorado.edu

2005-11-24, 7:59 am

The difference can be striking for built-in functions,
e.g. the dot product:

n=1000000; a=b=Table[N[i],{i,n}];
Print[Timing[a.b]];
Print[Timing[Sum[a[[i]]*b[[i]],{i,n}]]];

Print[Timing[s=0; For[i=1,i<=n,i++,s+=a[[i]]*b[[i]]] ]];
Print[Timing[s=0; Do[s+=a[[i]]*b[[i]],{i,n}] ]];

Times: 0.03, 13.2, 28.4, 19.9 sec

Norbert Marxer

2005-11-24, 7:59 am

Hello Daniel

I think your conclusions about the timings of Map and Do are not
correct, because you use the function "fun" with Map and the undefined
function "f" with Do.

If I use the function "fun" in all three cases I get roughly (note:
even though I restart the Kernel each time I get slightly different
results with every evaluation) the following times: {1.1, 1.3, 1.5}.

If I define "fun" as x^2 I get the following times: {1.1, 3.6, 3.6}.

Therefore I conclude that using Map has advantages over the Do
construct.

Best regards
Norbert Marxer
www.mec.li

Sponsored Links