8
$\begingroup$

Why is the compiled function so slow? I have seen question 41344 but don't understand any potential relevance.

Here are the two functions for comparison

logisticMap[x0_, μ_, n_] := Module[{i}, 
  RecurrenceTable[{x[i + 1] == μ x[i] (1 - x[i]), x[1] == x0}, x, {i, 1, n}]]
logisticMapC = Compile[{{x0, _Real}, {μ, _Real}, {n, _Integer}},
   t = {x0};
   For[i = 2, i <= n, i++, 
    AppendTo[t, μ t[[i - 1]] (1 - t[[i - 1]])]];
   , CompilationTarget -> "C"];

Compiler is Visual Studio 2015 Community Edition; compiling from MMA 10.1

Timing results as follows:

Module[{i}, Timing[For[i = 1, i <= 1000, i++, logisticMap[0.1, 3.55, 1000]]]]
(* {0.468003, Null} *)

Module[{i}, Timing[For[i = 1, i <= 1000, i++, logisticMapC[0.1, 3.55, 1000]]]]
(* {20.0929, Null} *)

That is not the sort of performance change I was hoping for; can anyone suggest what is wrong and whether I can actually gain an increase in speed by compilation?

I am still a beginner with MMA, please assume minimal knowledge.

$\endgroup$
  • $\begingroup$ AppendTo certainly has horrible performance, probably it calls back to Mathematica to manage your list. Create a list/array of fixed size, ideally outside the function (before calling the compiled function) and use that. $\endgroup$ – masterxilo Sep 30 '16 at 17:30
  • $\begingroup$ I don't think you should be compiling this function. Try running this: << CompiledFunctionTools` CompilePrint[logisticMapC] and note the several MainEvaluate calls. Typically if you see these you shouldn't be compiling, as you are still needing to revert to Mathematica for the call which can add more latency than you save. Not all functions are compilable. $\endgroup$ – ktm Sep 30 '16 at 17:30
  • 8
    $\begingroup$ Unfortunately you can't just tack Compile around any function you want and expect it to go faster, there's somewhat of an art to it. $\endgroup$ – ktm Sep 30 '16 at 17:31
  • 1
    $\begingroup$ [Edit: just seem the preceding comment... will look into that] Ah. Art. Perhaps my expectation was unreasonable, but if a simple For loop, arithmetic and list appending is so slow when and why should I expect improvements elsewhere? How to tell? it does take effort to recast into compilable form (RecurrenceTable, for all its simplicity not being compilable) - how am I to know whether it would be a worthwhile investment? I suppose I must be apprenticed to The Guild of MathematicaL Arts for 10 Years to learn The Art... $\endgroup$ – Julian Moore Sep 30 '16 at 17:47
  • 1
    $\begingroup$ Well, if you're still a beginner, I really suggest you not to touch Compile, it's the toy of experienced user. Currently it's more cost-efficient for you to learn to write code in Mathematica-style. If you still insist on using Compile, you can begin from this answer. $\endgroup$ – xzczd Oct 1 '16 at 3:41
13
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks: clear concise and to the point (additional thanks to @user6014 for saying how I might have detected the main evaluator calls with << CompiledFunctionTools` CompilePrint[logisticMapC]). I should have thought more about how AppendTo might work, but as this was my 1st compilation test after getting the VS Studio 2015 to work, I was perhaps distracted. If certain functions are known to be slow, it would be nice if the Compile function had a "warnings" option about using such... maybe it does... will check docs. $\endgroup$ – Julian Moore Oct 1 '16 at 6:38
  • $\begingroup$ @JulianMoore, AppendTo is particularly bad, in both compiled and ordinary expressions. Generally in Mathematica if you are creating a list you should not start with an empty list and grow it element by element, instead use a function designed to return a list (like Table or NestList in Daniel's examples). The doc page on Constructing Lists shows many such functions. $\endgroup$ – Simon Woods Oct 1 '16 at 9:16
  • $\begingroup$ Yes, and it's easy to see why in hindsight; however I lost sight of the fact that deep down I probably knew this while focussing on compilation... this particular function is called rarely and it wasn't a concern - I picked a poor example, but have still learned a lot. Thx. $\endgroup$ – Julian Moore Oct 1 '16 at 9:19
16
$\begingroup$

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} *)
| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for illustrating a variety of techniques in detail; that gives usedul guidance for the future. $\endgroup$ – Julian Moore Oct 1 '16 at 6:34

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.