# Why is my compiled function slower than a regular function?

I have the following functions:

Block[{n, diag},
snakediag[n_] = Ceiling[1/2 (-1 + Sqrt[1 + 8 n])];
snakealongdiag[n_, diag_] = {0, diag + 1} + (n - diag (diag - 1)/2) {1, -1};
snake[n_] = snakealongdiag[n, snakediag[n]];]
(*A003986 on OEIS, http://oeis.org/A003986*)
A003986[n_] := BitOr @@ (snake[n] - {1, 1})
A003986c =
Compile[{{n, _Integer}}, A003986[n], CompilationTarget -> "C",
RuntimeAttributes -> {Listable}, RuntimeOptions -> "Speed"]


The functions seem very "compilable" in that they're just numerical computations. However, the compiled function performs as badly or worse:

Table[{x, A003986 /@ Range@(10^x); // Timing // First,
A003986c[Range@(10^x)]; // Timing // First}, {x, 5}]~
Prepend~{"Func", "ME", "Comp"} // TableForm Fine - perhaps the function does "too little" and the overhead from running the C code is costing too much. But then altering my code to fix that doesn't help things:

A003986l =
Compile[{{n, _Integer}}, A003986 /@ Range[n],
CompilationTarget -> "C", RuntimeOptions -> "Speed"];
Table[{x, A003986 /@ Range@(10^x); // Timing // First,
A003986l[(10^x)]; // Timing // First}, {x, 5}]~
Prepend~{"Func", "ME", "Comp"} // TableForm Both functions are approximately linear, so everything seems to be working as expected in an algorithmic regard, but this is very slow for a couple of formulas and BitOr! What is going wrong?

• Try CompiledFunctionToolsCompilePrint on A003986c -- I bet it shows a MainEvaluate. – Michael E2 Jan 29 '14 at 17:49
• @MichaelE2 Okay. Why doesn't it display the usual warning "Proceding with ME..." if it does? – VF1 Jan 29 '14 at 17:50
• @MichaelE2 Huh, it did... I'll see how I can fix that. Why wouldn't it compile? – VF1 Jan 29 '14 at 17:52
• On[Compile::noinfo] will cause a warning to be printed when you compile A003986c. – Michael E2 Jan 29 '14 at 17:55
• I think you want Compile[ ... , Evaluate@A003986[n], ...], otherwise the function won't be inlined. – Szabolcs Jan 29 '14 at 18:31

I made two changes in your code and got a dramatic time drop: I changed A003986[n] to Evaluate@A003986[n] as Szabolcs suggested and I changed diag (diag - 1)/2 to Quotient[diag (diag - 1), 2].

Table[{x, A003986 /@ Range@(10^x); // Timing // First,
A003986c[Range@(10^x)]; // Timing // First}, {x, 5}]~
Prepend~{"Func", "ME", "Comp"} // TableForm • This explains m my error for my Ac2 function. Thanks. – VF1 Jan 29 '14 at 20:47
• Why is this so much faster than my Ac3 and Ac4? Is the re-computation that results from direct inlining like you have done cheaper than writing to and storing repeated intermediate results? – VF1 Jan 29 '14 at 21:17
• Put Block[{diag, temp},  within Compile. – Chip Hurst Jan 29 '14 at 21:36

As mentioned in the comments by users @Szabolcs and @MichaelE2, the issue is that the function A003986 is not inlined by Compile automatically so the compiled function just invokes MainEvaluate.

As recommended by @Szabolcs, inlining can be achieved by using Evaluate, as shown in the function Ac2 (note I add the Listable attribute for speed):

Ac2 = Compile[{{n, _Integer}}, Evaluate@A003986[n],
CompilationTarget -> "C", RuntimeAttributes -> {Listable},
RuntimeOptions -> "Speed"]


Unfortunately, running Ac2 results in a run-time error because of some complications with BitOr.

Also, looking at the inlined function that results from the evaluation of the above one can see a couple repeated calculations. These in turn can be factored out as well, resulting in code which proceeds fully compiled:

Block[{diag, temp},
Ac3 = Compile[{{n, _Integer}},
diag = Ceiling[1/2 (-1 + Sqrt[1 + 8 n])];
temp = n - diag (diag - 1)/2;
BitOr[-1 + temp,
diag - temp], {{diag, _Integer}, {temp, _Integer}},
CompilationTarget -> "C", RuntimeAttributes -> {Listable},
RuntimeOptions -> "Speed"];]
Table[{x, A003986 /@ Range[10^x]; // Timing // First,
Ac3[Range@(10^x)]; // Timing // First}, {x, 5}]~
Prepend~{"Func", "ME", "Ac3"} // TableForm And this version is even faster, though I don't know why:

Block[{res},
Ac4 = Compile[{{n, _Integer}},
Module[{diag = Ceiling[1/2 (-1 + Sqrt[1 + 8 n])]},
res = {-1, diag} + (n - diag (diag - 1)/2) {1, -1};
BitOr[res // First, res // Last]], {{res, _Integer, 1}},
CompilationTarget -> "C", RuntimeAttributes -> {Listable},
RuntimeOptions -> "Speed"];]
Table[{x, Ac3[Range[10^x]]; // Timing // First,
Ac4[Range[10^x]]; // Timing // First}, {x, 5}]~
Prepend~{"Func", "Ac3", "Ac4"} // TableForm
` • @Szabolcs Could you please explain the behavior at the bottom of my answer? Or do you think this merits another question? – VF1 Jan 29 '14 at 19:34