Quantcast

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

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

GHC-2
#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: <http://hackage.haskell.org/trac/ghc/ticket/2271>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

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  |     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: <http://hackage.haskell.org/trac/ghc/ticket/2271#comment:1>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

GHC-2
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: <http://hackage.haskell.org/trac/ghc/ticket/2271#comment:2>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

GHC-2
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: <http://hackage.haskell.org/trac/ghc/ticket/2271#comment:3>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

GHC-2
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: <http://hackage.haskell.org/trac/ghc/ticket/2271#comment:4>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

GHC-2
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: <http://hackage.haskell.org/trac/ghc/ticket/2271#comment:7>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

GHC-2
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: <http://hackage.haskell.org/trac/ghc/ticket/2271#comment:8>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

GHC-2
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: <http://hackage.haskell.org/trac/ghc/ticket/2271#comment:9>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

GHC-2
In reply to this post by GHC-2
#2271: floor, ceiling, round :: Double -> Int are awesomely slow
-----------------------------+----------------------------------------------
  Reporter:  dons            |          Owner:                          
      Type:  bug             |         Status:  new                      
  Priority:  normal          |      Milestone:  6.12 branch              
 Component:  libraries/base  |        Version:  6.8.2                    
Resolution:                  |       Keywords:  performance, math, double
Difficulty:  Unknown         |             Os:  Unknown/Multiple        
  Testcase:                  |   Architecture:  Unknown/Multiple        
   Failure:  None/Unknown    |  
-----------------------------+----------------------------------------------
Changes (by igloo):

  * owner:  [hidden email] =>
  * failure:  => None/Unknown
  * milestone:  6.12.1 => 6.12 branch

--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/2271#comment:10>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Loading...