Why is my compiled function slower than a regular function?

Question

I have the following functions:

Block[{n, diag},
 snake`diag[n_] = Ceiling[1/2 (-1 + Sqrt[1 + 8 n])];
 snake`alongdiag[n_, diag_] = {0, diag + 1} + (n - diag (diag - 1)/2) {1, -1};
 snake[n_] = snake`alongdiag[n, snake`diag[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?

Answer 1

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

Answer 2

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[3] 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