[GHC] #13193: Integer (gmp) performance regression?

[GHC]

#13193: Integer (gmp) performance regression?
-------------------------------------+-------------------------------------
        Reporter:  j.waldmann        |                Owner:
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.0.1
      Resolution:                    |             Keywords:  newcomer
Operating System:  Linux             |         Architecture:  x86_64
 Type of failure:  Runtime           |  (amd64)
  performance bug                    |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by rwbarton):

 Yes, the additional allocations do have to do with the new integer-gmp,
 though they aren't entirely the integer-gmp library's fault. The
 additional allocations occur in subtraction (in `pred`).
 {{{
 -- | Subtract one 'Integer' from another.
 minusInteger :: Integer -> Integer -> Integer
 minusInteger x       (S# 0#)            = x
 minusInteger (S# 0#) (S# INT_MINBOUND#) = Jp# (wordToBigNat
 ABS_INT_MINBOUND##)
 minusInteger (S# 0#) (S# y#)            = S# (negateInt# y#)
 minusInteger (S# x#) (S# y#)
   = case subIntC# x# y# of
     (# z#, 0# #) -> S# z#
     (# 0#, _  #) -> Jn# (wordToBigNat2 1## 0##)
     (# z#, _  #)
       | isTrue# (z# ># 0#) -> Jn# (wordToBigNat ( (int2Word# (negateInt#
 z#))))
       | True               -> Jp# (wordToBigNat ( (int2Word# z#)))
 -- more cases, that aren't (S# _) (S# _)
 }}}
 Based on looking at the assembly, this seems to have been compiled in
 7.10.1 to something like
 {{{
 minusInteger x y = case y of {
   S# y# -> case y# of {
     0# -> ...
     INT_MINBOUND# -> ...
     __DEFAULT__ -> let minusY = S# (negateInt# y#)
                    in case x of {
                       S# x# -> ...
                       Jp# {} -> ...
                       Jn# {} -> ...
                    }
     }
   Jp# {} -> ...
   Jn# {} -> ...
   }
 }}}
 Note that we allocate `S# (negateInt# y#)` even though we're unlikely to
 actually need it, and will never need it more than once.

 I see two issues here:

 * There are many special cases in `minusInteger`, that are almost never
 helpful, and harmful in the common case of small integers (i.e., `S#`).
 The old code which began
   {{{
 minusInteger (S# i)      (S# j)    = case subIntC# i j of ...
 }}}
   was much better. But, by itself this shouldn't cause additional
 ''allocations'', just additional work in the form of conditionals and
 branches.

 * GHC floated out `S# (negateInt# y#)`, which was a bad choice: increased
 allocations, and never any gain, as far as I can see.

   Aha, now that I look at the rest of `minusInteger`, `(negateInt# y#)`
 does appear again in some branches like
   {{{
 minusInteger (Jp# x) (S# y#)
   | isTrue# (y# >=# 0#) = bigNatToInteger (minusBigNatWord x (int2Word#
 y#))
   | True                = Jp# (plusBigNatWord x (int2Word# (negateInt#
 y#)))
 }}}
   But it's never used more than once per branch, and the `S#` box that we
 allocated is still not used.

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13193#comment:6>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler