Performance of Nest vs. Do

Question

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?

Answer 1

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

Answer 2

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.