10
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Little hint: NestCompileLength is 100 by default. $\endgroup$ – Karsten 7. Jun 4 '17 at 2:22
  • $\begingroup$ Also RepeatedTiming can be misleading. $\endgroup$ – Karsten 7. Jun 4 '17 at 2:28
  • $\begingroup$ @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? $\endgroup$ – Stitch Jun 4 '17 at 2:48
  • $\begingroup$ 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. $\endgroup$ – Michael E2 Jun 4 '17 at 4:44
  • $\begingroup$ @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. $\endgroup$ – xzczd Jun 4 '17 at 6:23
11
$\begingroup$

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

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

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.
$\endgroup$
  • $\begingroup$ Do you have any insight or references as to why or how pure functions work so much better? +1 $\endgroup$ – jjc385 Jun 4 '17 at 4:39
  • $\begingroup$ 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. $\endgroup$ – Karsten 7. Jun 4 '17 at 6:03
  • 2
    $\begingroup$ @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. $\endgroup$ – Karsten 7. Jun 4 '17 at 6:34
  • 1
    $\begingroup$ @jjc385 Also check the comment by xzczd and the links therein for why the other approaches don't autocompile properly. $\endgroup$ – Karsten 7. Jun 4 '17 at 8:57
  • $\begingroup$ Thank you! Your last bullet point is a great rule! It should probably be added here $\endgroup$ – Stitch Jun 4 '17 at 15:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.