# About auto-compiling and performance between Do and Fold

I was investigating how Fold could improve performance vs Do. I tested the code

AbsoluteTiming[
sum = 1.0;
inc = 1.0;
Do[inc = inc*Sin[10.5]/i; sum = sum + Tan[inc], {i, 10^5}];
sum]


The output is

Out[] = {2.303896, 0.105747}


I have hoped that using Fold could improve the performance:

AbsoluteTiming@
Fold[{#[[1]]*Sin[10.5]/(#2 + 1), #[[2]] + Tan@#[[1]]} &,
{Sin[10.5], 1.0}, N@Range[10^5]]


However, this code is not faster:

Out[] = {2.471189, {-5.537337857006675*10^-462146, 0.105747}}


I have some questions concerning the above example:

(1) [Partially solved. See EDIT] Why the Fold here is not faster? I thought it should have been auto-compiled and thus faster. But it didn't.

(2) [Solved. See EDIT] Here Mathematica is using precision much higher than double precision (by having number as small as 10^{-462146}). Would it be possible to set precision to boost performance? I tried SetPricision and SetAccuracy. The precision changes but it doesn't improve performance.

(3) [Solved. See Mr. Wizard's example in his answer] Another problem of Fold is that one has first to generate a long list (length 10^5 in this example). For much larger list, the Fold method may use too much memory. Is it possible to use functional way (not necessarily Fold) in a more memory-efficient way?

Thank you very much!

PS: I met this question when trying to reproduce Mr.Wizard's answer of the below thread, with some modifications. I can reproduce Wizard's result, where Fold boots the performance greatly compared with Do. But I don't understand why my above example is not as good.

Alternatives to procedural loops and iterating over lists in Mathematica

EDIT:

(a) Rojo's comment is the answer of (2): SetSystemOptions["CatchMachineUnderflow" -> False]

(b) About the performance of Fold: on Mathematica v7 after disabling CatchMachineUnderflow, the Fold code is 10x faster then Do code. However, on Mathematica v9 the Fold code is a bit slower than Do. This seems like a regression in Mathematica. For comparison, this code has 10x improvement than the Do version: Fold[# + Sin[#2] &, 1.0, Range[10^6]] both on v7 and v9.

• Perhaps you have to decrease "FoldCompileLength" -> 100? As detalied here mathematica.stackexchange.com/a/1816/745. Also your function can easily be compiled manually, giving you more control (for example you can compile to C etc...) – Ajasja Jan 25 '14 at 20:33
• @Ajasja : Thanks for the comment! I think 10^5 is greater than 100 and thus Fold should have compiled (but it didn't). I have just tried "FoldCompileLength" 1, 50, Infinity. All have the same performance. Indeed, this code can be compiled to C. I actually tried that and did some benchmarks at here. Nevertheless I'd like to learn if functional programming could do better than Do-loop. – Yi Wang Jan 25 '14 at 20:42
• You can try with SetSystemOptions["CatchMachineUnderflow" -> False] to avoid the low numbers – Rojo Jan 25 '14 at 20:42
• @Rojo : Thanks! This answers one of my questions! The performance is improved by 10x. Fold is still no faster than Do though. – Yi Wang Jan 25 '14 at 20:49

In version 7, after setting the option that Rojo described, your Fold code is nearly an order of magnitude faster than Do:

SetSystemOptions["CatchMachineUnderflow" -> False];

AbsoluteTiming[
sum = 1.0;
inc = 1.0;
Do[inc = inc*Sin[10.5]/i; sum = sum + Tan[inc], {i, 10^6}];
sum
]

{2.0100028, 0.105747}

AbsoluteTiming@
Fold[{(#[[1]] Sin[10.5])/(#2 + 1), #[[2]] + Tan[#[[1]]]} &, {Sin[10.5], 1.0},
N@Range[10^6]]

{0.2500003, {0., 0.105747}}


The Fold code can be made faster still with a few optimizations:

sin = Sin[10.5];

AbsoluteTiming[
Fold[
{Divide[#[[1]] sin, #2], #[[2]] + Tan[#[[1]]]} &,
{sin, 1.0},
Range[2, 10^6 + 1]
]
]

{0.1600025, {0., 0.105747}}


In this case splitting the operations and vectorizing Tan yields a greater improvement:

AbsoluteTiming[
1 + Tr @ Tan @ FoldList[Divide[# sin, #2] &, sin, Range[2, 10^6 + 1]]
]

{0.0600001, 0.105747}


This may use additional memory, but trading memory consumption for greater speed is a common programming compromise. If you need to work with longer lists you can split the list into sections and use the output of one Fold as the input for the next:

Fold[
Fold[{Divide[#[[1]] sin, #2], #[[2]] + Tan[#[[1]]]} &, #, Range[#2, #2 + 10000]] &,
{sin, 1.0},
Range[2, 10^7, 10000]
] // AbsoluteTiming

{1.8000025, {0., 0.105747}}

• Thanks a lot! This is very interesting. However, I still cannot reproduce your achievements on Mathematica 9 (and don't have M7 to test). On my machine with M9, your Fold code uses a little longer time then Do. I noticed on my machine CompileOptions->AutomaticCompile is by default False. I set it to True but it doesn't help. Is there a way to debug why Mathematica doesn't compile the code, or any other suggestions? (Explicit Compile command works on my machine) – Yi Wang Jan 26 '14 at 9:36
• And it is very strange that for your previous example on Fold here I can reproduce that Fold is about 20x faster than Do. But on your current answer every Fold example takes about 10x longer on my machine (while Do example takes about the same time). – Yi Wang Jan 26 '14 at 10:02
• I have also tested that if I consider a similar (but different) problem: Fold[# + Sin[#2] &, 1.0, Range[10^6]]. This is 10x faster than Do on my machine. But somehow if # is a list as in the example on my question, the performance breaks down. – Yi Wang Jan 26 '14 at 10:11
• @YiWang I'm afraid I can't be of help because I don't have v9, but I hope that someone else can and will answer your questions. – Mr.Wizard Jan 26 '14 at 10:30
• I found that I have access to v7. I tested your examples on v7 and the performance is similar to those you gave. Thus my problem may be a regression on v9? I think I had better accept your answer, and discuss this regression elsewhere. Thank you very much! – Yi Wang Jan 26 '14 at 10:53

Simple and fast method:

SetSystemOptions["CatchMachineUnderflow" -> False];
inc = 1.0;
a = Sin[10.5];
1 + Sum[Tan[inc *= Divide[a, n]], {n, 10^5}]


It is about 70% faster than your example with Do.

• Thanks! It is interesting to see Divide is different from /. Also it's clever to use Sum here! – Yi Wang Jan 26 '14 at 10:07