On Wed, 2008-06-04 at 09:32 +0200, Henning Thielemann wrote:
On Tue, 3 Jun 2008, Don Stewart wrote:
I wrote up the second part of the tour of understanding low level performance in GHC here,
http://reddit.com/r/programming/info/6lx36/comments/
Follows on from the discussion last week about various performance related things.
Now the difficult question: How to write the 'mean' function in terms of 'sum' and 'length' while getting the same performance?
There's another rather harder fusion transformation that notices when two left folds are demanded in the same strictness context and they fold over the same input list then they can be performed together. sum = foldl (\s x -> s + x) 0 length = foldl (\l x -> l + 1) 0 mean xs = sum xs / length xs So we must note that sum and length are demanded at the same time and since they are both foldl's will consume the whole of xs. So we can merge the two foldl's into one just by tupling them up: sumlength = foldl (\(s, l) x -> (s + x, l + 1)) (0, 0) mean xs = s / l where (s, l) = sumlength xs The Fortran people have been doing this kind of loop fusion for some years. What makes it a bit harder for us is that we cannot do it with rules because it's not a simple local transformation. It could probably be done with a special compiler pass, though it'd need strictness analysis to be done much earlier. Duncan