[Haskell-cafe] not enough fusion?

[Dmitry Olshansky]

s1 ~ sum $ map (sum . flip map [0..n] . gcd) [0..n]
s2 ~ sum $ concatMap (flip map [0..n] . gcd) [0..n]

There are some posts from Joachim Breitner investigated fusion for
concatMap:
http://www.haskell.org/pipermail/haskell-cafe/2011-December/thread.html#97227



2012/6/25 Johannes Waldmann <waldmann at imn.htwk-leipzig.de>

> 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?)
> so the code generator essentially can produce straightforward
> assembly code (no allocations, no closures, etc.)
>
>
> For reference, I also wrote the equivalent imperative program
> (two nested loops, one accumulator for the sum)
> (with the straightforward recursive gcd)
> and runtimes are (for same input as above)
>
> C/gcc: 7.3 s , Java: 7.7 s, C#/Mono: 8.7 s
>
>
> So, they sort of agree with each other, but disagree with ghc.
> Where does the factor 2 come from? Lists? Laziness?
> Does  ghc  turn the tail recursion (in gcd) into a loop? (gcc does).
> (I am looking at  -ddump-asm  but can't quite see through it.)
>
>
> (*) benchmarking to show that today's compilers are clever enough
> such that the choice of paradigm/language does not really matter
> for this kind of low-level programming.
>
>
>
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120625/d895b646/attachment.htm>