Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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

enter image description here

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

enter image description here

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?

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

2 Answers

up vote 4 down vote accepted

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

enter image description here

share|improve this answer
    
This explains m my error for my Ac2 function. Thanks. –  VF1 Jan 29 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 at 21:17
    
Put Block[{diag, temp}, within Compile. –  RiemannZeta Jan 29 at 21:36
add comment

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

enter image description here 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

enter image description here

share|improve this answer
    
@Szabolcs Could you please explain the behavior at the bottom of my answer? Or do you think this merits another question? –  VF1 Jan 29 at 19:34
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.