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

Closing, as this ticket is subsumed by #3055.

Note: See TracTickets for help on using tickets.