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

[William Lee Irwin III]

At some point in the past, I wrote:
>> 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.

On Thu, Jan 27, 2005 at 09:47:50AM -0500, Matthew Fluet wrote:
> 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.

Okay, where's the bugzilla/whatever?


At some point in the past, I wrote:
>> 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.

On Thu, Jan 27, 2005 at 09:47:50AM -0500, Matthew Fluet wrote:
> 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.

$ dpkg --list mlton
Desired=Unknown/Install/Remove/Purge/Hold
| Status=Not/Installed/Config-files/Unpacked/Failed-config/Half-installed
|/ Err?=(none)/Hold/Reinst-required/X=both-problems (Status,Err: uppercase=bad)
||/ Name           Version        Description
+++-==============-==============-============================================
ii  mlton          20041109-1     Optimizing compiler for Standard ML


At some point in the past, I wrote:
>> 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.

On Thu, Jan 27, 2005 at 09:47:50AM -0500, Matthew Fluet wrote:
> 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.

What the naive recurrence ends up doing is n steps of 1 addition. It's
unclear whether the Haskell code gets update-in-place, but it's doing
4 multiplies and 2 additions for each step, and ceil(lg(n)) steps. I
suspect the multiplication of small integers is not being special-cased,
among other things. Reorganizing to share subresults can reduce this to
3 multiplications and 3 additions, but the compiler should probably be
able to do this by itself anyway, since integers are exact, and it isn't
speeding anything up when I try doing it. So it may be that the addition
vs. multiplication tradeoff is very steep, which sounds wrong to me.
And comparing the advanced implementation in mlton with the naive one
in mlton suggests that it's not gmp's multiplication algorithm, as the
O(lg(n)) algorithm handily trounces the naive recurrence in mlton-to-mlton
comparisons for small n. So there are as-of-yet-unknown factors at work.


-- wli