Replacement for GMP

[Peter Tanski]

Simon,

> (1) We'd be delighted to use a BSD-licensed alternative to GMP in GHC.
> It's been a long-standing issue, just never quite important enough to
> get done.  If either or both of you are willing to put in the legwork,
> and emerge with an implementation that we understand and can maintain,
> we'd be happy to use it.  We'll certainly help in any way we can.

I shouldn't speak for Esa, who kindly offered advice if I run into  
trouble.  More than a few people seem interested in this, so maybe it  
will be a bunch of use can carry it off.

> (2) We're concerned about performance.  Replacing GMP, but losing
> substantial performance on bignum-intensive programs would be
> unattractive.

Definitely.  You had mentioned OpenSSL as a possible replacement (at  
least it contains all the currently implemented Prelude functions  
over Integer except for lcm and integral powers).  I had mentioned  
ARPREC and Esa had cautioned against attempting to integrate with a C+ 
+ library.  LibToMath covers everything and Esa had worked on that  
before.  Would you be able to suggest another possibility?

> (3) It's unlikely (albeit not impossible) that we'll get GMP-level
> performance out of a Haskell-only bignum library.  ... this would be a
> step backwards!

It certainly would.  As noted below I have been searching for high  
performance options because a Bignum library for a builtin-type such  
as Integer should optimally perform like an embedded system.

> (4) The tricky spot for any library is memory allocation.  Our GMP- 
> based
> implementation works by getting GMP to use GHC's allocator to allocate
> memory.  This means that every bignum is allocated in the Haskell  
> heap,
> is automatically managed by GHC's garbage collector, which is Very  
> Good.

How would lib-based memory allocation affect concurrency and  
parallelism?  I mentioned to Esa that the library should be threaded,  
not merely thread-safe or reentrant.  (OpenSSL is reentrant, through  
the CTX system, I believe.)

> But because the allocator is statically linked to GMP, you can only  
> have
> one allocator, and that leads to difficulties if you have another  
> bit of
> the same binary that also wants to use GMP.

That seems to be the second main reason to replace GMP.  I could  
modify the Bignum library to be multi-threaded, with a separate  
thread system tied to RTS-memory.  Would that be workable?

> (Of course, we could *copy*
> GMP, changing all the function names.  That would eliminate the
> problem!)

In an email I sent to Bulat Ziganshin, I noted that such a fix would  
be legally worrisome: it seems like a cosmetic change, like changing  
the titles of chapters in a book.  At the least I think it would  
worry the lawyers of any company using GHC to produce commercial  
products.

> I suppose that one alternative is to let the library use 'malloc', but
> make a foreign-pointer proxy for every bignum, which calls 'free' when
> the GHC garbage collector frees it.  Not as efficient, though.

Esa and I had discussed the possibility of copying the value returned  
from the Bignum lib into the GHC system, which certainly would not be  
very memory efficient, but might be faster.  Among other memory  
modifications, it might be a good idea to initialise the Bignum lib  
with the RTS and modify the lib with a memory cache or garbage  
collection system of its own.

> (5) If you do go ahead, could you pls start a Wiki page on the GHC
> development Wiki (http://hackage.haskell.org/trac/ghc), where you
> document your thoughts, the evolving design etc?  You might want to
> extract the core of this email thread to initialise the Wiki page.

I got the page started on a document here already.  I will have the  
rest up very soon.

On a related note, I am working through the Makefiles for the RTS; I  
could clean things up a bit while I am at it.  One of the big goals  
seemed to be to move to Cabal--or was that just for the Haskell  
libraries?  I had mentioned this to Esa: would you be interested in  
moving to a higher level configuration system for heterogeneous  
program parts, such as Bakefile or Scons?  Bakefile, at least, would  
result in the current make-based install but would be more easily  
maintainable and would allow variations for different compilers.

Best regards,
Peter