Opened 11 years ago
Closed 10 years ago
#2270 closed bug (duplicate)
gcd is specialised only for Int
Reported by: | dons | Owned by: | |
---|---|---|---|
Priority: | normal | Milestone: | 6.12.1 |
Component: | libraries/base | Version: | 6.8.2 |
Keywords: | rules, performance, double, gcd | Cc: | |
Operating System: | Unknown/Multiple | Architecture: | Unknown/Multiple |
Type of failure: | None/Unknown | Test Case: | |
Blocked By: | Blocking: | ||
Related Tickets: | Differential Rev(s): | ||
Wiki Page: |
Description
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?
Change History (8)
comment:1 Changed 11 years ago by
difficulty: | → Unknown |
---|---|
Milestone: | → 6.10.1 |
comment:2 Changed 11 years ago by
Component: | Compiler → libraries/base |
---|
comment:3 Changed 11 years ago by
Cc: | rules performance double gcd removed |
---|---|
Keywords: | rules performance double gcd added |
comment:4 Changed 11 years ago by
Architecture: | Unknown → Unknown/Multiple |
---|
comment:5 Changed 11 years ago by
Operating System: | Unknown → Unknown/Multiple |
---|
comment:6 Changed 11 years ago by
Milestone: | 6.10.1 → 6.10.2 |
---|
comment:7 Changed 10 years ago by
Milestone: | 6.10.2 → 6.12.1 |
---|
comment:8 Changed 10 years ago by
Resolution: | → duplicate |
---|---|
Status: | new → closed |
Closing, as this ticket is subsumed by #3055.