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