<div dir="ltr">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.<div><br></div><div>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.</div><div><div><br></div><div>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.<br></div><div><br></div><div>-harendra<br><div><br></div><div><div class="gmail_extra"><div class="gmail_quote">On 15 May 2016 at 01:56, David Feuer <span dir="ltr"><<a href="mailto:david.feuer@gmail.com" target="_blank">david.feuer@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><p dir="ltr">The state token is zero-width and should therefore be erased altogether in code generation.</p><div><div>
<div class="gmail_quote">On May 14, 2016 4:21 PM, "Tyson Whitehead" <<a href="mailto:twhitehead@gmail.com" target="_blank">twhitehead@gmail.com</a>> wrote:<br type="attribution"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">On 14/05/16 02:31 PM, Harendra Kumar wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
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.<br>
</blockquote>
<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" rel="noreferrer" 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="http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users</a><br>
</blockquote></div>
</div></div><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="http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users</a><br>
<br></blockquote></div><br></div></div></div></div></div>