Opened 13 years ago

Closed 8 years ago

Last modified 3 years ago

#601 closed task (fixed)

Replace GMP

Reported by: simonmar Owned by:
Priority: normal Milestone:
Component: Compiler Version: None
Keywords: Integer-gmp gmp Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case: N/A
Blocked By: Blocking:
Related Tickets: #9281 Differential Rev(s):
Wiki Page:

Description (last modified by simonpj)

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.

Attachments (2)

base.html (327.6 KB) - added by igloo 9 years ago.
Comparing nofib runs with GMP and integer-simple
jmp.c (8.5 KB) - added by JimCrayne 9 years ago.
partial re-implementation of gmp

Download all attachments as: .zip

Change History (21)

comment:1 Changed 12 years ago by simonmar

Architecture: Unknown
Description: modified (diff)
difficulty: Difficult (1 week)
Operating System: Unknown

comment:2 Changed 11 years ago by simonpj

Description: modified (diff)

comment:3 Changed 11 years ago by igloo

Milestone: 6.8

See also 311 and ReplacingGMPNotes.

comment:4 Changed 11 years ago by igloo

Test Case: N/A

comment:5 Changed 10 years ago by simonmar

Milestone: 6.8 branch_|_

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.

comment:6 Changed 10 years ago by 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:

comment:7 Changed 10 years ago by 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.

comment:8 Changed 10 years ago by 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.

Changed 9 years ago by igloo

Attachment: base.html added

Comparing nofib runs with GMP and integer-simple

comment:9 Changed 9 years ago by 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%

comment:10 Changed 9 years ago by igloo

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

Changed 9 years ago by JimCrayne

Attachment: jmp.c added

partial re-implementation of gmp

comment:11 Changed 9 years ago by 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.

comment:12 Changed 9 years ago by simonmar

Architecture: UnknownUnknown/Multiple

comment:13 Changed 9 years ago by simonmar

Operating System: UnknownUnknown/Multiple

comment:14 in reply to:  9 Changed 9 years ago by 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.

comment:15 Changed 9 years ago by 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.

comment:16 Changed 9 years ago by igloo

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

comment:17 Changed 8 years ago by simonmar

difficulty: Difficult (1 week)Difficult (2-5 days)

comment:18 Changed 8 years ago by igloo

Resolution: Nonefixed
Status: newclosed
Type of failure: None/Unknown

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

comment:19 Changed 3 years ago by hvr

Keywords: Integer-gmp gmp added
Note: See TracTickets for help on using tickets.