Changes between Version 12 and Version 16 of ReplacingGMPNotes/TheCurrentGMPImplementation

Jan 15, 2007 4:02:29 AM (11 years ago)

add note implementation details in practice


  • ReplacingGMPNotes/TheCurrentGMPImplementation

    v12 v16  
    107107As for printing GMP numbers, [[GhcFile(libraries/base/GHC/Num.lhs)]] defines a special internal function `jtos` to handle `showsPrec` and `showList` for `Integer` as an instance of the class `Show`.  The `jtos` function uses the primitive GMP-based function `quotRemInteger` and performs many conversions from Integer to Int.  This is not as efficient as the internal GMP functions, especially for large numbers, because each conversion allocates extra storage for GMP as noted in [wiki:ReplacingGMPNotes#OptimisationOpportunities Replacing GMP -- Optimisation Opportunities].
     109=== GMP Library Implementation ===
     111[general notes, not finished] The GMP library, like most multi-precision libraries has a fundamental limitation that might seem odd if you are only familiar with Haskell--not likely, but it bears mention anyway!  GMP functions require that their operands be separate entities.  (Remember: an operation such as `a + b` has three entities: the two operands and the result.)  That is, if you want to add `mpz_t a` to `mpz_t b`, and place the result in `mpz_t c`, you are fine but if you try to add `a` to `a` you will run into trouble.  (The problem is, the multi-precision integer library functions are designed so the operands cannot alias; this is more of a problem for complex operations such as multiplication than simple operations like addition.)  This limitation might be overcome by designing the API differently, i.e., compare the operands in Haskell, Cmm or whatever before you pass them to the _add function and create a separate copy of the operand if it is indeed the same then you are o.k. for the case where two operands cannot be the same.  For the case where one of the operands and the result is the same you would have to check outside the general Haskell, Cmm or whatever function wrapping the _add function--you would seem to need a higher level construct.  In any case, this is an annoying thing if you expect `Integer` to behave the same way as `Int`.  Here is an example from GHCi:
     113  (in GHCi)
     114  > let m_integer = 123456789 :: Integer
     115  > let n_integer = m_integer + m_integer
     116  -- this will show o.k., but the implementation involves *always* making extra temporaries
     117  > n_integer
     118  246913578
     120  -- a = a + a
     121  > let m_integer = m_integer + m_integer
     122  > let n_integer = m_integer + m_integer
     124  -- this will be fine until you try to evaluate it:
     125  > n_integer
     126  *** Exception: stack overflow
     129''The comment on being able to do this with plain Ints is wrong.''  In fact, plain Ints in ghci (not compiled code) will also cause a stack overflow:
     131Prelude> let a = 5
     132Prelude> let a = a + a
     133Prelude> let b = a + a
     134Prelude> b
     135*** Exception: stack overflow