[GHC] #2270: gcd is specialised only for Int

[GHC]

#2270: gcd is specialised only for Int
------------------------+---------------------------------------------------
    Reporter:  dons     |       Owner:  dons at galois.com
        Type:  bug      |      Status:  new            
    Priority:  normal   |   Component:  Compiler       
     Version:  6.8.2    |    Severity:  normal         
    Keywords:           |    Testcase:                 
Architecture:  Unknown  |          Os:  Unknown        
------------------------+---------------------------------------------------
 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?

-- 
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/2270>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler