compile - Why is my compiled function slower than a regular function?

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

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