Replace GMP

[simonmar]

GMP is a great multi-precision integer library, but its LGPL license is problematic for users of GHC (it prohibits static linking of GHC-compiled programs, for example).

One possible alternative would be to use the bignum library from OpenSSL, which is available under a BSD-style license.

[igloo]

See also 311 and ReplacingGMPNotes.

[simonmar]

We'd like to see this happen, but we aren't committing to making it happen. It'd be great if someone else could do it.

[igloo]

In the HEAD, integer is now a separate package, by default provided by libraries/integer-gmp. If you make a variant in libraries/integer-foo and change libraries/Makefile to refer to integer-foo instead of integer-gmp then it will use your variant instead. You need to export the same functions with the same types.

The current package is just the old GMP implementation, and still uses primitives from the RTS. If anyone is interested in workong on this, it would be very interesting to:

• Write an Integer performance suite
• Compare the current implementation to a direct GMP binding, i.e. not using RTS primitives
• Compare the GMP implementation to a pure Haskell binding, e.g.  http://www.haskell.org/pipermail/libraries/2007-August/007909.html
• Compare the GMP implementation to a binding to a BSD-licenced C library

[igloo]

 http://darcs.haskell.org/libraries/integer-ultra-simple/ is a very simple (and inefficient) pure Haskell implementation. It validates, except print003 and print006 give different output (probably OK, due to different Integer representations) and simplrun004(optc) needs more stack space.

This is not a reasonable replacement for Integer, although it's close to something that might be.

[igloo]

 http://darcs.haskell.org/libraries/integer-simple/ is a much more efficient implementation than ultra-simple. It validates on 32bit and 64bit machines, although simplrun004(optc) may fail by running out of stack space. This is probably because the Integer operations and/or representation are lazy, but this is fixable.

[igloo]

Comparing nofib runs with GMP and integer-simple

[igloo]

I was hopeful that we could go with a really simple Haskell impl for Integer, with serious Integer users using other types provided by packages wrapping C libraries instead; this would avoid all the pain of sometimes having to build GMP in-tree, it being LGPL, colliding with other uses of GMP, etc.

However, the attached base.html (comparing nofib runs with GMP and integer-simple) makes me think that that is infeasible, at least not without a lot of integer-simple tuning. e.g.

Compile Times
-1 s.d.     -7.6%
+1 s.d.    +26.9%
Average     +8.2%

[igloo]

An alternative would be to do the S#/J# trick with integer-simple, of course; it's a bit unpleasant, though.

[JimCrayne]

partial re-implementation of gmp

[JimCrayne]

An interim approach that could be done is creating a binary compatible, minimal, drop in replacement for GMP. People who statically link could just implement enough functions to get their program working without linker errors... eventually we'd have all of them done. I attached some starting code as the file jmp.c (Credit to Joe Crayne for this code)

The way I envision this approach is that the initial emphasis would be on just having something which works, getting it to be more efficient would come later.

Note that this approach would mean that perhaps we can borrow test-suite code from libgmp and that almost no changes would be necessary to GHC.

[igloo]

Replying to igloo:

However, the attached base.html (comparing nofib runs with GMP and integer-simple) makes me think that that is infeasible

I did some digging to find out what was going on. Using an instrumented integer-gmp, it turned out that, during a build of GHC, there were 7,312,684 calls to GHC.Integer that returns a J# result. Of these, 4,479,189 were calls to decodeFloat, and 2,804,132 were calls to quotRem. This is because functions like round call properFraction, which looked like this:

    properFraction x
      = case (decodeFloat x)      of { (m,n) ->
        let  b = floatRadix x     in
        if n >= 0 then
            (fromInteger m * fromInteger b ^ n, 0.0)
        else
            case (quotRem m (b^(negate n))) of { (w,r) ->
            (fromInteger w, encodeFloat r n)
            }
        }

where m and n are Integers (and always J#, despite never being big enough to need to be). In the HEAD this has now been rewritten to use Int rather than Integer, so all of those J# integers disappear (we're also looking at reducing the number of round calls we make, but that no longer affects this ticket).

There are now only 28,741 calls returning J# integers; 22,306 of them are wordToInteger calls, which are very cheap with simple-integer (which builds Integers out or Word#s).

Division is probably the slowest operation with simple-integer, so it seems likely that this was the cause of the slow-down. We should do some new timings to see where we stand.

[igloo]

Current status

The Integer type is now provided by a separate integer package, which provides an API that hides the implementation details. By default this is integer-gmp. To change it, set INTEGER_LIBRARY=integer-foo in mk/build.mk.

There is an alternative implementation  integer-simple, although as we don't regularly test builds with it you may need to make a few tweaks to get it to work. integer-simple is intended to be easily understood, entirely Haskell code that is fast enough. For serious number crunching one of the highly tuned big integer libraries will be needed, but hopefully integer-simple will suffice for normal use. In order to test this, we need to do some testing, e.g. nofib runs.

It would also be interesting to separate out the J#/S# wrapper from the GMP Integer, and to compare all 4 combinations: GMP, GMP+J#/S#, simple, simple+S#/J#.

If integer-simple is indeed fast enough, then I think that it solves all of the problems with integer-gmp. We would also have packages like gmp for those who want to use the fast C implementations.

[igloo]

Related webpage, if we split GMP out into its own library:  http://haskell.forkio.com/gmpwindows

[igloo]

It's now possible to build GHC with different integer libraries, so I think we can call this ticket fixed.