Proposal: Faster conversion between Rational and Double/Float
Currently, the conversions between Rational and Double resp. Float are rather slow: Converting 10,000 (pseudo-random) Doubles (from an unboxed array) to Floats and summing: Range -1e308 to 1e308: - double2Float: mean: 4.343703 ms, lb 4.324399 ms, ub 4.382361 ms, ci 0.950 - uncurry encodeFloat . decodeFloat: mean: 6.449336 ms, lb 6.427503 ms, ub 6.488190 ms, ci 0.950 - fromRational . toRational: mean: 875.3696 ms, lb 874.4413 ms, ub 876.6326 ms, ci 0.950 Range -1e37 to 1e37: - double2Float: mean: 547.6073 us, lb 544.3635 us, ub 559.5245 us, ci 0.950 - uncurry encodeFloat . decodeFloat: mean: 2.754600 ms, lb 2.749209 ms, ub 2.768121 ms, ci 0.950 - fromRational . toRational: mean: 287.4107 ms, lb 286.9602 ms, ub 288.0782 ms, ci 0.950 So all conversions suffer from large/out of range values, the primop most. The conversion via fromRational . toRational takes 200 - 500 times as long (subtracting array reads and addition, it would probably be much more for the conversion itself). The conversion via the proposed new implementations of toRational and fromRational took - large range: mean: 10.89560 ms, lb 10.86049 ms, ub 10.97370 ms, ci 0.950 - small range: mean: 7.015212 ms, lb 6.993312 ms, ub 7.068088 ms, ci 0.950 It suffers much less from large/out of range values and is 40 - 80 times faster than the old (probably a little more, subtracting array reads and additions). Converting 10,000 Floats to Doubles: - float2Double: mean: 540.6598 us, lb 539.0135 us, ub 545.1019 us, ci 0.950 - uncurry encodeFloat . decodeFloat: mean: 1.886183 ms, lb 1.882036 ms, ub 1.896018 ms, ci 0.950 - fromRational . toRational: mean: 280.6127 ms, lb 280.2228 ms, ub 281.1654 ms, ci 0.950 - new implementation: mean: 5.909890 ms, lb 5.892503 ms, ub 5.961752 ms, ci 0.950 ==================================================== One of the key factors for a fast fromRational is a fast integer logarithm to base 2. Since GHC can be built with integer-gmp or integer-simple and a fast implementation requires exploiting the low-level representation of Integers, I deemed it better to add modules to those packages implementing logarithms than adding different source directories to base to choose the appropriate one based on a flag, therefore in addition to the patch to base, this proposal includes patches to integer-gmp and to integer-simple, providing some integer logarithm functions. All functions have been tested to satisfy the appropriate conditions (fromRational (toRational x) == x for x Float/Double not NaN; toRational/fromRational yield the same values as the old implementation; base ^ integerLogBase base num <= num && num < base ^ (integerLogBase base num + 1) for base > 1, num > 0), both with pseudo-random input and selected special cases. The patches have been validated against ghc-7.1.20110329 (no unexpected failures in the testsuite which aren't identical without the patches). Since I have a 32-bit system, it is conceivable that I have a glitch in the 64-bit code, I'd appreciate testing. Summary: I propose - adding modules implementing integer logarithm functions to integer-gmp and integer-simple - changing the implementation of toRational and fromRational for Double and Float using those to become significantly faster. Period of discussion: two weeks (until 14th April). Cheers, Daniel
On Thu, 31 Mar 2011, Daniel Fischer wrote:
Summary:
I propose - adding modules implementing integer logarithm functions to integer-gmp and integer-simple - changing the implementation of toRational and fromRational for Double and Float using those to become significantly faster.
Is there also a rule to, say, convert fromRational . toRational :: Double -> Double to 'id'? Sure 'id' is not quite correct because of NaNs. Maybe 'realToFrac'.
On Thursday 31 March 2011 23:34:47, Henning Thielemann wrote:
On Thu, 31 Mar 2011, Daniel Fischer wrote:
Summary:
I propose - adding modules implementing integer logarithm functions to integer-gmp and integer-simple - changing the implementation of toRational and fromRational for Double and Float using those to become significantly faster.
Is there also a rule to, say, convert fromRational . toRational :: Double -> Double to 'id'? Sure 'id' is not quite correct because of NaNs. Maybe 'realToFrac'.
There are already rules for realToFrac, but afaik, not for (fromRational . toRational). But if those rules don't fire, you get realToFrac = fromRational . toRational, which is horrible for performance (and the conversion is less truthful than id/double2Float/float2Double which you get from the rules, so you probably don't really want the standard-conforming realToFrac for these conversions, but if you get it, does it have to be so slow?).
Wow, thank you Daniel! Ian: can you validate and apply, unless anyone has an objection? Simon | -----Original Message----- | From: libraries-bounces@haskell.org [mailto:libraries-bounces@haskell.org] On | Behalf Of Daniel Fischer | Sent: 31 March 2011 20:14 | To: libraries@haskell.org | Subject: Proposal: Faster conversion between Rational and Double/Float | | Currently, the conversions between Rational and Double resp. Float are rather | slow: | | Converting 10,000 (pseudo-random) Doubles (from an unboxed array) to Floats | and summing: | | Range -1e308 to 1e308: | - double2Float: | mean: 4.343703 ms, lb 4.324399 ms, ub 4.382361 ms, ci 0.950 | - uncurry encodeFloat . decodeFloat: | mean: 6.449336 ms, lb 6.427503 ms, ub 6.488190 ms, ci 0.950 | - fromRational . toRational: | mean: 875.3696 ms, lb 874.4413 ms, ub 876.6326 ms, ci 0.950 | | Range -1e37 to 1e37: | - double2Float: | mean: 547.6073 us, lb 544.3635 us, ub 559.5245 us, ci 0.950 | - uncurry encodeFloat . decodeFloat: | mean: 2.754600 ms, lb 2.749209 ms, ub 2.768121 ms, ci 0.950 | - fromRational . toRational: | mean: 287.4107 ms, lb 286.9602 ms, ub 288.0782 ms, ci 0.950 | | So all conversions suffer from large/out of range values, the primop most. | The conversion via fromRational . toRational takes 200 - 500 times as long | (subtracting array reads and addition, it would probably be much more for the | conversion itself). | | The conversion via the proposed new implementations of toRational and | fromRational took | | - large range: | mean: 10.89560 ms, lb 10.86049 ms, ub 10.97370 ms, ci 0.950 | - small range: | mean: 7.015212 ms, lb 6.993312 ms, ub 7.068088 ms, ci 0.950 | | It suffers much less from large/out of range values and is 40 - 80 times | faster than the old (probably a little more, subtracting array reads and | additions). | | Converting 10,000 Floats to Doubles: | - float2Double: | mean: 540.6598 us, lb 539.0135 us, ub 545.1019 us, ci 0.950 | - uncurry encodeFloat . decodeFloat: | mean: 1.886183 ms, lb 1.882036 ms, ub 1.896018 ms, ci 0.950 | - fromRational . toRational: | mean: 280.6127 ms, lb 280.2228 ms, ub 281.1654 ms, ci 0.950 | - new implementation: | mean: 5.909890 ms, lb 5.892503 ms, ub 5.961752 ms, ci 0.950 | ==================================================== | | One of the key factors for a fast fromRational is a fast integer logarithm to | base 2. | Since GHC can be built with integer-gmp or integer-simple and a fast | implementation requires exploiting the low-level representation of Integers, | I deemed it better to add modules to those packages implementing logarithms | than adding different source directories to base to choose the appropriate | one based on a flag, therefore in addition to the patch to base, this | proposal includes patches to integer-gmp and to integer-simple, providing | some integer logarithm functions. | | All functions have been tested to satisfy the appropriate conditions | (fromRational (toRational x) == x for x Float/Double not NaN; | toRational/fromRational yield the same values as the old implementation; base | ^ integerLogBase base num <= num && | num < base ^ (integerLogBase base num + 1) for base > 1, num > 0), both | with pseudo-random input and selected special cases. | | The patches have been validated against ghc-7.1.20110329 (no unexpected | failures in the testsuite which aren't identical without the patches). | | Since I have a 32-bit system, it is conceivable that I have a glitch in the | 64-bit code, I'd appreciate testing. | | | Summary: | | I propose | - adding modules implementing integer logarithm functions to integer-gmp | and integer-simple | - changing the implementation of toRational and fromRational for Double and | Float using those to become significantly faster. | | Period of discussion: two weeks (until 14th April). | | Cheers, | Daniel
On Friday 01 April 2011 08:50:03, Simon Peyton-Jones wrote:
Wow, thank you Daniel!
Ian: can you validate and apply, unless anyone has an objection?
Simon
The discussion period is over, no objections were raised. The ticket is at: http://hackage.haskell.org/trac/ghc/ticket/5122 Cheers, Daniel
participants (3)
-
Daniel Fischer -
Henning Thielemann -
Simon Peyton-Jones