Haskell › Haskell - Glasgow-haskell-bugs

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

Classic

List

Threaded

9 messages Options

GHC-2

[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: <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

GHC-2

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: <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

GHC-2