Why is this compiled function 50x slower?

Here is the original code.

logisticMap[x0_, μ_, n_] := 
 Module[{i}, 
  RecurrenceTable[{x[i + 1] == μ x[i] (1 - x[i]), x[1] == x0}, 
   x, {i, 1, n}]]

We'll show an example so we can test other variants for correctness.

In[316]:= logisticMap[0.1, 3.55, 10]

Out[316]= {0.1, 0.3195, 0.7718401125, 0.625165483988, 0.831884285744, \
0.49647751411, 0.887455951931, 0.354566492863, 0.812414287256, \
0.541010461569}

We will also set a baseline for speed comparisons.

Module[{i}, Timing[Do[logisticMap[0.1, 3.55, 1000], {1000}]]]

(* Out[363]= {0.214107, Null} *)

A function for this is NestList.

lmap[mu_, x0_, n_] := NestList[mu *#*(1 - #) &, x0, n - 1]

In[362]:= lmap[3.55, .1, 10]

(* Out[362]= {0.1, 0.3195, 0.7718401125, 0.625165483988, 0.831884285744, \
0.49647751411, 0.887455951931, 0.354566492863, 0.812414287256, \
0.541010461569} *)

Speed is not bad.

Timing[Do[lmap[3.55, .1, 1000], {1000}]]

(* Out[360]= {0.030262, Null} *)

This can be run through Compile for a speed gain.

lmap2 = Compile[{{mu, _Real}, {x0, _Real}, {n, _Integer}}, 
   NestList[mu *#*(1 - #) &, x0, n - 1], CompilationTarget -> "C", 
   "RuntimeOptions" -> "Speed"];

lmap[3.55, .1, 10]

(* Out[365]= {0.1, 0.3195, 0.7718401125, 0.625165483988, 0.831884285744, \
0.49647751411, 0.887455951931, 0.354566492863, 0.812414287256, \
0.541010461569} *)

Timing[Do[lmap2[3.55, .1, 1000], {1000}]]

(* Out[369]= {0.009464, Null} *)

An alternative is to just use Table. This gives fairly pedestrian code. Speed is about the same.

lmap3 = Compile[{{mu, _Real}, {x0, _Real}, {n, _Integer}}, 
   Module[{elem = x0}, 
    Prepend[Table[elem = mu*elem*(1 - elem), {n - 1}], x0]], 
   CompilationTarget -> "C", "RuntimeOptions" -> "Speed"];

lmap3[3.55, .1, 10]

(* Out[392]= {0.1, 0.3195, 0.7718401125, 0.625165483988, 0.831884285744, \
0.49647751411, 0.887455951931, 0.354566492863, 0.812414287256, \
0.541010461569} *)
Timing[Do[lmap3[3.55, .1, 1000], {1000}]]

(* Out[384]= {0.008511, Null} *)

Your code is slow because

  1. You used the symbols t and i in the compiled function, but did not localise them. So they are global symbols and every assignment requires a callback to the main evaluator. To avoid this use Block or Module in the compiled expression.
  2. You used AppendTo, which is slow because it creates a copy of the list. The documentation does state (though admittedly it is well hidden) that:

Using AppendTo to accumulate values in large loops can be slow.

Tags:

Compile