Re: [GHC] #10678: integer-gmp's runS seems unnecessarily expensive

4 Aug 2015

      #10678: integer-gmp's runS seems unnecessarily expensive
-------------------------------------+-------------------------------------
        Reporter:  rwbarton          |                   Owner:
            Type:  bug               |                  Status:  new
        Priority:  normal            |               Milestone:
       Component:  Compiler          |                 Version:  7.10.1
  (CodeGen)                          |
      Resolution:                    |                Keywords:
Operating System:  Unknown/Multiple  |            Architecture:
 Type of failure:  Runtime           |  Unknown/Multiple
  performance bug                    |               Test Case:
      Blocked By:                    |                Blocking:
 Related Tickets:                    |  Differential Revisions:
-------------------------------------+-------------------------------------

Comment (by rwbarton):

 Replying to [comment:7 simonpj]:
...
Good!  Can you give a small example of your last para?  I bet it's
 something like
{{{
case (runRW (\s -> I# x)) of (# _ , I# y) -> blah
}}}
Right, so in integer-gmp, where I previously had
 {{{
 runS :: S RealWorld a -> a      -- type S s a = State# s -> (# State# s, a
 #)
 runS m = case runRW# m of (# _, a #) -> a
 }}}
 when `a = BigNat` (`data BigNat = BN# ByteArray#`), I can instead use
 {{{
 runS_BigNat :: S RealWorld BigNat -> BigNat
 runS_BigNat m = case runRW# (\s -> case m s of (# s', BN# ba #) -> (# s',
 ba #)) of
   (# _, ba #) -> BN# ba
 }}}

 The idea is

 * `m` usually simplifies to something like
   {{{
   \s0 -> case newByteArray# n s0 of
     (# s1, arr #) -> case someGmpFunction arr s1 of
       s2 -> case unsafeFreezeByteArray# arr s2 of
         (# s3, farr #) -> (# s3, BN# farr #)
   }}}
   so in the "inner case" in `runS_BigNat`, the constructor `BN#` will
 cancel

 * Now the caller of `runS_BigNat` (say, `plusBigNat`) has the CPR property
 because the `BN#` constructor is visible outside the `runRW#`

 * Its caller in turn (say, `plusInteger`) looks like
   {{{
   plusInteger (Jp# x) (Jp# y) = Jp# (plusBigNat x y)
   }}}
   but `Jp#`'s argument is unboxed for size reasons
   {{{
   data Integer = ... | Jp# {-# UNPACK #-} !BigNat | ...
   }}}
   so `Jp# (plusBigNat x y)` would have meant extracting the field from a
 `BN#` and repacking it into a `Jp#`. But by calling the unboxed worker we
 can avoid ever allocating an intermediate `BN#` constructor.

 Note that the transformation `runS -> runS_BigNat` is always valid for any
 `m`, even though it looks like a nested CPR situation. The reason is that
 the context of the `runRW#` is strict in the second argument anyways. To
 determine when the transformation is a good idea for a particular argument
 `m`, we can use regular CPR analysis on the function `\s -> case m s of (#
 _, r #) -> r`.

--
Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10678#comment:9
GHC http://www.haskell.org/ghc/
The Glasgow Haskell Compiler