[Haskell-cafe] More on performance

[Duncan Coutts]

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