Opened 5 years ago

Last modified 5 years ago

#9431 new feature request

integer-gmp small Integer multiplication does two multiplications on x86

Reported by: rwbarton Owned by:
Priority: normal Milestone:
Component: Compiler (NCG) Version: 7.9
Keywords: Cc: hvr, simonmar
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

timesInteger begins thusly:

timesInteger :: Integer -> Integer -> Integer
timesInteger (S# i) (S# j)         = if isTrue# (mulIntMayOflo# i j ==# 0#)
                                     then S# (i *# j)
                                     else -- ...

The x86 backend implements mulIntMayOflo# as a (word, word) -> double word multiplication, followed by bit manipulation to test for overflow of the low word. Then, if there was no overflow, on the next line we multiply the operands again.

We should be able to do better here. We need a new primop that combines mulIntMayOflo# with the actual multiplication result, at least in the non-overflow case (though with some more work we might be able to turn the double word result directly into a large Integer), and then we need to update timesInteger to use it.

The LLVM backend probably has the same behavior, though it might be smart enough to notice that the multiplication is repeated; I haven't checked its assembly output.

Change History (2)

comment:1 Changed 5 years ago by hvr

It'd be interesting to know *why* mulIntMayOflo# was introduced instead of a version that'd output the non-overflowing result as well.

Update: mulIntMayOflo# was originally introduced in 7dee9e10796acdc3af04f222ef06808ad3d1b611

Last edited 5 years ago by hvr (previous) (diff)

comment:2 Changed 5 years ago by thomie

Cc: simonmar added
Component: CompilerCompiler (NCG)
Type of failure: None/UnknownRuntime performance bug

For reference, from libraries/integer-gmp2/src/GHC/Integer/Type.hs:

-- | Multiply two 'Integer's
 timesInteger :: Integer -> Integer -> Integer
 timesInteger _       (S# 0#) = S# 0#
 timesInteger (S# 0#) _       = S# 0#
 timesInteger x       (S# 1#) = x
 timesInteger (S# 1#) y       = y
 timesInteger x      (S# -1#) = negateInteger x
 timesInteger (S# -1#) y      = negateInteger y
 timesInteger (S# x#) (S# y#)
   = case mulIntMayOflo# x# y# of
     0# -> S# (x# *# y#)
     _  -> timesInt2Integer x# y#
Note: See TracTickets for help on using tickets.