You are right, probably I didn&#39;t because I cannot reproduce it now.<div>Sorry for the noise.</div><div>(Anyway, I am still surprised that list-comprehension gives a different result from do-notation in the list monad.)</div>
<div><br></div><div>L.</div><div><br></div><div><br></div><div><br><div class="gmail_quote">On Mon, Jun 25, 2012 at 11:55 AM, Dmitry Olshansky <span dir="ltr">&lt;<a href="mailto:olshanskydr@gmail.com" target="_blank">olshanskydr@gmail.com</a>&gt;</span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">In my test it works ~20% faster than s2 and ~20% slower than s1.<div>Did you use -O2 flag?<div><div class="h5"><br><br>
<div class="gmail_quote">2012/6/25 Lorenzo Bolla <span dir="ltr">&lt;<a href="mailto:lbolla@gmail.com" target="_blank">lbolla@gmail.com</a>&gt;</span><br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">I wonder why this performs really badly, though (I would expect it to be the same as s2):<div><br><div><div>s3 :: Int -&gt; Int</div>

<div>s3 n = sum [gcd x y | x &lt;- [ 0 .. n-1 ], y &lt;- [ 0 .. n-1 ]]</div><div><br></div>
<div>From the links posted by Dmitry, it might be that the code generated is made of 2 recursive calls: in fact, what I observe is a &quot;stack space overflow&quot; error on runtime...</div><span><font color="#888888"><div>

<br></div><div>L.</div></font></span><div><div><div>
<br></div><div><br></div><div><br></div><br><div class="gmail_quote">On Mon, Jun 25, 2012 at 10:09 AM, Dmitry Olshansky <span dir="ltr">&lt;<a href="mailto:olshanskydr@gmail.com" target="_blank">olshanskydr@gmail.com</a>&gt;</span> wrote:<br>


<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">s1 ~ sum $ map (sum . flip map [0..n] . gcd) [0..n]<div><div>s2 ~ sum $ concatMap (flip map [0..n] . gcd) [0..n] </div>


<div><br></div><div>There are some posts from <span style="font-size:medium;font-family:&#39;Times New Roman&#39;">Joachim Breitner investigated fusion for concatMap:</span></div>
<div><a href="http://www.haskell.org/pipermail/haskell-cafe/2011-December/thread.html#97227" target="_blank">http://www.haskell.org/pipermail/haskell-cafe/2011-December/thread.html#97227</a></div><div><div><div>
<br></div><div><br></div><div><div><br>
<div class="gmail_quote">2012/6/25 Johannes Waldmann <span dir="ltr">&lt;<a href="mailto:waldmann@imn.htwk-leipzig.de" target="_blank">waldmann@imn.htwk-leipzig.de</a>&gt;</span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">



Dear all,<br>
<br>
while doing some benchmarking (*)<br>
I noticed that function  s1  is considerably faster than  s2<br>
(but I wanted  s2  because it looks more natural)<br>
(for n = 10000,  s1 takes 20 s, s2 takes 13 s; compiled by ghc-7.4.2 -O2)<br>
<br>
s1 :: Int -&gt; Int<br>
s1 n = sum $ do<br>
        x &lt;- [ 0 .. n-1 ]<br>
        return $ sum $ do<br>
            y &lt;- [ 0 .. n-1 ]<br>
            return $ gcd x y<br>
<br>
s2 :: Int -&gt; Int<br>
s2 n = sum $ do<br>
      x &lt;- [ 0 .. n-1 ]<br>
      y &lt;- [ 0 .. n-1 ]<br>
      return $ gcd x y<br>
<br>
I was expecting that in both programs,<br>
all lists will be fused away (are they?)<br>
so the code generator essentially can produce straightforward<br>
assembly code (no allocations, no closures, etc.)<br>
<br>
<br>
For reference, I also wrote the equivalent imperative program<br>
(two nested loops, one accumulator for the sum)<br>
(with the straightforward recursive gcd)<br>
and runtimes are (for same input as above)<br>
<br>
C/gcc: 7.3 s , Java: 7.7 s, C#/Mono: 8.7 s<br>
<br>
<br>
So, they sort of agree with each other, but disagree with ghc.<br>
Where does the factor 2 come from? Lists? Laziness?<br>
Does  ghc  turn the tail recursion (in gcd) into a loop? (gcc does).<br>
(I am looking at  -ddump-asm  but can&#39;t quite see through it.)<br>
<br>
<br>
(*) benchmarking to show that today&#39;s compilers are clever enough<br>
such that the choice of paradigm/language does not really matter<br>
for this kind of low-level programming.<br>
<br>
<br>
<br>
<br>
<br>
<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
</blockquote></div><br></div></div></div></div></div>
<br>_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
<br></blockquote></div><br></div></div></div></div>
</blockquote></div><br></div></div></div>
</blockquote></div><br></div>