# Speeding up compilation of recursive functions

I am trying to understand how to speed up recursive functions via compilation. I am experimenting with the Fibonacci sequence (though this is not really what I want to do eventually). Can somebody explain why these different versions of the functions have different computational speeds?

In[2]:= num = 30;

In[3]:= Table[Fibonacci[i], {i, 1, num}]

Out[3]= {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, \
987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, \
121393, 196418, 317811, 514229, 832040}

In[4]:= fib = Compile[{{n, _Integer}},
Module[
{},
Which[n == 0, 0, n == 1, 1, True, fib[n - 1] + fib[n - 2]]],
CompilationTarget -> "C"
];

In[5]:= RepeatedTiming@Table[fib[i], {i, 1, num}]

Out[5]= {5.449, {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,
610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025,
121393, 196418, 317811, 514229, 832040}}

In[6]:= fibW = Compile[{{n, _Integer}},
Module[
{},
Which[n == 0, 0, n == 1, 1, True, fibW[n - 1] + fibW[n - 2]]
]
];

In[7]:= RepeatedTiming@Table[fibW[i], {i, 1, num}]

Out[7]= {1.3769, {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,
610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368,
75025, 121393, 196418, 317811, 514229, 832040}}

In[8]:= fibWC = Compile[{{n, _Integer}},
Module[
{},
Which[n == 0, 0, n == 1, 1, True, fib[n - 1] + fib[n - 2]]
],
CompilationTarget -> "C"
];

In[9]:= RepeatedTiming@Table[fibWC[i], {i, 1, num}]

Out[9]= {0.1071, {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,
610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368,
75025, 121393, 196418, 317811, 514229, 832040}}

In[10]:= fibWC1 = Compile[{{n, _Integer}},
Module[
{},
Which[n == 0, 0, n == 1, 1, True, fib[n - 1] + fib[n - 2]]
],
CompilationTarget -> "C",
CompilationOptions -> {"InlineExternalDefinitions" -> True}
];

In[11]:= RepeatedTiming@Table[fibWC1[i], {i, 1, num}]

Out[11]= {5.467, {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,
610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368,
75025, 121393, 196418, 317811, 514229, 832040}}


In particular, fibW is faster than fib, which indicates that compilation to C does not help. But then, fibWC is much faster than fibW and fibWC1,(whihc inlines external definitions, but is otherwise the same as fibWC) on the otherhand is much slower.

I am wondering what is happening behind the scenes and in the end what is the best way to compile.

• This is weird. I can confirm such varying timings when running this on a fresh kernel. But when I compile all the functions twice after a kernel restart and check the timings, then fib, fibWC, and fibWC1 are rather closed together and approximately 16 times as fast as fibW. Jul 10, 2017 at 0:46
• Your functions fibWC and fibWC1 call fib[]... Shouldn't that be fibWC and fibWC1, respectively? Jul 10, 2017 at 3:39
• In general, support for compiling recursive functions in Mathematica is quite limited. Jul 10, 2017 at 7:50

With

CompiledFunctionToolsCompilePrint@fib


you will see that fib calls MainEvaluate in order to call itself recursively. As the CompilationTarget is set to "C", this means that certain code for the communication with the MathKernel is injected into the C-code for fib. This code gets compiled into a LibraryFunction automatically. At runtime, every call from the LibraryFunction behind fib to MainEvaluate means that the library function has to wait for the MathKernel to process this call.

You can show the produced code with

ExportString[fib, "C"]


The pseudocode of fibW is the same as that of fib but the CompilationTarget is now the Wolfram Virtual Machine ("WVM"). Code compiled into "WVM" is usually not as fast as code compiled to "C", but as it is still somewhat on the Mathematica side, the communication with the MathKernel tends to be a bit quicker (e.g., see here).

Personally, I would suggest that you abandon the idea of recursion and use a plain, simple loop in C, instead. This will produce the first 30 Fibonacci numbers 70000 times faster than fibWC.

fibC = Compile[{{n, _Integer}},
Module[{a, x, y, z},
a = Table[1, {i, 1, n}];
x = 1;
y = 1;
Do[z = x + y; a[[i]] = z; x = y; y = z;, {i, 3, n}];
a
],
CompilationTarget -> "C"
];
`