<HTML>
<HEAD>
<TITLE>Re: [Haskell-cafe] Stacking State on State.....</TITLE>
</HEAD>
<BODY>
<FONT SIZE="4"><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'>On 01/03/2009 20:16, &quot;Andrew Wagner&quot; &lt;wagner.andrew@gmail.com&gt; wrote:<BR>
I know very little about profiling, but your comment about spending a lot of time garbage collecting rang a bell with me - the example on RWH talks about that exact issue. Thus, I would recommend walking through the profiling techniques described on <FONT COLOR="#0000FF"><U><a href="http://book.realworldhaskell.org/read/profiling-and-optimization.html">http://book.realworldhaskell.org/read/profiling-and-optimization.html</a></U></FONT> .<BR>
<HR ALIGN=CENTER SIZE="3" WIDTH="95%">Yes, I&#8217;ve been going through this very example to try to ascertain where the problem lies:<BR>
<BR>
Profiling gives an almost identical program flow for both:<BR>
<BR>
Three stacks:<BR>
<a href="http://pastebin.com/m18e530e2">http://pastebin.com/m18e530e2</a><BR>
<BR>
Two Stacks:<BR>
<a href="http://pastebin.com/m2ef7c081">http://pastebin.com/m2ef7c081</a><BR>
<BR>
The output from &#8220;&#8211;sstderr&#8221; shows the garbage collector in overdrive for Three Stacks:<BR>
<BR>
Three Stacks:<BR>
<a href="http://pastebin.com/m5f1c93d8">http://pastebin.com/m5f1c93d8</a><BR>
<BR>
Two Stacks:<BR>
<a href="http://pastebin.com/m2f5a625">http://pastebin.com/m2f5a625</a><BR>
<BR>
Also note the huge memory usage for Three Stacks! &nbsp;If I &#8216;heap profile&#8217; this I can see that within the first few seconds the &#8216;Three Stacks&#8217; approach grabs ~85MB, it then peaks after 100 seconds. &nbsp;It then starts to reclaim the memory until the end of the program.... Slowly but surely. &nbsp;The ~85MB is due to a Constant Applicative Form &#8211; as I understand it these are values with no arguments that have a one-off cost. &nbsp;I assume this means they are things that are not assigned to a variable.<BR>
<BR>
On the other hand the graph for the Two Stack approach is a mess &#8211; that is it jumps all over the place which I can only interpret as things are being allocated and de-allocated very quickly.<BR>
<BR>
Three Stacks heap:<BR>
<a href="http://www.beadling.co.uk/mc2_3stacks.pdf">http://www.beadling.co.uk/mc2_3stacks.pdf</a><BR>
<BR>
Two Stacks heap:<BR>
<a href="http://www.beadling.co.uk/mc2_2stacks.pdf">http://www.beadling.co.uk/mc2_2stacks.pdf</a><BR>
<BR>
<BR>
Thinking about this some more, perhaps the issue here is that all the memory required is held through the whole computation for the Three Stack approach, because we continually thread computations until we have an answer. &nbsp;Because the Two Stack approach produces a list that we then map, perhaps the garbage collector can start to reduce memory usage as it does the final computation. &nbsp;This is counterintuitive to what I had hoped &#8211; but if we use replicateM, does haskell throw away preceding states after we have a new state, or is holding the 3 states of every single computation right up until it has chained the last computation?<BR>
I&#8217;d still expect to see a spike or a peak in the Two State approach, but we see nothing of the sort.<BR>
<BR>
If anyone can offer up a better explanation, I&#8217;d be interested to hear it!<BR>
<BR>
Thanks again,<BR>
<BR>
Phil,</SPAN></FONT></FONT>
</BODY>
</HTML>