id summary reporter owner description type status priority milestone component version resolution keywords cc os architecture failure testcase blockedby blocking related differential wikipage
2270 gcd is specialised only for Int dons dons@… "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?" bug closed normal 6.12.1 libraries/base 6.8.2 duplicate rules, performance, double, gcd Unknown/Multiple Unknown/Multiple None/Unknown