GitLab

We have the general:

gcd             :: (Integral a) => a -> a -> a
gcd 0 0         =  error "Prelude.gcd: gcd 0 0 is undefined"
gcd x y         =  gcd' (abs x) (abs y)
                   where gcd' a 0  =  a
                         gcd' a b  =  gcd' b (a `rem` b)

And a specialisation for Int only:

{-# RULES
"gcd/Int->Int->Int"             gcd = gcdInt
 #-}

gcdInt (I# a) (I# b) = g a b
   where g 0# 0# = error "GHC.Base.gcdInt: gcd 0 0 is undefined"
         g 0# _  = I# absB
         g _  0# = I# absA
         g _  _  = I# (gcdInt# absA absB

Thanks to the gcdInt# primop.

If we use Word here, or other Int types, we get the slow version (which is only 10x slower, surprisingly):

main = print . sumU
             . mapU (gcd 2)
             $ enumFromToU 0 (100000000 :: Word)

Comes out as:

 time ./henning 
150000002
./henning  25.73s user 0.05s system 99% cpu 25.936 total

Versus:

$ time ./henning 
150000002
./henning  2.33s user 0.00s system 99% cpu 2.334 tota

So there are two things we can do here to improve the situation:

Step 1: Add rules for getting from the other Int* types to gcdInt#

{-# RULES

"gcd/Int32->Int32->Int32" gcd = gcdInt32

  #-}

gcdInt32 :: Int32 -> Int32 -> Int32
gcdInt32 x y = fromIntegral ((gcd :: Int -> Int -> Int) (fromIntegral x) (fromIntegral y))

For example, takes the running time from 28 seconds to 2.4seconds, for:

main = print . sumU
             . mapU (gcd 2)
             $ enumFromToU 0 (100000000 :: Int32)

Step 2: optionally add a gcdWord#

We could then also add a gcdWord# primop,or perhaps just following fromIntegral, and test for negative first, then conditionally dispatch to gcdInt.

What do people think?

Trac metadata

Trac field	Value
Version	6.8.2
Type	Bug
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	Compiler
Test case
Differential revisions
BlockedBy
Related
Blocking
CC	double, gcd, performance, rules
Operating system	Unknown
Architecture	Unknown