Why are pure functions faster in Mathematica code? [duplicate]

This question already has answers here: Closed 11 years ago.

Possible Duplicate:

Performance difference between functions and pattern matching in Mathematica

I often find a heavy use of pure functions in a lot of the answers posted here, and often those solutions are much faster than using named patterns etc. Why is this so? Why are pure functions faster than others? Does it have to do with the mma interpreter having开发者_StackOverflow中文版 to do less work?

---

First, let us consider some sample benchmarks:

In[100]:= f[x_]:=x^2;

In[102]:= Do[#^2&[i],{i,300000}]//Timing
Out[102]= {0.406,Null}

In[103]:= Do[f[i],{i,300000}]//Timing
Out[103]= {0.484,Null}

In[104]:= Do[Function[x,x^2][i],{i,300000}]//Timing
Out[104]= {0.578,Null}

Pure functions are often (much) faster for 2 reasons. First, anonymous pure functions (those defined with the slots - # and &) do not need to resolve name conflicts for variable names. Therefore, they are somewhat faster than pattern-defined ones, where some name conflict resolution takes place. But you see that pure functions with named variables are actually slower, not faster, than pattern-defined ones. I can speculate that this is because they also have to resolve possible conflicts inside their body, while rule-based ones ignore such conflicts. In nay case, speed differences are of the order of 10-20 %.

Another, and much more dramatic, difference is when they are used in functions such as Map, Scan, Table, etc, because the latter auto-compile on large numerical (packed) lists. But while pure functions can often be compiled, pattern-defined ones fundamentally can not, so this speed gain is inaccessible to them. For example:

In[117]:= ff[x_] := Sqrt[x];

In[116]:= Map[Sqrt[#] &, N@Range[100000]]; // Timing

Out[116]= {0.015, Null}

In[114]:= Map[ff, N@Range[100000]]; // Timing

Out[114]= {0.094, Null}

---

Pure function have several advantages : - Result can be cached. - Computation can be safely parralelized. - In some cases, result can be calculated at compilation time (CTFE) and the function never executed at the end. - As the outer scope isn't modified, you don't need to pass all arguments by copy.

So, if the compiler is able to manage the optimization relative the these function, your program will be faster. Whatever the langage is.

---

actually, pattern matching seems typically faster than Function[{u},...] constructions and as fast as #&-type constructions (ignoring the possibility of compiling, which has become more exciting in mma 8).

To see this define a function to time short pieces of code:

SetAttributes[timeshort, HoldAll];
timeshort[expr_] := Module[{t = Timing[expr;][[1]], tries = 1},
    While[t < 1.,
        tries *= 2;
        t = Timing[Do[expr, {tries}];][[1]]];
    Return[t/tries]]

then try this:

ClearAll[f]; f[x_] := Cos[x]
Trace[f[5.]]
f[5] // timeshort

ClearAll[f]; f = Function[x, Cos[x]]
Trace[f[5.]]
f[5] // timeshort

ClearAll[f]; f = Cos[#] &
Trace[f[5.]]
f[5] // timeshort

which give

{f[5.],Cos[5.],0.283662}
8.45641\[Times]10^-7
Function[x,Cos[x]]
{{f,Function[x,Cos[x]]},Function[x,Cos[x]][5.],Cos[5.],0.283662}
1.51906\[Times]10^-6
Cos[#1]&
{{f,Cos[#1]&},(Cos[#1]&)[5.],Cos[5.],0.283662}
8.04602\[Times]10^-7

that is, pattern matching and #& are faster than Function. I have no idea why.

EDIT: Guess I should have checked the question belisarius suggested earlier... See here for essentially the same answer as I gave, and read the comments too for some interesting discussion.

---

Yes. It means it never has to copy much stuff, because a pure function can't change it. List processing purely can take a certain amount of copying, but usually the functional algorithms are arranged to be efficient. Once stuff gets compiled down, imperative code will be as quick (almost always), but for interpreted Mathematica bytecode, pure is usually quick.