Re: [Haskell-cafe] Haskell performance (again)!
On 10/8/06, Udo Stenzel u.stenzel-at-web.de |haskell-cafe| ... wrote: Yang wrote: type Poly = [(Int,Int)] addPoly1 :: Poly - Poly - Poly addPoly1 p1@(p1h@(p1c,p1d):p1t) p2@(p2h@(p2c,p2d):p2t) | p1d == p2d = (p1c + p2c, p1d) : addPoly1 p1t p2t | p1d p2d = p1h : addPoly1 p1t p2 | p1d p2d = p2h : addPoly1 p1 p2t addPoly1 p1 [] = p1 addPoly1 [] p2 = p2 addPoly1 [] [] = [] But this doesn't use tail recursion/accumulation Indeed it doesn't. Now remind me, why is that supposed to be a Bad Thing? The above code exhibits a maximum of lazyness and runs with no useless space overhead. Apart from the expression (p1c + p2c), which you probably want to evaluate eagerly, it is close to perfect. so I rewrote it: [...] But laziness will cause this to occupy Theta(n)-space of cons-ing thunks. No, it doesn't. Insisting on accumulator recursion does. Actually, using reverse does. Think about it, a strict reverse cannot use less than O(n) space, either. Well, in general, the problem you run into is this, where we use linear space for the thunks: foldl (+) 0 [1,2,3] = foldl (+) (0 + 1) [2,3] = foldl (+) ((0 + 1) + 2) [3] = foldl (+) (((0 + 1) + 2) + 3) [] = ((0 + 1) + 2) + 3 = (1 + 2) + 3 = 3 + 3 = 6 whereas with strictness, you use constant space: foldl' f z [] = z foldl' f z (x:xs) = let u = f z x in u `seq` foldl' f u xs foldl' (+) 0 [1,2,3] = let u = 0 + 1 in u `seq` foldl' (+) u [2,3] = foldl' (+) 1 [2,3] = let u = 1 + 2 in u `seq` foldl' (+) u [3] = foldl' (+) 3 [3] = let u = 3 + 3 in u `seq` foldl' (+) u [] = foldl' (+) 6 [] = 6 I was hoping for more in-depth insights on how to take advantage of laziness to write cleaner AND more efficient code. Try to explain why your first iteration was bad. You'll achieve enlightenment at the point where your explanation fails. Udo. -- Hast du zum Leben kein Motiv -- steig mal vor, vielleicht geht's schief. -- aus einem Gipfelbuch -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.1 (GNU/Linux) iD8DBQFFKYwQc1ZCC9bsOpURAs4KAKCymnLiE5LfkCa01H0AJ2FddwJ6oQCfY6DY sYRPT1fGr0mUozUcs+qGC8s= =BRLQ -END PGP SIGNATURE- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell performance (again)!
I think your first try looks good. The only thing to worry about would be the + being too lazy. But that's easy to fix at the same time as improving your code in another respect. It's usually good to use real types instead of synonyms, so let's do that. data Nom = Nom Int Int type PolyNom = [Nom] ... addPoly1 p1@(p1h@(Nom p1c p1d):p1t) p2@(p2h@(Nom p2c p2d):p2t) | p1d == p2d = Nom (p1c + p2c) p1d : addPoly1 p1t p2t | p1d p2d = p1h : addPoly1 p1t p2 | p1d p2d = p2h : addPoly1 p1 p2t ... And then to make the + strict we just change the data type definition. data Nom = Nom !Int Int -- Lennart On Oct 8, 2006, at 12:58 , Yang wrote: This email actually turned out much longer than I expected, but I hope it sparks interesting (and hopefully, thorough!) discussion on points that weren't touched on by previous threads on this topic. What follows describes my journey thus far exploring what I see (as a newcomer to Haskell) as a major problem with Haskell - the ease with which users can write inefficient code, and have no idea that they did. Some of this has to do with laziness, some of it with the functional programming in general. My goal is to achieve (as a link further down says) *good* performance, not blazing performance. I.e., I want to avoid what should really be no-brainers such as little-omega(1) space utilization for simple folds. The first version of a simple program I wrote was reasonably clean. (Throughout this email, clean is supposed to mean some combination of: clear, compact, modular, elegant, etc.) It's a polynomial adder, which takes in lists of (coefficient, degree) tuples, combining terms of the same degree and maintaining a sorted order of least-to-greatest degree: type Poly = [(Int,Int)] addPoly1 :: Poly - Poly - Poly addPoly1 p1@(p1h@(p1c,p1d):p1t) p2@(p2h@(p2c,p2d):p2t) | p1d == p2d = (p1c + p2c, p1d) : addPoly1 p1t p2t | p1d p2d = p1h : addPoly1 p1t p2 | p1d p2d = p2h : addPoly1 p1 p2t addPoly1 p1 [] = p1 addPoly1 [] p2 = p2 addPoly1 [] [] = [] But this doesn't use tail recursion/accumulation (which seems to me like a complete hack that is a mandatory price to pay for using FP), so I rewrote it: addPoly :: Poly - Poly - Poly addPoly p1 p2 = let addPoly' p1@(p1h@(p1c,p1d):p1t) p2@(p2h@(p2c,p2d):p2t) result | p1d == p2d = addPoly' p1t p2t ((p1c + p2c, p1d):result) | p1d p2d = addPoly' p1 p2t (p2h:result) | p1d p2d = addPoly' p1t p2 (p1h:result) addPoly' (p1:p1s) [] result = addPoly' p1s [] (p1:result) addPoly' [] (p2:p2s) result = addPoly' [] p2s (p2:result) addPoly' [] [] result = reverse result in addPoly' p1 p2 [] But laziness will cause this to occupy Theta(n)-space of cons-ing thunks. (See appendix for a simpler example.) My third iteration will become even uglier because I will have to incorporate strictness and things like $! or seq. And there's probably a whole host of other issues that I haven't even thought of or don't know about (boxing, space leaks, etc.). From #haskell, I got a general piece of advice: Oct 07 22:37:20 CaleActually, a lot of the time, code gets messy when people optimise because they take the wrong road to optimisation Oct 07 22:37:31 Cale There are two ways to optimise a piece of Haskell code Oct 07 22:37:43 CaleYou can make it stricter, forcing evaluation to occur sooner Oct 07 22:38:01 CaleOr you can make it lazier, ensuring that things are not demanded until actually needed Oct 07 22:38:09 Korollary @wiki performance Oct 07 22:38:09 lambdabot http://www.haskell.org/haskellwiki/ performance Oct 07 22:38:13 Cale the latter route actually tends to result in cleaner code Of course, to want to learn route 2 was a no-brainer. I read through that wiki page on laziness and various other resources, but was disappointed in what I found: http://www.haskell.org/haskellwiki/Performance/Laziness only discusses the aspect of laziness where you only evaluate what you need, which by now has been repeatedly beaten into my head and sounds obvious. Aren't there other advantages to laziness? Or at least, am I not fully appreciating the obvious work-avoiding part of laziness? For instance, the example seems to allude to sharing (between the even and odd functions), which I think ties in strongly with laziness. I was hoping for more in-depth insights on how to take advantage of laziness to write cleaner AND more efficient code. (A loose analogy exists in computer architecture - the smaller the chip, the less power it can consume/the faster it can clock.) http://en.wikibooks.org/wiki/Haskell/Laziness_revisited does slightly better but still just scratches the surface - it gives an example of a clean (compact and modular) yet efficient piece of code (isSubstringOf), then completely neglects explaining it (e.g., exactly why/how does it run more efficiently?). http://users.aber.ac.uk/afc/stricthaskell.html seems to suggest that strictness
Re: [Haskell-cafe] Haskell performance (again)!
Lennart Augustsson wrote: I think your first try looks good. [snip] ... addPoly1 p1@(p1h@(Nom p1c p1d):p1t) p2@(p2h@(Nom p2c p2d):p2t) | p1d == p2d = Nom (p1c + p2c) p1d : addPoly1 p1t p2t | p1d p2d = p1h : addPoly1 p1t p2 | p1d p2d = p2h : addPoly1 p1 p2t ... The last comparison is redundant (this was in the original version too) because p1d p2d is implied (certainly for this case where p1d, p2d::Int) by the fall through from not satisfying == and so how about: addPoly1 p1@(p1h@(Nom p1c p1d):p1t) p2@(p2h@(Nom p2c p2d):p2t) | p1d == p2d = Nom (p1c + p2c) p1d : addPoly1 p1t p2t | p1d p2d = p1h : addPoly1 p1t p2 | otherwise = p2h : addPoly1 p1 p2t Regards, Brian. -- Logic empowers us and Love gives us purpose. Yet still phantoms restless for eras long past, congealed in the present in unthought forms, strive mightily unseen to destroy us. http://www.metamilk.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Haskell performance (again)!
This email actually turned out much longer than I expected, but I hope it sparks interesting (and hopefully, thorough!) discussion on points that weren't touched on by previous threads on this topic. What follows describes my journey thus far exploring what I see (as a newcomer to Haskell) as a major problem with Haskell - the ease with which users can write inefficient code, and have no idea that they did. Some of this has to do with laziness, some of it with the functional programming in general. My goal is to achieve (as a link further down says) *good* performance, not blazing performance. I.e., I want to avoid what should really be no-brainers such as little-omega(1) space utilization for simple folds. The first version of a simple program I wrote was reasonably clean. (Throughout this email, clean is supposed to mean some combination of: clear, compact, modular, elegant, etc.) It's a polynomial adder, which takes in lists of (coefficient, degree) tuples, combining terms of the same degree and maintaining a sorted order of least-to-greatest degree: type Poly = [(Int,Int)] addPoly1 :: Poly - Poly - Poly addPoly1 p1@(p1h@(p1c,p1d):p1t) p2@(p2h@(p2c,p2d):p2t) | p1d == p2d = (p1c + p2c, p1d) : addPoly1 p1t p2t | p1d p2d = p1h : addPoly1 p1t p2 | p1d p2d = p2h : addPoly1 p1 p2t addPoly1 p1 [] = p1 addPoly1 [] p2 = p2 addPoly1 [] [] = [] But this doesn't use tail recursion/accumulation (which seems to me like a complete hack that is a mandatory price to pay for using FP), so I rewrote it: addPoly :: Poly - Poly - Poly addPoly p1 p2 = let addPoly' p1@(p1h@(p1c,p1d):p1t) p2@(p2h@(p2c,p2d):p2t) result | p1d == p2d = addPoly' p1t p2t ((p1c + p2c, p1d):result) | p1d p2d = addPoly' p1 p2t (p2h:result) | p1d p2d = addPoly' p1t p2 (p1h:result) addPoly' (p1:p1s) [] result = addPoly' p1s [] (p1:result) addPoly' [] (p2:p2s) result = addPoly' [] p2s (p2:result) addPoly' [] [] result = reverse result in addPoly' p1 p2 [] But laziness will cause this to occupy Theta(n)-space of cons-ing thunks. (See appendix for a simpler example.) My third iteration will become even uglier because I will have to incorporate strictness and things like $! or seq. And there's probably a whole host of other issues that I haven't even thought of or don't know about (boxing, space leaks, etc.). From #haskell, I got a general piece of advice: Oct 07 22:37:20 CaleActually, a lot of the time, code gets messy when people optimise because they take the wrong road to optimisation Oct 07 22:37:31 CaleThere are two ways to optimise a piece of Haskell code Oct 07 22:37:43 CaleYou can make it stricter, forcing evaluation to occur sooner Oct 07 22:38:01 CaleOr you can make it lazier, ensuring that things are not demanded until actually needed Oct 07 22:38:09 Korollary @wiki performance Oct 07 22:38:09 lambdabot http://www.haskell.org/haskellwiki/performance Oct 07 22:38:13 Calethe latter route actually tends to result in cleaner code Of course, to want to learn route 2 was a no-brainer. I read through that wiki page on laziness and various other resources, but was disappointed in what I found: http://www.haskell.org/haskellwiki/Performance/Laziness only discusses the aspect of laziness where you only evaluate what you need, which by now has been repeatedly beaten into my head and sounds obvious. Aren't there other advantages to laziness? Or at least, am I not fully appreciating the obvious work-avoiding part of laziness? For instance, the example seems to allude to sharing (between the even and odd functions), which I think ties in strongly with laziness. I was hoping for more in-depth insights on how to take advantage of laziness to write cleaner AND more efficient code. (A loose analogy exists in computer architecture - the smaller the chip, the less power it can consume/the faster it can clock.) http://en.wikibooks.org/wiki/Haskell/Laziness_revisited does slightly better but still just scratches the surface - it gives an example of a clean (compact and modular) yet efficient piece of code (isSubstringOf), then completely neglects explaining it (e.g., exactly why/how does it run more efficiently?). http://users.aber.ac.uk/afc/stricthaskell.html seems to suggest that strictness is the way to go. Please say it ain't so! http://www.algorithm.com.au/mt/haskell/haskells_performance.html says that between code optimized for performance in Haskell and in another language (like O'Caml), which is more declarative, high-level, and most importantly, which one doesn't require an expert in the language to write is an unfortunate (for Haskell fans) no-brainer: The problem then is you have to know why something is slow, and there's where Haskell can get complex. Is there a space leak? (Do you even know what a space leak is?) Is your array strict instead of lazy? If it's strict, is it boxed instead of unboxed? (Do you even know what unboxing
Re: [Haskell-cafe] Haskell performance (again)!
On 10/8/06, Yang [EMAIL PROTECTED] wrote: And do most (experienced) Haskell users sacrifice cleanliness for speed, or speed for cleanliness? Keep the internals of your code--that which will be looked at a lot--fast and ugly, while the rest can be clean. If you have a function that does something very simple, but the pretty way to do it takes a second to run while the ugly way is much, much faster, use the pretty one if it's only going to be needed once or twice. It's certainly not the kind of thing you want to fold your lists with: use the ugly version for that. Also, if you want, you can write both a pretty version and an ugly version, and put the pretty version in comments while the ugly version does all the real work. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell performance (again)!
On 10/8/06, ihope [EMAIL PROTECTED] wrote: Keep the internals of your code--that which will be looked at a lot--fast and ugly, while the rest can be clean. Sorry. Meant that which will be used a lot. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell performance (again)!
On 10/8/06, ihope [EMAIL PROTECTED] wrote: On 10/8/06, Yang [EMAIL PROTECTED] wrote: And do most (experienced) Haskell users sacrifice cleanliness for speed, or speed for cleanliness? Keep the internals of your code--that which will be looked at a lot--fast and ugly, while the rest can be clean. If you have a function that does something very simple, but the pretty way to do it takes a second to run while the ugly way is much, much faster, use the pretty one if it's only going to be needed once or twice. It's certainly not the kind of thing you want to fold your lists with: use the ugly version for that. Also, if you want, you can write both a pretty version and an ugly version, and put the pretty version in comments while the ugly version does all the real work. Another good idea when you have a pretty version which is easy to verify for correctness and an ugly version that is harder to verify is to use QuickCheck or SmallCheck and define a property that says both versions are equal for all inputs. Ugly code is notorious for holding bugs, but doing this would help test the ugly code. Jason ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell performance (again)!
On Sun, 2006-10-08 at 15:25 -0700, Jason Dagit wrote: Another good idea when you have a pretty version which is easy to verify for correctness and an ugly version that is harder to verify is to use QuickCheck or SmallCheck and define a property that says both versions are equal for all inputs. Ugly code is notorious for holding bugs, but doing this would help test the ugly code. This is exactly how we tested Data.ByteString and to great effect I think. We uncovered loads of bugs during testing. The few bugs uncovered by our users since it has been released have invariably been in things we didn't have QC properties for. Duncan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell performance (again)!
duncan.coutts: On Sun, 2006-10-08 at 15:25 -0700, Jason Dagit wrote: Another good idea when you have a pretty version which is easy to verify for correctness and an ugly version that is harder to verify is to use QuickCheck or SmallCheck and define a property that says both versions are equal for all inputs. Ugly code is notorious for holding bugs, but doing this would help test the ugly code. This is exactly how we tested Data.ByteString and to great effect I think. We uncovered loads of bugs during testing. The few bugs uncovered by our users since it has been released have invariably been in things we didn't have QC properties for. Yes, I agree with this. By checking fast-bug-ugly code against slow-but-obvious code, we were able to catch bugs before Data.ByteString was deployed in the outside world, and before the bugs could hurt anyone. These days, Data.ByteString has some 2000 lines of QC properties, which are run on ever darcs commit. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell performance (again)!
Yang wrote: type Poly = [(Int,Int)] addPoly1 :: Poly - Poly - Poly addPoly1 p1@(p1h@(p1c,p1d):p1t) p2@(p2h@(p2c,p2d):p2t) | p1d == p2d = (p1c + p2c, p1d) : addPoly1 p1t p2t | p1d p2d = p1h : addPoly1 p1t p2 | p1d p2d = p2h : addPoly1 p1 p2t addPoly1 p1 [] = p1 addPoly1 [] p2 = p2 addPoly1 [] [] = [] But this doesn't use tail recursion/accumulation Indeed it doesn't. Now remind me, why is that supposed to be a Bad Thing? The above code exhibits a maximum of lazyness and runs with no useless space overhead. Apart from the expression (p1c + p2c), which you probably want to evaluate eagerly, it is close to perfect. so I rewrote it: [...] But laziness will cause this to occupy Theta(n)-space of cons-ing thunks. No, it doesn't. Insisting on accumulator recursion does. Actually, using reverse does. Think about it, a strict reverse cannot use less than O(n) space, either. I was hoping for more in-depth insights on how to take advantage of laziness to write cleaner AND more efficient code. Try to explain why your first iteration was bad. You'll achieve enlightenment at the point where your explanation fails. Udo. -- Hast du zum Leben kein Motiv -- steig mal vor, vielleicht geht's schief. -- aus einem Gipfelbuch signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
