[Haskell-cafe] not enough fusion?

[Duncan Coutts]

On 25 June 2012 02:04, Johannes Waldmann <waldmann at imn.htwk-leipzig.de> wrote:
> Dear all,
>
> while doing some benchmarking (*)
> I noticed that function  s1  is considerably faster than  s2
> (but I wanted  s2  because it looks more natural)
> (for n = 10000,  s1 takes 20 s, s2 takes 13 s; compiled by ghc-7.4.2 -O2)
>
> s1 :: Int -> Int
> s1 n = sum $ do
>        x <- [ 0 .. n-1 ]
>        return $ sum $ do
>            y <- [ 0 .. n-1 ]
>            return $ gcd x y
>
> s2 :: Int -> Int
> s2 n = sum $ do
>      x <- [ 0 .. n-1 ]
>      y <- [ 0 .. n-1 ]
>      return $ gcd x y
>
> I was expecting that in both programs,
> all lists will be fused away (are they?)

Almost certainly not.

> so the code generator essentially can produce straightforward
> assembly code (no allocations, no closures, etc.)

Unless it changed recently, sum does not fuse (as it is currently
defined, using the current implementation of foldr/build fusion).
Also, lists built using do notation do not (I think) translate into
instances of foldr and build, only list comprehension syntax.

On the first point: sum is a foldl and the current implementation of
foldr/build fusion does not cope well with foldl. While foldl can be
defined in terms of foldr the result is lots of closure allocations.
This could in principle be fixed with an arity raising transformation,
and GHC now does have a simple implementation of this transformation,
so it may be possible to get sum as a foldl to fuse. I'm not sure that
anyone has yet tried changing the sum implementation to try to get it
to fuse. It would be an interesting experiment.

On the second point: ghc has a special desugaring for list
comprehensions (in -O mode) where it turns them into uses of foldr and
build. On the other hand, do notation desugars into bind and return.
I'm not sure how well the result fuses, it uses: foldr ((++) . k) [].

You can find out, just look at the core. If all goes well then you
should see a single list being built and then consumed by sum.

Duncan