Proposal: Faster toRational and fromRational
trac: http://hackage.haskell.org/trac/ghc/ticket/4344#comment:10 Proposal: include faster implementations for 1. toRational :: Float -> Rational 2. toRational :: Double -> Rational 3. fromRational :: Rational -> Float 4. fromRational :: Rational -> Double The semantics of these functions shall remain the same as it is now, only their speed will be affected. For fromRational, a fast integer logarithm is essential. Without access to the internal representation of Integer, it would be significantly slower, so this proposal includes the addition of modules defining the needed integer logarithm functions to the packages integer-gmp and integer-simple. Since Int is not available in the integer-* packages, those functions would return Int# values. I suggest adding wrappers integerLog2 :: Integer -> Int and integerLogBase :: Integer -> Integer -> Int to some module in base because those functions are far more generally useful. Currently integerLogBase is available from GHC.Float, so we might stick them there, although it's not very intuitive. Suggestions welcome. Discussion period: one week, until 29th October 2010 (I'd like to see it in 7.0). At http://hackage.haskell.org/trac/ghc/attachment/ticket/4344/FloatingRationalC... there's a bundle containing the proposed new implementations, QuickCheck tests and benchmarks. I get a pretty impressive speedup. Cheers, Daniel
On 10/21/10 15:35, Daniel Fischer wrote:
trac: http://hackage.haskell.org/trac/ghc/ticket/4344#comment:10
Proposal: include faster implementations for
1. toRational :: Float -> Rational 2. toRational :: Double -> Rational 3. fromRational :: Rational -> Float 4. fromRational :: Rational -> Double
The semantics of these functions shall remain the same as it is now, only their speed will be affected.
I generally approve! If the libraries list has any non-trivial doubts then it might be best not to squeeze it into 7.0. But if not, then great!(IMHO) Do we, the Libraries list, need to approve adding ( integerLog2# :: Integer -> Int# ) to the integer-* packages? I had the notion those are relatively private packages that GHC developers have purview over. (Then we could think separately from this proposal about adding a user-friendly integerLog2 to somewhere nice; and then I'd wish for a log2 for types like Int as well; maybe it would make sense for Data.Bits; questions like that. I would be supportive but I don't think we have to do this before we optimize Rational.) -Isaac
On Friday 22 October 2010 02:50:41, Isaac Dupree wrote:
On 10/21/10 15:35, Daniel Fischer wrote:
trac: http://hackage.haskell.org/trac/ghc/ticket/4344#comment:10
Proposal: include faster implementations for
1. toRational :: Float -> Rational 2. toRational :: Double -> Rational 3. fromRational :: Rational -> Float 4. fromRational :: Rational -> Double
The semantics of these functions shall remain the same as it is now, only their speed will be affected.
I generally approve! If the libraries list has any non-trivial doubts then it might be best not to squeeze it into 7.0. But if not, then great!(IMHO)
Do we, the Libraries list, need to approve adding ( integerLog2# :: Integer -> Int# ) to the integer-* packages? I had the notion those are relatively private packages that GHC developers have purview over.
Well, I don't know. I'm not quite clear on which libraries concern libraries@ and which not, so I rather ask too often than too rarely (and then get told "No, can't do that").
(Then we could think separately from this proposal about adding a user-friendly integerLog2 to somewhere nice; and then I'd wish for a log2 for types like Int as well; maybe it would make sense for Data.Bits; questions like that. I would be supportive but I don't think we have to do this before we optimize Rational.)
I have also wordLog2# :: Word# -> Int#, that would cover also Int arguments (and WordN, IntN for N <= WORD_SIZE_IN_BITS, but the smaller types would profit from special implementations as the high bits are checked first; those would be easy to add).
-Isaac
Daniel Thank you for doing this stuff on improving Haskell numerics. My impression is that good numerics requires both expertise (to get the details right) and sweat (to get the details right), and you seem willing to bring both to the table. Thank you. Simon | -----Original Message----- | From: libraries-bounces@haskell.org [mailto:libraries-bounces@haskell.org] On Behalf | Of Daniel Fischer | Sent: 21 October 2010 20:36 | To: libraries@haskell.org | Subject: Proposal: Faster toRational and fromRational | | trac: http://hackage.haskell.org/trac/ghc/ticket/4344#comment:10 | | Proposal: include faster implementations for | | 1. toRational :: Float -> Rational | 2. toRational :: Double -> Rational | 3. fromRational :: Rational -> Float | 4. fromRational :: Rational -> Double | | The semantics of these functions shall remain the same as it is now, only | their speed will be affected. | | For fromRational, a fast integer logarithm is essential. Without access to | the internal representation of Integer, it would be significantly slower, | so this proposal includes the addition of modules defining the needed | integer logarithm functions to the packages integer-gmp and integer-simple. | | Since Int is not available in the integer-* packages, those functions would | return Int# values. I suggest adding wrappers integerLog2 :: Integer -> Int | and integerLogBase :: Integer -> Integer -> Int to some module in base | because those functions are far more generally useful. Currently | integerLogBase is available from GHC.Float, so we might stick them there, | although it's not very intuitive. Suggestions welcome. | | Discussion period: one week, until 29th October 2010 (I'd like to see it in | 7.0). | | At | http://hackage.haskell.org/trac/ghc/attachment/ticket/4344/FloatingRationalC... | s.tar.gz | there's a bundle containing the proposed new implementations, QuickCheck | tests and benchmarks. | I get a pretty impressive speedup. | | Cheers, | Daniel | _______________________________________________ | Libraries mailing list | Libraries@haskell.org | http://www.haskell.org/mailman/listinfo/libraries
Yes, a big thanks to Daniel. The code used at the moment was meant as
a reference implementation and needs a lot of improvement.
On Fri, Oct 22, 2010 at 8:31 AM, Simon Peyton-Jones
Daniel
Thank you for doing this stuff on improving Haskell numerics. My impression is that good numerics requires both expertise (to get the details right) and sweat (to get the details right), and you seem willing to bring both to the table. Thank you.
Simon
| -----Original Message----- | From: libraries-bounces@haskell.org [mailto:libraries-bounces@haskell.org] On Behalf | Of Daniel Fischer | Sent: 21 October 2010 20:36 | To: libraries@haskell.org | Subject: Proposal: Faster toRational and fromRational | | trac: http://hackage.haskell.org/trac/ghc/ticket/4344#comment:10 | | Proposal: include faster implementations for | | 1. toRational :: Float -> Rational | 2. toRational :: Double -> Rational | 3. fromRational :: Rational -> Float | 4. fromRational :: Rational -> Double | | The semantics of these functions shall remain the same as it is now, only | their speed will be affected. | | For fromRational, a fast integer logarithm is essential. Without access to | the internal representation of Integer, it would be significantly slower, | so this proposal includes the addition of modules defining the needed | integer logarithm functions to the packages integer-gmp and integer-simple. | | Since Int is not available in the integer-* packages, those functions would | return Int# values. I suggest adding wrappers integerLog2 :: Integer -> Int | and integerLogBase :: Integer -> Integer -> Int to some module in base | because those functions are far more generally useful. Currently | integerLogBase is available from GHC.Float, so we might stick them there, | although it's not very intuitive. Suggestions welcome. | | Discussion period: one week, until 29th October 2010 (I'd like to see it in | 7.0). | | At | http://hackage.haskell.org/trac/ghc/attachment/ticket/4344/FloatingRationalC... | s.tar.gz | there's a bundle containing the proposed new implementations, QuickCheck | tests and benchmarks. | I get a pretty impressive speedup. | | Cheers, | Daniel | _______________________________________________ | Libraries mailing list | Libraries@haskell.org | http://www.haskell.org/mailman/listinfo/libraries
_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries
On Friday 22 October 2010 10:04:47, Lennart Augustsson wrote:
The code used at the moment was meant as a reference implementation
And it serves that purpose well.
and needs a lot of improvement.
Which reminds me of the fact that fromRat is reexported from Numeric. My code is strictly for floatRadix 2, so it can't serve as the fromRat implementation which has to allow other floatRadices. I see two possibilities, - the simpler is to just bind fromRat to fromRational in Numeric, - the other is to incorporate as many of the improvements into fromRat as possible. The latter would lead to further bloat in GHC.Float, since it would contain two implementations of essentially the same function, one general and one specialised. Is there any reason not to follow the simpler route?
On Thu, Oct 21, 2010 at 09:35:30PM +0200, Daniel Fischer wrote:
Discussion period: one week, until 29th October 2010 (I'd like to see it in 7.0).
I don't think that's a good reason for an abnormally short discussion period. In general, the more patches we push into the 7.0 branch, the greater the chance we regress, which means either longer until we can release it (if we spot it in time), lots of extra effort to put out another release (if we don't), or having to live with the regression for a few months (if we don't think it's worth putting in the effort to quickly do another release). And the probability of a patch causing a regression is higher if the process is rushed. It's great to see work on improving performance of the libraries, but after we've started putting out release candidates is not the best time to be doing it if you want the changes to get into that release. Thanks Ian
On Sat, Oct 23, 2010 at 12:00:45AM +0100, Ian Lynagh wrote:
It's great to see work on improving performance of the libraries, but after we've started putting out release candidates is not the best time to be doing it if you want the changes to get into that release.
I always thought the cutoff was when you forked off a new stable branch.
On Sat, Oct 23, 2010 at 9:08 AM, Ross Paterson
On Sat, Oct 23, 2010 at 12:00:45AM +0100, Ian Lynagh wrote:
It's great to see work on improving performance of the libraries, but after we've started putting out release candidates is not the best time to be doing it if you want the changes to get into that release.
I always thought the cutoff was when you forked off a new stable branch.
I think that's this: http://darcs.haskell.org/ghc-7.0/ At least, that's what I made my last build from. Antoine
On Saturday 23 October 2010 01:00:45, Ian Lynagh wrote:
On Thu, Oct 21, 2010 at 09:35:30PM +0200, Daniel Fischer wrote:
Discussion period: one week, until 29th October 2010 (I'd like to see it in 7.0).
I don't think that's a good reason for an abnormally short discussion period.
In general, the more patches we push into the 7.0 branch, the greater the chance we regress, which means either longer until we can release it (if we spot it in time), lots of extra effort to put out another release (if we don't), or having to live with the regression for a few months (if we don't think it's worth putting in the effort to quickly do another release). And the probability of a patch causing a regression is higher if the process is rushed.
Well, my idea was to get a quick conclusion so there might be enough time for testing for the change to have a fighting chance to get in.
It's great to see work on improving performance of the libraries, but after we've started putting out release candidates is not the best time to be doing it if you want the changes to get into that release.
I had never looked at the standard libraries' code before to see whether I could improve it because I didn't expect I could. I only stumbled across the first thing a few days before the release candidate came out. Then I started looking and found a couple more, I'd just like the major things to be available as soon as possible. If they don't make it because HQ has not enough time to test and verify, okay, bad luck.
Thanks Ian
Cheers, Daniel
participants (7)
-
Antoine Latter -
Daniel Fischer -
Ian Lynagh -
Isaac Dupree -
Lennart Augustsson -
Ross Paterson -
Simon Peyton-Jones