[MLton] IntInf implementation questions

[Stephen Weeks]

> Re IntInf multiply, as I recall, the time it takes for a 32*32->64
> multiply is the same as for a 32*32->32 multiply on the x86, so if
> it could be done inline (no call to a C routine), it might still be
> faster to do the big digit multiply and then check for the right
> kind of overflow.  Probably not a big win unless you are frequently
> multiplying smalls with a product that doesn't fit.

We don't have the primitive support to do the smallMul inline, so I
guess that the right thing is to do the trick Appel mentions, which is
fast when multiplying 2 smalls to get a small.

For completeness, here is the trick.

If

 i' = 2i + 1
 j' = 2j + 1

then

 (i' - 1) * floor(j' / 2) + 1 = 2 (ij) + 1

So, one can multiply two smalls using 4 bitops: zero tag (or sub1),
shift (/2), mul, and add 1.  And as with plus, the zero tag can be
simplified at compile time if one argument is a constant.  Counting
areSmall and the overflow check, that gives 6 bitops, one test, and
one overflow check.  That should be a big win over our current
approach.

> Re dontInline, is this exported to any thing any where?

mlton -show-basis shows that it is not.  However, it is a small piece
of code and doesn't rely on any privileged primitives, so you can
easily put it in your own code.

      val dontInline: (unit -> 'a) -> 'a =
         fn f =>
         let
            val rec recur: int -> 'a =
               fn i =>
               if i = 0
                  then f ()
               else (ignore (recur (i - 1))
                     ; recur (i - 2))
         in
            recur 0
         end