
On 25 June 2012 02:04, Johannes Waldmann
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