Speeding up compilation of recursive functions

Question

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.

Answer 1

With

CompiledFunctionTools`CompilePrint@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"
   ];