# [GHC] #2271: floor, ceiling, round :: Double -> Int are awesomely slow

9 messages
Open this post in threaded view
|
Report Content as Inappropriate

## [GHC] #2271: floor, ceiling, round :: Double -> Int are awesomely slow

 #2271: floor, ceiling, round :: Double -> Int are awesomely slow ------------------------------------------+---------------------------------     Reporter:  dons                       |       Owner:  [hidden email]         Type:  bug                        |      Status:  new                 Priority:  normal                     |   Component:  Compiler            Version:  6.8.2                      |    Severity:  normal             Keywords:  performance, math, double  |    Testcase:                 Architecture:  Unknown                    |          Os:  Unknown         ------------------------------------------+---------------------------------  We have super-naive implementations of the RealFrac class for Double.  Consider:  {{{  {-# RULES "truncate/Double->Int" truncate = double2Int #-}  instance  RealFrac Double  where      properFraction x        = case (decodeFloat x)      of { (m,n) ->          let  b = floatRadix x     in          if n >= 0 then              (fromInteger m * fromInteger b ^ n, 0.0)          else              case (quotRem m (b^(negate n))) of { (w,r) ->              (fromInteger w, encodeFloat r n)              }          }      floor x     = case properFraction x of                      (n,r) -> if r < 0.0 then n - 1 else n  }}}  So now, we *do* have a good rule for truncate, but floor, ceiling and  round turn  out to be awesomely slow.  {{{  main = print . sumU               . mapU (floor :: Double -> Int)               \$ enumFromToFracU 0 100000000  }}}  Runs in 1 minute, 10 seconds:  {{{  \$ time ./henning  5000000050000000  ./henning  70.25s user 0.17s system 99% cpu 1:10.99 total  }}}  Now, if we just replace that with a ccall to math.h:floor, we get:  {{{  main = print . sumU               . mapU (floor' :: Double -> Int)               \$ enumFromToFracU 0 100000000  floor' :: Double -> Int  floor' x = (truncate :: Double -> Int) (c_floor x)  {-# INLINE floor' #-}  foreign import ccall unsafe "math.h floor"      c_floor :: Double -> Double  }}}  Which runs in 1.8 seconds:  {{{  \$ time ./henning  5000000050000000  ./henning  1.88s user 0.00s system 99% cpu 1.884 total  }}}  Similar results for ceiling and round (see the main ticket for RealFrac,  http://hackage.haskell.org/trac/ghc/ticket/1434)  == Action ==  Use math.h versions of round, floor and ceiling for Double and Float? -- Ticket URL: GHC The Glasgow Haskell Compiler_______________________________________________ Glasgow-haskell-bugs mailing list [hidden email] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Open this post in threaded view
|
Report Content as Inappropriate

