Replacement for GMP: Update

[Simon Peyton-Jones]

Sounds good! 

Remember that the memory-allocation mechanism is crucial.  How does BN
do that?


| (3) I have been looking at how to implement a dual-constructor-in-a-
| pointer for Integer (i.e., merge constructors of small Integers and
| big Integers into the Int#).  Would that solution be workable or
| might it break current Haskell programs?  Just a thought.

Making a single word contain either a pointer or a non-pointer
(depending on the setting of some bit) would have some quite global
implications, as would losing 32 bit precision from Int#.  I suggest
that you do not couple these two projects together!  Do the GMP thing
first, then investigate this later.  We have quite a few bit-twidding
ideas that we have never followed up.

Simon


| -----Original Message-----
| From: Peter Tanski [mailto:p.tanski at gmail.com]
| Sent: 10 August 2006 06:32
| To: Simon Peyton-Jones; Simon Marlow; Esa Ilari Vuokko; John Meacham
| Cc: glasgow-haskell-users at haskell.org
| Subject: Replacement for GMP: Update
| 
| Simon PJ, Simon, Esa and John,
| 
| Here is an update on what I have been doing so far in making a grand
| attempt to replace GMP.
| 
| (1) evaluate replacement libraries
| 	LibTomMath:
| 		Pros-
| 		* has all the operators GMP offered
| 		Cons-
| 		* slow; about half as fast as OpenSSL in my tests for
simple
| 		   mathematical operations, much slower if you account
for time to
| 		   write or resize memory. (There is another MP library,
which
| 		   LibTomMath is based on, that is also very
slow--student work)
| 		* not even reentrant; needs significant modification
| 		* beta-release; needs a bit of work to get it to
production level
| 		* configuration needs to be written (not really
portable, messy)
| 	ARPREC:
| 		Pros-
| 		* very fast (essentially does everything through the
| 		   Floating Point Unit of a CPU)
| 		* complex mathematical operations
| 		* very precise
| 		* already thread safe (through C++ thread-safe statics)
| 		Cons-
| 		* no bitwise operations (not even left and right-shifts)
| 		* difficult configuration (everything runs by setting a
precision
| level;
| 		   ("precision level" ~= number of words (doubles) in
array)
| 		   it does not automatically resize memory; conversion
from
| 		   MP Real to Integer relies specially on careful
precision-level)
| 		* memory inefficient (underestimates the number of real
digits you
| 		   can fit into a double, i.e., a 64-bit double has 48
bits of
| precision,
| 		   holding about 9.6 digits per byte, resulting in an
848-byte array
| 		   to hold an MP number with 1000 digits).
| 	OpenSSL:
| 	Crypto++ (http://www.eskimo.com/~weidai/cryptlib.html):
| 	Botan (http://botan.randombit.net/):
| 		Pros-
| 		* all of these are fast, since all use Integers to
support
| cryptography;
| 		   (Crypto++ and Botan are C++ crypto-libraries, all
licenses good)
| 		* all of these provide most basic mathematical
operations
| 		Cons-
| 		* none of these provide &, |, ^(xor) bitwise operators
| 		* Botan has least mathematical operators of the three
| 		* none provide lcm operator
| 		* all would realistically have to have the Integer
libraries stripped
| 		   out of the distribution and repackaged for GHC
| 
| Summary: I finally settled on modifying OpenSSL, since that would be
| the easiest to work with under GHC's hood (plain C code, not C++).  I
| have to:
| 	a. make OpenSSL's BN thread-safe (add thread local storage, at
least)
| 	b. optimally add configure-conditional parallelism to BN
(through PVM)
| 	c. add &, |, ^, lcm and a few other operations
| 	d. separate the BN from the rest of OpenSSL and rename the
symbols
| to avoid conflicts (necessary because I have to modify the library
| anyway)
| 
| (2) work on GHC:
| 	* finally understand C--; know what I need to modify
| 	* work through Makefiles: touch and go; I haven't mapped out all
the
| 	   variable settings from configure.in on down when it comes to
DLLs
| 	Comment:
| 		for the Makefile in ghc/rts, in lines 300-346,
| 		GC_HC_OPTS += -optc-O3
| 		--isn't this problematic?  gcc, from -O2 on includes
-fgcse which may
| 		   *reduce* runtime performance in programs using
computed gotos;
| 		  -fgcse is actually run twice, because
-frerun-cse-after-loop is also
| 		  set at -O2.  Would it be better to pass individual
flags, such as
| 	 	  -funroll-loops and -falign-loops=16 (ppc, Intel
setting)?
| 
| (3) I have been looking at how to implement a dual-constructor-in-a-
| pointer for Integer (i.e., merge constructors of small Integers and
| big Integers into the Int#).  Would that solution be workable or
| might it break current Haskell programs?  Just a thought.
| 
| -Peter
| 
|