Performance of compiled functions (Project Euler No14)

Question

I was playing around with the project euler problem 14.

The solution I came up with is listed below as cf1. The solution works fine but I get the compiler warning:

Compile::cset: Variable max of type _Integer encountered in assignment of type _Real.

I don't get this message at all since the only assignment of max is max=l while Head@l == Integer. This error can be fixed by substituting with max=Round[l]. Any ideas?

cf1 = Compile[{}, Module[{l, max = 0, maxN = 0},
  Do[
   l = Length[NestWhileList[If[EvenQ[#], #~Quotient~2, 3 # + 1] &, n, # != 1 &]];
   If[l > max, max = l; maxN = n];
   , {n, 1, 10^4}];
   {max, maxN}
  ]];
cf1[] // Timing

{6.349241, {262, 6171}}

I also found a solution with much better performance listed below as cf2. Is it just that NestWhileList doesn't compile very good or is there another reason why this solution is so much faster?

cf2 = Compile[{}, Module[{n1, l, max = 0, maxN = 0},
  Do[
   n1 = n;
   l = 1;
   While[n1 != 1, n1 = If[EvenQ[n1], n1~Quotient~2, 3 n1 + 1]; l++];
   If[l > max, max = l; maxN = n];
   , {n, 1, 10^4}];
   {max, maxN}
  ]];
cf2[] // Timing

{0.374402, {262, 6171}}

Answer 1

You can fix the error by setting max = 0. (Note the .).

But this doesn't really Compile completely and you can check that by inspecting the 6th Part of the compiled function:

FreeQ[cf1[[6]], _Function, {0, Infinity}]

False

Whenever your compiled function has a Function definition in Part 6, your function did not compile properly. On the other hand, inspecting cf2 we see:

FreeQ[cf2[[6]], _Function, {0, Infinity}]

True

Also,

MatchQ[cf2[[6]], {{__Integer} ..}]

True

This tells us that not only did the function Compile correctly, there's no call to MainEvaluate, so the performance will be top notch as you noticed. Finally, you can get better performance if you have a C compiler by adding the Option: CompilationTarget -> "C"

cf3 = Compile[{}, 
  Module[{n1, l, max = 0, maxN = 0}, 
   Do[n1 = n; l = 1; 
    While[n1 != 1, n1 = If[EvenQ[n1], n1~Quotient~2, 3 n1 + 1]; l++]; 
    If[l > max, max = l; maxN = n];, {n, 1, 10^4}]; {max, maxN}],
  CompilationTarget -> "C"]

Timings

cf1[] // Timing
cf2[] // Timing
cf3[] // Timing

{1.578125, {262., 6171.}}
{0.093750, {262, 6171}}
{0.031250, {262, 6171}}