Proposal: Faster conversion between Rational and Double/Float

[Simon Peyton-Jones]

Wow, thank you Daniel!

Ian: can you validate and apply, unless anyone has an objection?

Simon

| -----Original Message-----
| From: libraries-bounces at haskell.org [mailto:libraries-bounces at haskell.org] On
| Behalf Of Daniel Fischer
| Sent: 31 March 2011 20:14
| To: libraries at 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