## Re: [GHC] #2271: floor, ceiling, round :: Double -> Int are awesomely slow

 #2271: floor, ceiling, round :: Double -> Int are awesomely slow ------------------------------------------+---------------------------------     Reporter:  dons                       |        Owner:  [hidden email]         Type:  bug                        |       Status:  new                 Priority:  normal                     |    Milestone:                    Component:  Compiler                   |      Version:  6.8.2               Severity:  normal                     |   Resolution:                     Keywords:  performance, math, double  |     Testcase:                 Architecture:  Unknown                    |           Os:  Unknown         ------------------------------------------+--------------------------------- Comment (by dons):  An old complaint:      http://article.gmane.org/gmane.comp.lang.haskell.cafe/21757/ Was due to this issue.  The original poster was complaining about:     quant8 :: Double -> Word8     quant8 x = floor \$ x * 0xFF  being too slow.  Of course, it turns into a properFraction call,  {{{  quant8_rha :: Double -> Word8  quant8_rha =    \ (x_ahf :: Double) ->      case properFraction5             @ Word8             \$f32             (case x_ahf of wild_aVL { D# x1_aVN ->              D# (*## x1_aVN 255.0)              })      of wild_aUN { (n_aUP, r_aUQ) ->      case r_aUQ of wild1_aVn { D# x1_aVp ->      case <## x1_aVp 0.0 of wild11_aUS {        False -> n_aUP;        True ->          case n_aUP of wild2_aVx { W8# x#_aVz ->          W8# (narrow8Word# (minusWord# x#_aVz __word 1))          }      }  }}}  Rather than an expected unboxed double floor(). The properFraction call  there is going to kill things. We'd need a C floor call to get something  like:  {{{  \$wccall_r182 :: Double#                  -> State# RealWorld                  -> (# State# RealWorld, Double# #)  \$wccall_r182 =    {__ccall floor Double#                 -> State# RealWorld                 -> (# State# RealWorld, Double# #)}_dRy  quant8_rha :: Double -> Word8  quant8_rha =    \ (x_ahf :: Double) ->      case x_ahf of wild_aUI { D# x1_aUK ->      case \$wccall_r182 (*## x1_aUK 255.0) realWorld#      of wild1_XB { (# ds_dRx, ds1_dRw #) ->      W8#        (narrow8Word# (int2Word# (double2Int# ds1_dRw)))      }  }}}  With the result we can turn this program:  {{{  import Data.Word  import Data.Array.Vector  main = print . sumU               . mapU (quant8 :: Double -> Word8)                            \$ enumFromToFracU 0 100000000  }}}  From running in 1 minute, 14 seconds, to one that runs in 4.1 seconds.  But note, with the pure Haskell quant, we get a fold of this form:  {{{  \$wfold :: Word# -> Double# -> Word#  }}}  While with the FFI, we get:  {{{  \$wfold :: Word# -> Double# -> Word8  }}}  Is this related to Neil's issue with FFI and unboxing results?  So, anyway, more support that the Double floor/ceiling functions need to  be turned into ccalls if we're going to use them for anything with  meaningful performance.  The full program  {{{  {-# LANGUAGE ForeignFunctionInterface #-}  import Data.Word  import Data.Array.Vector  main = print . sumU               . mapU (quant8 :: Double -> Word8)                            \$ enumFromToFracU 0 100000000  quant8 :: Double -> Word8  quant8 x = floor' \$ x * 0xFF  floor' :: Double -> Word8  floor' x = (fromIntegral . (truncate :: Double -> Int)) \$ c_floor x  foreign import ccall unsafe "math.h floor"      c_floor :: Double -> Double  }}} -- Ticket URL: GHC The Glasgow Haskell Compiler_______________________________________________ Glasgow-haskell-bugs mailing list [hidden email] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Open this post in threaded view
|
Report Content as Inappropriate

## Re: [GHC] #2271: floor, ceiling, round :: Double -> Int are awesomely slow

 In reply to this post by GHC-2 #2271: floor, ceiling, round :: Double -> Int are awesomely slow ---------------------------------------+------------------------------------  Reporter:  dons                       |          Owner:  [hidden email]      Type:  bug                        |         Status:  new              Priority:  normal                     |      Milestone:                 Component:  Compiler                   |        Version:  6.8.2            Severity:  normal                     |     Resolution:                  Keywords:  performance, math, double  |     Difficulty:  Unknown          Testcase:                             |   Architecture:  Unknown                Os:  Unknown                    |   ---------------------------------------+------------------------------------ Changes (by simonpj):   * difficulty:  => Unknown Comment:  Thanks for following this up, Don.  But can you be more specific?   * Do you have a clear idea about what exactly changes are required?  Or  are there alternatives to consider?   * Can you make concrete proposals?   * Or, if it's clear what to do, can you offer a patch?  thanks  Simon -- Ticket URL: GHC The Glasgow Haskell Compiler_______________________________________________ Glasgow-haskell-bugs mailing list [hidden email] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Open this post in threaded view
|
Report Content as Inappropriate

## Re: [GHC] #2271: floor, ceiling, round :: Double -> Int are awesomely slow

 In reply to this post by GHC-2 #2271: floor, ceiling, round :: Double -> Int are awesomely slow ---------------------------------------+------------------------------------  Reporter:  dons                       |          Owner:  [hidden email]      Type:  bug                        |         Status:  new              Priority:  normal                     |      Milestone:  6.10.1         Component:  Compiler                   |        Version:  6.8.2            Severity:  normal                     |     Resolution:                  Keywords:  performance, math, double  |     Difficulty:  Unknown          Testcase:                             |   Architecture:  Unknown                Os:  Unknown                    |   ---------------------------------------+------------------------------------ Changes (by igloo):   * milestone:  => 6.10.1 -- Ticket URL: GHC The Glasgow Haskell Compiler_______________________________________________ Glasgow-haskell-bugs mailing list [hidden email] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Open this post in threaded view
