Opened 6 years ago
Closed 5 years ago
#2270 closed bug (duplicate)
gcd is specialised only for Int
Reported by: | dons | Owned by: | dons@… |
---|---|---|---|
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: | Difficulty: | Unknown | |
Test Case: | Blocked By: | ||
Blocking: | Related Tickets: |
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 6 years ago by igloo
- Difficulty set to Unknown
- Milestone set to 6.10.1
comment:2 Changed 6 years ago by igloo
- Component changed from Compiler to libraries/base
comment:3 Changed 6 years ago by guest
- Cc rules performance double gcd removed
- Keywords rules performance double gcd added
comment:4 Changed 6 years ago by simonmar
- Architecture changed from Unknown to Unknown/Multiple
comment:5 Changed 6 years ago by simonmar
- Operating System changed from Unknown to Unknown/Multiple
comment:6 Changed 6 years ago by igloo
- Milestone changed from 6.10.1 to 6.10.2
comment:7 Changed 5 years ago by igloo
- Milestone changed from 6.10.2 to 6.12.1
comment:8 Changed 5 years ago by igloo
- Resolution set to duplicate
- Status changed from new to closed
Note: See
TracTickets for help on using
tickets.
Closing, as this ticket is subsumed by #3055.