Changes between Version 3 and Version 4 of ReplacingGMPNotes


Ignore:
Timestamp:
Aug 3, 2006 12:08:32 AM (9 years ago)
Author:
ptanski
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • ReplacingGMPNotes

    v3 v4  
    2323        In the current GMP implementation, GMP is configured to use GHC's GC memory, so C code in the same binary as GHC-compiled Haskell code cannot access GMP separately.  This problem was noted in [http://hackage.haskell.org/trac/ghc/ticket/311 bug Ticket #311].  Simon Peyton-Jones suggested that a simple renaming of GHC-GMP functions would solve this problem and Bulat Ziganshin suggested simply using an automated tool to do this.  See [http://www.haskell.org/pipermail/glasgow-haskell-users/2006-August/010679.html Replacement for GMP].
    2424
     25        The custom-memory configuration of GMP uses GMP's [http://swox.com/gmp/manual/Custom-Allocation.html#Custom-Allocation Custom Allocation] routines.  Alternative libraries may not have this facility builtin.
     26
     273. Other Improvements to Integer
     28
     29        Most of the suggestions in this section come from discussions in the glasgow-haskell-users list thread [http://www.haskell.org/pipermail/glasgow-haskell-users/2006-July/010654.html returning to Cost of Integer].  In particular, [http://www.haskell.org/pipermail/glasgow-haskell-users/2006-July/010660.html John Meacham's suggestion] to use a !ForeignPtr to data held by the normal GMP system library and store the value in an unboxed Int if the number of significant digits in Integer could fit into the size of an Int.  For those who are curious, a guide to GHC primitives is available (in an unformatted version) in ghc/compiler/prelude/primops.txt.pp; here is a link to [http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/prelude/primops.txt.pp?rev=1.37;content-type=text%2Fplain CVS version of primops.txt.pp].  You might want to search for the text "section "The word size story."", and especially the text "section "Integer#"".
     30
     31        The current GMP implementation of Integer is:
     32{{{
     33data Integer = Int# ByteArr#
     34}}}
     35        where the Int# counts the number of [http://swox.com/gmp/manual/Nomenclature-and-Types.html#Nomenclature-and-Types limbs] (a GMP term referring to parts of a multi-precision number that fit into a 32 or 64 bit word, depending on the machine) and the ByteArr# is the actual array in RTS-GC memory holding the limbs.  The sign of the Int# is used to indicate the sign of the number represented by the ByteArr#. 
     36
     37        This current implementation of Integer means that all Integers hold a !ByteArr, even if there is only one limb (which would fit into an Int, as Int is also the representation of a machine word in current implementations).  The suggestion discussed by John Meacham, [http://www.haskell.org/pipermail/glasgow-haskell-users/2006-August/010664.html Lennart Augustsson], [http://www.haskell.org/pipermail/glasgow-haskell-users/2006-August/010677.html Simon Marlow] and [http://www.haskell.org/pipermail/glasgow-haskell-users/2006-August/010687.html Bulat Ziganshin] was to change the representation of Integer so the Int# could be either a pointer to the Bignum library array of limbs or, if the number of significant digits could fit into say, 31 bits, to use the extra bit as an indicator of that fact and hold the entire value in the Int#, thereby saving the memory from the ByteArr# and increasing the speed with an unboxed Int#. 
     38
     39        Note that the downside to this approach would mean that:
     40        * pointers would have to be constrained (the size of an actual pointer may be greater than 32 bits on some machines (it is not defined by the C99 standard)); and,
     41        * either Ints in general would all be 30 or 31 bits, depending on how many bits you need to indicate the ByteArr#, or you would have to come up with a new primitive type.
     42
    2543=== Overview of the Current GMP Implementation ===
    2644