GHC: Ticket #601: Replace GMP
http://ghc.haskell.org/trac/ghc/ticket/601
<p>
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).
</p>
<p>
One possible alternative would be to use the bignum library from OpenSSL, which is available under a BSD-style license.
</p>
en-usGHChttp://ghc.haskell.org/trac/ghc/chrome/site/ghc_logo.png
http://ghc.haskell.org/trac/ghc/ticket/601
Trac 1.0.7simonmarThu, 15 Dec 2005 11:00:21 GMTdescription changed; difficulty, os, architecture set
http://ghc.haskell.org/trac/ghc/ticket/601#comment:1
http://ghc.haskell.org/trac/ghc/ticket/601#comment:1
<ul>
<li><strong>difficulty</strong>
set to <em>Difficult (1 week)</em>
</li>
<li><strong>os</strong>
set to <em>Unknown</em>
</li>
<li><strong>description</strong>
modified (<a href="/trac/ghc/ticket/601?action=diff&version=1">diff</a>)
</li>
<li><strong>architecture</strong>
set to <em>Unknown</em>
</li>
</ul>
TicketsimonpjWed, 02 Aug 2006 12:10:56 GMTdescription changed
http://ghc.haskell.org/trac/ghc/ticket/601#comment:2
http://ghc.haskell.org/trac/ghc/ticket/601#comment:2
<ul>
<li><strong>description</strong>
modified (<a href="/trac/ghc/ticket/601?action=diff&version=2">diff</a>)
</li>
</ul>
TicketiglooFri, 13 Oct 2006 22:30:14 GMTmilestone set
http://ghc.haskell.org/trac/ghc/ticket/601#comment:3
http://ghc.haskell.org/trac/ghc/ticket/601#comment:3
<ul>
<li><strong>milestone</strong>
set to <em>6.8</em>
</li>
</ul>
<p>
See also <a class="closed ticket" href="http://ghc.haskell.org/trac/ghc/ticket/311" title="bug: gmp's memory management (closed: fixed)">311</a> and <a class="wiki" href="http://ghc.haskell.org/trac/ghc/wiki/ReplacingGMPNotes">ReplacingGMPNotes</a>.
</p>
TicketiglooFri, 20 Oct 2006 16:12:22 GMTtestcase set
http://ghc.haskell.org/trac/ghc/ticket/601#comment:4
http://ghc.haskell.org/trac/ghc/ticket/601#comment:4
<ul>
<li><strong>testcase</strong>
set to <em>N/A</em>
</li>
</ul>
TicketsimonmarMon, 12 Nov 2007 13:36:01 GMTmilestone changed
http://ghc.haskell.org/trac/ghc/ticket/601#comment:5
http://ghc.haskell.org/trac/ghc/ticket/601#comment:5
<ul>
<li><strong>milestone</strong>
changed from <em>6.8 branch</em> to <em>_|_</em>
</li>
</ul>
<p>
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.
</p>
TicketiglooSun, 23 Mar 2008 23:10:02 GMT
http://ghc.haskell.org/trac/ghc/ticket/601#comment:6
http://ghc.haskell.org/trac/ghc/ticket/601#comment:6
<p>
In the HEAD, <tt>integer</tt> is now a separate package, by default provided by <tt>libraries/integer-gmp</tt>. If you make a variant in <tt>libraries/integer-foo</tt> and change <tt>libraries/Makefile</tt> to refer to <tt>integer-foo</tt> instead of <tt>integer-gmp</tt> then it will use your variant instead. You need to export the same functions with the same types.
</p>
<p>
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:
</p>
<ul><li>Write an Integer performance suite
</li><li>Compare the current implementation to a direct GMP binding, i.e. not using RTS primitives
</li><li>Compare the GMP implementation to a pure Haskell binding, e.g. <a class="ext-link" href="http://www.haskell.org/pipermail/libraries/2007-August/007909.html"><span class="icon"></span>http://www.haskell.org/pipermail/libraries/2007-August/007909.html</a>
</li><li>Compare the GMP implementation to a binding to a BSD-licenced C library
</li></ul>
TicketiglooMon, 21 Apr 2008 10:48:04 GMT
http://ghc.haskell.org/trac/ghc/ticket/601#comment:7
http://ghc.haskell.org/trac/ghc/ticket/601#comment:7
<p>
<a class="ext-link" href="http://darcs.haskell.org/libraries/integer-ultra-simple/"><span class="icon"></span>http://darcs.haskell.org/libraries/integer-ultra-simple/</a> is a very simple (and inefficient) pure Haskell implementation. It validates, except <tt>print003</tt> and <tt>print006</tt> give different output (probably OK, due to different <tt>Integer</tt> representations) and <tt>simplrun004(optc)</tt> needs more stack space.
</p>
<p>
This is not a reasonable replacement for Integer, although it's close to something that might be.
</p>
TicketiglooFri, 25 Apr 2008 02:53:42 GMT
http://ghc.haskell.org/trac/ghc/ticket/601#comment:8
http://ghc.haskell.org/trac/ghc/ticket/601#comment:8
<p>
<a class="ext-link" href="http://darcs.haskell.org/libraries/integer-simple/"><span class="icon"></span>http://darcs.haskell.org/libraries/integer-simple/</a> 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.
</p>
TicketiglooSat, 14 Jun 2008 15:43:26 GMTattachment set
http://ghc.haskell.org/trac/ghc/ticket/601
http://ghc.haskell.org/trac/ghc/ticket/601
<ul>
<li><strong>attachment</strong>
set to <em>base.html</em>
</li>
</ul>
<p>
Comparing nofib runs with GMP and integer-simple
</p>
TicketiglooSat, 14 Jun 2008 15:55:11 GMT
http://ghc.haskell.org/trac/ghc/ticket/601#comment:9
http://ghc.haskell.org/trac/ghc/ticket/601#comment:9
<p>
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.
</p>
<p>
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.
</p>
<pre class="wiki">Compile Times
-1 s.d. -7.6%
+1 s.d. +26.9%
Average +8.2%
</pre>
TicketiglooSat, 14 Jun 2008 16:00:36 GMT
http://ghc.haskell.org/trac/ghc/ticket/601#comment:10
http://ghc.haskell.org/trac/ghc/ticket/601#comment:10
<p>
An alternative would be to do the S#/J# trick with integer-simple, of course; it's a bit unpleasant, though.
</p>
TicketJimCrayneWed, 03 Sep 2008 21:43:58 GMTattachment set
http://ghc.haskell.org/trac/ghc/ticket/601
http://ghc.haskell.org/trac/ghc/ticket/601
<ul>
<li><strong>attachment</strong>
set to <em>jmp.c</em>
</li>
</ul>
<p>
partial re-implementation of gmp
</p>
TicketJimCrayneWed, 03 Sep 2008 21:45:53 GMT
http://ghc.haskell.org/trac/ghc/ticket/601#comment:11
http://ghc.haskell.org/trac/ghc/ticket/601#comment:11
<p>
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)
</p>
<p>
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.
</p>
<p>
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.
</p>
TicketsimonmarTue, 30 Sep 2008 15:37:14 GMTarchitecture changed
http://ghc.haskell.org/trac/ghc/ticket/601#comment:12
http://ghc.haskell.org/trac/ghc/ticket/601#comment:12
<ul>
<li><strong>architecture</strong>
changed from <em>Unknown</em> to <em>Unknown/Multiple</em>
</li>
</ul>
TicketsimonmarTue, 30 Sep 2008 15:51:01 GMTos changed
http://ghc.haskell.org/trac/ghc/ticket/601#comment:13
http://ghc.haskell.org/trac/ghc/ticket/601#comment:13
<ul>
<li><strong>os</strong>
changed from <em>Unknown</em> to <em>Unknown/Multiple</em>
</li>
</ul>
TicketiglooThu, 02 Apr 2009 13:43:38 GMT
http://ghc.haskell.org/trac/ghc/ticket/601#comment:14
http://ghc.haskell.org/trac/ghc/ticket/601#comment:14
<p>
Replying to <a class="ticket" href="http://ghc.haskell.org/trac/ghc/ticket/601#comment:9" title="Comment 9">igloo</a>:
</p>
<blockquote class="citation">
<p>
However, the attached base.html (comparing nofib runs with GMP and integer-simple) makes me think that that is infeasible
</p>
</blockquote>
<p>
I did some digging to find out what was going on. Using an instrumented <tt>integer-gmp</tt>, it turned out that, during a build of GHC, there were 7,312,684 calls to <tt>GHC.Integer</tt> that returns a <tt>J#</tt> result. Of these, 4,479,189 were calls to <tt>decodeFloat</tt>, and 2,804,132 were calls to <tt>quotRem</tt>. This is because functions like <tt>round</tt> call <tt>properFraction</tt>, which looked like this:
</p>
<pre class="wiki"> 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)
}
}
</pre><p>
where <tt>m</tt> and <tt>n</tt> are <tt>Integer</tt>s (and always <tt>J#</tt>, despite never being big enough to need to be).
In the HEAD this has now been rewritten to use <tt>Int</tt> rather than <tt>Integer</tt>, so all of those <tt>J#</tt> integers disappear (we're also looking at reducing the number of <tt>round</tt> calls we make, but that no longer affects this ticket).
</p>
<p>
There are now only 28,741 calls returning <tt>J#</tt> integers; 22,306 of them are <tt>wordToInteger</tt> calls, which are very cheap with simple-integer (which builds <tt>Integer</tt>s out or <tt>Word#</tt>s).
</p>
<p>
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.
</p>
TicketiglooFri, 10 Apr 2009 12:34:13 GMT
http://ghc.haskell.org/trac/ghc/ticket/601#comment:15
http://ghc.haskell.org/trac/ghc/ticket/601#comment:15
<p>
<strong>Current status</strong>
</p>
<p>
The <tt>Integer</tt> type is now provided by a separate <tt>integer</tt> package, which provides an API that hides the implementation details. By default this is <tt>integer-gmp</tt>. To change it, set <tt>INTEGER_LIBRARY=integer-foo</tt> in <tt>mk/build.mk</tt>.
</p>
<p>
There is an alternative implementation <a class="ext-link" href="http://darcs.haskell.org/libraries/integer-simple/"><span class="icon"></span>integer-simple</a>, although as we don't regularly test builds with it you may need to make a few tweaks to get it to work. <tt>integer-simple</tt> is intended to be easily understood, entirely Haskell code that is <em>fast enough</em>. For serious number crunching one of the highly tuned big integer libraries will be needed, but hopefully <tt>integer-simple</tt> will suffice for normal use. In order to test this, we need to do some testing, e.g. nofib runs.
</p>
<p>
It would also be interesting to separate out the <tt>J#/S#</tt> wrapper from the GMP <tt>Integer</tt>, and to compare all 4 combinations: <tt>GMP</tt>, <tt>GMP+J#/S#</tt>, <tt>simple</tt>, <tt>simple+S#/J#</tt>.
</p>
<p>
If <tt>integer-simple</tt> is indeed fast enough, then I think that it solves all of the problems with <tt>integer-gmp</tt>. We would also have packages like <tt>gmp</tt> for those who want to use the fast C implementations.
</p>
TicketiglooSat, 25 Apr 2009 17:51:00 GMT
http://ghc.haskell.org/trac/ghc/ticket/601#comment:16
http://ghc.haskell.org/trac/ghc/ticket/601#comment:16
<p>
Related webpage, if we split GMP out into its own library: <a class="ext-link" href="http://haskell.forkio.com/gmpwindows"><span class="icon"></span>http://haskell.forkio.com/gmpwindows</a>
</p>
TicketsimonmarMon, 16 Nov 2009 13:14:44 GMTdifficulty changed
http://ghc.haskell.org/trac/ghc/ticket/601#comment:17
http://ghc.haskell.org/trac/ghc/ticket/601#comment:17
<ul>
<li><strong>difficulty</strong>
changed from <em>Difficult (1 week)</em> to <em>Difficult (2-5 days)</em>
</li>
</ul>
TicketiglooSun, 22 Nov 2009 15:42:23 GMTstatus, resolution changed; failure set
http://ghc.haskell.org/trac/ghc/ticket/601#comment:18
http://ghc.haskell.org/trac/ghc/ticket/601#comment:18
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>closed</em>
</li>
<li><strong>failure</strong>
set to <em>None/Unknown</em>
</li>
<li><strong>resolution</strong>
changed from <em>None</em> to <em>fixed</em>
</li>
</ul>
<p>
It's now possible to build GHC with different integer libraries, so I think we can call this ticket fixed.
</p>
TickethvrWed, 23 Jul 2014 10:30:36 GMTkeywords, related set
http://ghc.haskell.org/trac/ghc/ticket/601#comment:19
http://ghc.haskell.org/trac/ghc/ticket/601#comment:19
<ul>
<li><strong>keywords</strong>
<em>Integer-gmp</em> <em>gmp</em> added
</li>
<li><strong>related</strong>
set to <em>#9281</em>
</li>
</ul>
Ticket