gcd is specialised only for Int
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 gcdWordWe 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 |