[Haskell-cafe] Write Haskell as fast as C. [Was: Re: GHC
dons at galois.com
Thu May 15 14:31:32 EDT 2008
> I offer up the following example:
> mean xs = sum xs / length xs
> Now try, say, "mean [1.. 1e9]", and watch GHC eat several GB of RAM. (!!)
> If we now rearrange this to
> mean = (\(s,n) -> s / n) . foldr (\x (s,n) -> let s' = s+x; n' = n+1
> in s' `seq` n' `seq` (s', n')) (0,0)
> and run the same example, and watch it run in constant space.
> Of course, the first version is clearly readable, while the second one
> is almost utterly incomprehensible, especially to a beginner. (It's even
> more fun that you need all those seq calls in there to make it work
> The sad fact is that if you just write something in Haskell in a nice,
> declarative style, then roughly 20% of the time you get good
> performance, and 80% of the time you get laughably poor performance.
I've written an extended post on how to understand and reliably optimise
code like this, looking at it all the way down to the assembly.
The result are some simple rules to follow for generated code as good
as gcc -O2.
More information about the Haskell-Cafe