# Performance of Nest vs. Do

When I am iterating the logistic function using a pure function, comparing Do and Nest:

x = 0.1; Do[x = 3 x (1 - x), 300] // RepeatedTiming
Nest[3 # (1 - #) &, .1, 300] // RepeatedTiming


0.00026

7.8*10^-6

Tremendous speed advantage when using Nest.

However, when I define a function first, then

lf[x_] := 3 x (1 - x)
x = 0.1; Do[x = lf[x], 300] // RepeatedTiming // First
Nest[lf[#] &, .1, 300] // RepeatedTiming // First


0.00043

0.00045

Now Nest is actually slower oftentimes!

I can improve it by not using the Slot

Nest[lf, .1, 300] // RepeatedTiming // First


But it still is slow:

0.000342

Why? How can it be improved?

• Little hint: NestCompileLength is 100 by default. Jun 4, 2017 at 2:22
• Also RepeatedTiming can be misleading. Jun 4, 2017 at 2:28
• @Karsten7. Well, compiling it with Compile[{}, Nest[lf, .1, 300]] doesn't change much -- still 0.000382 even with increased NestCompileLength. Can you elaborate on misleading of RepeatedTiming? What is better then? Jun 4, 2017 at 2:48
• If the function being nested refers to a symbol, then most likely the compiled form would evaluate the symbol via MainEvaluate[], and diminish or destroy any advantage in compiling. So probably neither lf nor lf[#] & is compiled, but 3 # (1 - #) & is. Jun 4, 2017 at 4:44
• @Karsten7. No, the true reason is function definition based on pattern-matching cannot be compiled. This question is strongly related (if not a duplicate) to this one. Also, see the 3rd rule in this answer. Jun 4, 2017 at 6:23

The main reason why

x = 0.1; Do[x = 3 x (1 - x), 300] // AbsoluteTiming // First


0.000393629

and

lf[x_] := 3 x (1 - x)
x = 0.1; Do[x = lf[x], 300] // AbsoluteTiming // First
Nest[lf[#] &, .1, 300] // AbsoluteTiming // First


0.000643239
0.000691691

are slower than

Nest[3 # (1 - #) &, .1, 300] // AbsoluteTiming // First


0.000161729

is the fact, that the last Nest can and does make use of autocompilation.
The default NestCompileLength is 100:

SystemOptions["CompileOptions" -> "NestCompileLength"]


{"CompileOptions" -> {"NestCompileLength" -> 100}}

Autocompilation can be switched off for Nest by setting its compile length to Infinity.

SetSystemOptions["CompileOptions" -> "NestCompileLength" -> Infinity]


Now

Nest[3 # (1 - #) &, .1, 300] // AbsoluteTiming // First


0.000461127

is much slower and has a performance similar to the first Do.

By using a precompiled version of lf a performance that is even better than the pure function with Nest's autocompilation can be achieved:

clf = Compile[{{x, _Real, 0}}, 3 x (1 - x)];
Nest[clf, .1, 300] // AbsoluteTiming // First


0.000128982

However, if the time needed for compiling is included

First@AbsoluteTiming[
clf2 = Compile[{{x, _Real, 0}}, 3 x (1 - x)];
Nest[clf2, .1, 300]
]


0.000187792

one can see that this uses more time in total than the pure function with autocompilation, as calling clf2 for every evaluation adds an additional overhead.

After switching autocompilation back on

SetSystemOptions["CompileOptions" -> "NestCompileLength" -> 1];


Nest does need some extra time, because it tries to autocompile clf now

Nest[clf, .1, 300] // AbsoluteTiming // First


0.000188127

• You don't need clf[#] & -- clf is already a function. +1 however for addressing compilation. Jun 4, 2017 at 6:02
• @Mr.Wizard yes. Thanks for pointing that out. I'll remeasure my timings, as that added an additional overhead. Jun 4, 2017 at 6:08

I get results that differ form yours more than can be accounted form by my computer system being slower than yours. Here is what I'm seeing.

(x = 0.1; Do[x = 3 x (1 - x), 300];x) // AbsoluteTiming


{0.000406, 0.653113}

 Nest[3 # (1 - #) &, .1, 300] // AbsoluteTiming


{0.000177, 0.653113}

f[x_] := 3 x (1 - x)

func = Function[Evaluate[f[#]]]


3 (1 - #1) #1 &

(x = 0.1; Do[x = f[x], 300]; x) // AbsoluteTiming


{0.000712, 0.653113}

Nest[f, .1, 300] // AbsoluteTiming


{0.000586, 0.653113}

Nest[func, .1, 300] // AbsoluteTiming


{0.000177, 0.653113}

This last version is exactly the same internally as the 2nd version and, not surprisingly, gives the same results.

Conclusions

• Nest is alway faster than Do.
• Nest is optimized for pure functions.
• When you want to iterate over user defined function, when feasible it is best to convert it into a pure function and iterate over the pure function.
• Do you have any insight or references as to why or how pure functions work so much better? +1 Jun 4, 2017 at 4:39
• Your timings are slower, because you are using AbsoluteTiming instead of the RepeatedTiming used in the question. You can compare With[{func = Function[Evaluate@lf[#]]}, Nest[func, .1, 300] ] // AbsoluteTiming // First with With[{func = Function[Evaluate@lf[#]]}, Nest[func, .1, 300] ] // RepeatedTiming // First. On my PC the output of the former one is a factor 10 bigger. RepeatedTiming does reuse the autocompiled function multiple times. Jun 4, 2017 at 6:03
• @jjc385 Using pure functions allows autocompiling to create an efficient, properly compiled function, as it is not capable of inlining external definitions (as far as I know; check the documentation for details about inlining. Jun 4, 2017 at 6:34
• @jjc385 Also check the comment by xzczd and the links therein for why the other approaches don't autocompile properly. Jun 4, 2017 at 8:57
• Thank you! Your last bullet point is a great rule! It should probably be added here Jun 4, 2017 at 15:05