<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
p
{mso-style-priority:99;
mso-margin-top-alt:auto;
margin-right:0cm;
mso-margin-bottom-alt:auto;
margin-left:0cm;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
p.Code, li.Code, div.Code
{mso-style-name:Code;
margin-top:0cm;
margin-right:0cm;
margin-bottom:0cm;
margin-left:36.0pt;
margin-bottom:.0001pt;
font-size:9.0pt;
font-family:"Courier New";}
p.msonormal0, li.msonormal0, div.msonormal0
{mso-style-name:msonormal;
mso-margin-top-alt:auto;
margin-right:0cm;
mso-margin-bottom-alt:auto;
margin-left:0cm;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
span.EmailStyle20
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;
font-weight:normal;
font-style:normal;
text-decoration:none none;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;
mso-fareast-language:EN-US;}
.MsoPapDefault
{mso-style-type:export-only;
margin-top:6.0pt;
margin-right:0cm;
margin-bottom:6.0pt;
margin-left:0cm;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-GB" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal"><span style="font-family:"Calibri",sans-serif;mso-fareast-language:EN-US">As Harendra has found, the biggest difference is probably that the IO version is necessarily strict, constructing the entire list (via the stack) before it returns,
whereas the pure one is lazy, constructing the list only on demand. So the memory footprint of the lazy one will be asymptotically smaller (constant instead of linear in the list size).<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Calibri",sans-serif;mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Calibri",sans-serif;mso-fareast-language:EN-US">Simon<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Calibri",sans-serif;mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<div style="border:none;border-left:solid blue 1.5pt;padding:0cm 0cm 0cm 4.0pt">
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal"><b><span lang="EN-US" style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span lang="EN-US" style="font-size:11.0pt;font-family:"Calibri",sans-serif"> Glasgow-haskell-users [mailto:glasgow-haskell-users-bounces@haskell.org]
<b>On Behalf Of </b>Harendra Kumar<br>
<b>Sent:</b> 14 May 2016 22:18<br>
<b>To:</b> David Feuer <david.feuer@gmail.com><br>
<b>Cc:</b> GHC users <glasgow-haskell-users@haskell.org><br>
<b>Subject:</b> Re: suboptimal ghc code generation in IO vs equivalent pure code case<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
I have stared at the cmm and assembly quite a bit. Indeed there is no trace of a token in cmm and assembly as expected. Here is what is happening.<o:p></o:p></p>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
In the IO case the entire original list is evaluated and unfolded on the stack first. During the recursion, the stack will have as many closure pointers as the size of the list, last element of the list being on top of the stack. When we finish recursing the
original list, the stack unwinds and we start creating the closures for the new list in the reverse order. This is all pretty evident from the cmm dump output.<o:p></o:p></p>
</div>
<div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
This process retains a lot of heap and stack memory (proportional to the size of the list) which will require the GC to do a lot of walking, fixing and copying. I guess that's where the additional cost is coming from. When the list size increases this cost
increases nonlinearly. That explains why at lower list sizes the IO version performs not just equal to but a tad better than the pure version because if GC overhead is not considered this code is in fact more efficient.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
-harendra<o:p></o:p></p>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
On 15 May 2016 at 01:56, David Feuer <<a href="mailto:david.feuer@gmail.com" target="_blank">david.feuer@gmail.com</a>> wrote:<o:p></o:p></p>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<p>The state token is zero-width and should therefore be erased altogether in code generation.<o:p></o:p></p>
<div>
<div>
<div>
<p class="MsoNormal">On May 14, 2016 4:21 PM, "Tyson Whitehead" <<a href="mailto:twhitehead@gmail.com" target="_blank">twhitehead@gmail.com</a>> wrote:<o:p></o:p></p>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<p class="MsoNormal">On 14/05/16 02:31 PM, Harendra Kumar wrote:<o:p></o:p></p>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<p class="MsoNormal">The difference seems to be entirely due to memory pressure. At list size 1000 both pure version and IO version perform equally. But as the size of the list increases the pure version scales linearly while the IO version degrades exponentially.
Here are the execution times per list element in ns as the list size increases:<br>
<br>
Size of list Pure IO<br>
1000 8.7 8.3<br>
10000 8.7 18<br>
100000 8.8 63<br>
1000000 9.3 786<br>
<br>
This seems to be due to increased GC activity in the IO case. The GC stats for list size 1 million are:<br>
<br>
IO case: %GC time 66.1% (61.1% elapsed)<br>
Pure case: %GC time 2.6% (3.3% elapsed)<br>
<br>
Not sure if there is a way to write this code in IO monad which can reduce this overhead.<o:p></o:p></p>
</blockquote>
<p class="MsoNormal"><br>
Something to be aware of is that GHC currently can't pass multiple return values in registers (that may not be a 100% accurate statement, but a reasonable high level summary, see ticket for details)<br>
<br>
<a href="https://ghc.haskell.org/trac/ghc/ticket/2289" target="_blank">https://ghc.haskell.org/trac/ghc/ticket/2289</a><br>
<br>
This can bite you with with the IO monad as having to pass around the world state token turns single return values into multiple return values (i.e., the new state token plus the returned value).<br>
<br>
I haven't actually dug into your code to see if this is part of the problem, but figured I would mention it.<br>
<br>
Cheers! -Tyson<br>
_______________________________________________<br>
Glasgow-haskell-users mailing list<br>
<a href="mailto:Glasgow-haskell-users@haskell.org" target="_blank">Glasgow-haskell-users@haskell.org</a><br>
<a href="https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2fmail.haskell.org%2fcgi-bin%2fmailman%2flistinfo%2fglasgow-haskell-users&data=01%7c01%7csimonpj%40064d.mgd.microsoft.com%7cd6315a7cc7034672b7a008d37c3d4709%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=Zy2n6Lkhaqb4ZIty4bf20UhMYcOxqa61yeaolDebuZI%3d" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users</a><o:p></o:p></p>
</blockquote>
</div>
</div>
</div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><br>
_______________________________________________<br>
Glasgow-haskell-users mailing list<br>
<a href="mailto:Glasgow-haskell-users@haskell.org" target="_blank">Glasgow-haskell-users@haskell.org</a><br>
<a href="https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2fmail.haskell.org%2fcgi-bin%2fmailman%2flistinfo%2fglasgow-haskell-users&data=01%7c01%7csimonpj%40064d.mgd.microsoft.com%7cd6315a7cc7034672b7a008d37c3d4709%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=Zy2n6Lkhaqb4ZIty4bf20UhMYcOxqa61yeaolDebuZI%3d" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users</a><o:p></o:p></p>
</blockquote>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</body>
</html>