|
Report Content as Inappropriate

## Re: [GHC] #2271: floor, ceiling, round :: Double -> Int are awesomely slow

 In reply to this post by GHC-2 #2271: floor, ceiling, round :: Double -> Int are awesomely slow ---------------------------------------+------------------------------------  Reporter:  dons                       |          Owner:  [hidden email]      Type:  bug                        |         Status:  new              Priority:  normal                     |      Milestone:  6.10.1         Component:  libraries/base             |        Version:  6.8.2            Severity:  normal                     |     Resolution:                  Keywords:  performance, math, double  |     Difficulty:  Unknown          Testcase:                             |   Architecture:  Unknown                Os:  Unknown                    |   ---------------------------------------+------------------------------------ Changes (by igloo):   * component:  Compiler => libraries/base -- Ticket URL: GHC The Glasgow Haskell Compiler_______________________________________________ Glasgow-haskell-bugs mailing list [hidden email] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Open this post in threaded view
|
Report Content as Inappropriate

## Re: [GHC] #2271: floor, ceiling, round :: Double -> Int are awesomely slow

 In reply to this post by GHC-2 #2271: floor, ceiling, round :: Double -> Int are awesomely slow ---------------------------------------+------------------------------------  Reporter:  dons                       |          Owner:  [hidden email]      Type:  bug                        |         Status:  new              Priority:  normal                     |      Milestone:  6.10.2           Component:  libraries/base             |        Version:  6.8.2            Severity:  normal                     |     Resolution:                    Keywords:  performance, math, double  |     Difficulty:  Unknown          Testcase:                             |   Architecture:  Unknown/Multiple        Os:  Unknown/Multiple           |   ---------------------------------------+------------------------------------ Changes (by igloo):   * milestone:  6.10.1 => 6.10.2 -- Ticket URL: GHC The Glasgow Haskell Compiler_______________________________________________ Glasgow-haskell-bugs mailing list [hidden email] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Open this post in threaded view
|
Report Content as Inappropriate

## Re: [GHC] #2271: floor, ceiling, round :: Double -> Int are awesomely slow

 In reply to this post by GHC-2 #2271: floor, ceiling, round :: Double -> Int are awesomely slow ------------------------------------------+---------------------------------     Reporter:  dons                       |        Owner:  [hidden email]         Type:  bug                        |       Status:  new                 Priority:  normal                     |    Milestone:  6.12.1              Component:  libraries/base             |      Version:  6.8.2               Severity:  normal                     |   Resolution:                       Keywords:  performance, math, double  |   Difficulty:  Unknown             Testcase:                             |           Os:  Unknown/Multiple Architecture:  Unknown/Multiple           |   ------------------------------------------+--------------------------------- Changes (by igloo):   * milestone:  6.10.2 => 6.12.1 -- Ticket URL: GHC The Glasgow Haskell Compiler_______________________________________________ Glasgow-haskell-bugs mailing list [hidden email] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Open this post in threaded view
|
Report Content as Inappropriate

## Re: [GHC] #2271: floor, ceiling, round :: Double -> Int are awesomely slow

 In reply to this post by GHC-2 #2271: floor, ceiling, round :: Double -> Int are awesomely slow ------------------------------------------+---------------------------------     Reporter:  dons                       |        Owner:  [hidden email]         Type:  bug                        |       Status:  new                 Priority:  normal                     |    Milestone:  6.12.1              Component:  libraries/base             |      Version:  6.8.2               Severity:  normal                     |   Resolution:                       Keywords:  performance, math, double  |   Difficulty:  Unknown             Testcase:                             |           Os:  Unknown/Multiple Architecture:  Unknown/Multiple           |   ------------------------------------------+--------------------------------- Changes (by Khudyakov):  * cc: [hidden email] (added) -- Ticket URL: GHC The Glasgow Haskell Compiler_______________________________________________ Glasgow-haskell-bugs mailing list [hidden email] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs