No subject
Sun Oct 23 10:51:38 CEST 2011
overflow" error on runtime...
L.
On Mon, Jun 25, 2012 at 10:09 AM, Dmitry Olshansky <olshanskydr at gmail.com>wrote:
> 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
>>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
--90e6ba6153a0e75fa004c348acfe
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
I wonder why this performs really badly, though (I would expect it to be th=
e same as s2):<div><br><div><div>s3 :: Int -> Int</div><div>s3 n =3D sum=
[gcd x y | x <- [ 0 .. n-1 ], y <- [ 0 .. n-1 ]]</div><div><br></div=
>
<div>From the links posted by Dmitry, it might be that the code generated i=
s made of 2 recursive calls: in fact, what I observe is a "stack space=
overflow" error on runtime...</div><div><br></div><div>L.</div><div>
<br></div><div><br></div><div><br></div><br><div class=3D"gmail_quote">On M=
on, Jun 25, 2012 at 10:09 AM, Dmitry Olshansky <span dir=3D"ltr"><<a hre=
f=3D"mailto:olshanskydr at gmail.com" target=3D"_blank">olshanskydr at gmail.com<=
/a>></span> wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex">s1 ~=C2=A0sum $ map (sum . flip map [0..n] .=
gcd) [0..n]<div><div>s2 ~=C2=A0sum $ concatMap (flip map [0..n] . gcd) [0.=
.n]=C2=A0</div>
<div><br></div><div>There are some posts from=C2=A0<span style=3D"font-size=
:medium;font-family:'Times New Roman'">Joachim Breitner investigate=
d fusion for concatMap:</span></div>
<div><a href=3D"http://www.haskell.org/pipermail/haskell-cafe/2011-December=
/thread.html#97227" target=3D"_blank">http://www.haskell.org/pipermail/hask=
ell-cafe/2011-December/thread.html#97227</a></div><div><div class=3D"h5"><d=
iv>
<br></div><div><br></div><div><div><br>
<div class=3D"gmail_quote">2012/6/25 Johannes Waldmann <span dir=3D"ltr">&l=
t;<a href=3D"mailto:waldmann at imn.htwk-leipzig.de" target=3D"_blank">waldman=
n at imn.htwk-leipzig.de</a>></span><br><blockquote class=3D"gmail_quote" s=
tyle=3D"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 =C2=A0s1 =C2=A0is considerably faster than =C2=A0s2=
<br>
(but I wanted =C2=A0s2 =C2=A0because it looks more natural)<br>
(for n =3D 10000, =C2=A0s1 takes 20 s, s2 takes 13 s; compiled by ghc-7.4.2=
-O2)<br>
<br>
s1 :: Int -> Int<br>
s1 n =3D sum $ do<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0x <- [ 0 .. n-1 ]<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0return $ sum $ do<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0y <- [ 0 .. n-1 ]<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0return $ gcd x y<br>
<br>
s2 :: Int -> Int<br>
s2 n =3D sum $ do<br>
=C2=A0 =C2=A0 =C2=A0x <- [ 0 .. n-1 ]<br>
=C2=A0 =C2=A0 =C2=A0y <- [ 0 .. n-1 ]<br>
=C2=A0 =C2=A0 =C2=A0return $ 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 =C2=A0ghc =C2=A0turn the tail recursion (in gcd) into a loop? (gcc doe=
s).<br>
(I am looking at =C2=A0-ddump-asm =C2=A0but can't quite see through it.=
)<br>
<br>
<br>
(*) benchmarking to show that today'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=3D"mailto:Haskell-Cafe at haskell.org" target=3D"_blank">Haskell-Cafe@=
haskell.org</a><br>
<a href=3D"http://www.haskell.org/mailman/listinfo/haskell-cafe" target=3D"=
_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=3D"mailto:Haskell-Cafe at haskell.org">Haskell-Cafe at haskell.org</a><br=
>
<a href=3D"http://www.haskell.org/mailman/listinfo/haskell-cafe" target=3D"=
_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
<br></blockquote></div><br></div></div>
--90e6ba6153a0e75fa004c348acfe--
More information about the Haskell-Cafe
mailing list