Brian Hurt wrote:
> On Sun, 12 Dec 2010, Jon Harrop wrote:
> >  let rec collatzLen(c, n) : int =
> >    if n = 1L then c else
> >      collatzLen (c+1, if Int64.rem n 2L = 0L then Int64.div n 2L else
> > Int64.add (Int64.mul 3L n) 1L);;
> >
> >  let rec loop(i, (nlen, n)) =
> >    if i = 1L then n else
> >      let ilen = collatzLen(1, i) in
> >      let nlen, n = if ilen > nlen then ilen, i else nlen, n in
> >      loop (Int64.sub i 1L, (nlen, n));;
> 
> Congratulations, Jon, you win today's Captain Obvious award.  Using
> Int64's, which are forced to be boxed, really slows things down.

Apparently boxing isn't the issue here, as I had assumed. On 32-bit, OCaml
compiles each arithmetic operation on the int64s to a C function call.

> Also, uncurrying all your arguments also slows things down.

I see <3% performance improvement from currying everything.

> Running your
> original code on my 64-bit laptop, it took 6.35s to run the 1M example.
> The following alternate code only took 0.82s, for a speed up of almost
> 7.75x.

According to Edwin, you should be able to get C-like performance by running
the OCaml in 64-bit and replacing the div and mod operations with shifts and
logical ANDs.

> Scaling your timings by a similar amount gives Ocaml a running
> speed of 3.14s in your set up, or competitive with F#.

I'd be wary of scaling timings by measurements made across different
architectures. OCaml seems to be doing completely different things on x86
and x64 here.

Cheers,
Jon.