[MLton] Re: [Haskell-cafe] fastest Fibonacci numbers in the West

[Matthew Fluet]

> At some point in the past, I wrote:
> >> For the moment, mlton-generated binaries crash computing fib (10^8-1),
> 
> On Thu, Jan 27, 2005 at 09:09:10AM -0500, Matthew Fluet wrote:
> > As one of the MLton developers, I'm quite saddened to here it. ;-)
> > Seriously, if you are getting a segfault or related crash, please report a
> > bug.  If you are getting an unexpected uncaught exception, we would still 
> > be interested in hearing more details.
> > Given that you successfully compute fib (10^7-1), it is clear that you are 
> > computing the result at IntInf.int.  I don't see any reason why going up 
> > an order of magnitude would cause any problems.
> 
> This was originally reported by Excedrin on freenode #haskell; I
> managed to reproduce the issue locally. He claimed that he was going
> about reporting it properly and I've deferred completely to him on this.

If you encounter Excedrin again on #haskell, please encourage him to file 
the bug.  If you are able to reproduce the problem, then I encourage you 
to file the bug.

> In all honesty, I'd expect runtime crashes due to e.g. unhandled
> allocation failures in lower-level arbitrary-precision arithmetic
> libraries relied upon by the runtime upon to be normal for exceedingly
> large integer results, so I don't think it's significant, but he did.

We agree with your opinion, which is why the MLton implementation of the
Basis Library explicitly performs the allocation for all IntInf.int
objects (as a word vector, invoking the GC when necesary), before handing
off to the GnuMP library.  The lower-level library should never need to
perform allocation; hence, there are no unhandled allocation failures.

There was a bug in mlton-20040227 which occasionally computed the wrong
size for (relatively small) IntInf.int objects, which in turn could
manifest itself in GnuMP attempting to do reallocation, which in turn
could lead to segfaults.  It was fixed in mlton-20041109.

> There is actually more bizarre news. The naive implementation of the
> Fibonacci recurrence in mlton actually outperforms my O(lg(n))
> bitreversal etc. algorithm implemented in Haskell up to around 10^5-1.
> The ability of the efficient runtime to compensate for naive algorithms
> in this case is a particularly promising result for mlton.

Interesting.  MLton "optimizes" the representation of IntInf.int to use 
either a single word (with one "tag" big, yielding 31-bits of precision) 
or to use the GnuMP representation for larger integers.  Of course, you 
cross that threshold at about fib 45, so that certainly doesn't account 
for your results.