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.
fib
,fibWC
, andfibWC1
are rather closed together and approximately 16 times as fast asfibW
. $\endgroup$fibWC
andfibWC1
callfib[]
... Shouldn't that befibWC
andfibWC1
, respectively? $\endgroup$