<p dir="ltr">Well, a few weeks ago Bertram Felgenhauer came up with a version of IO that acts more like lazy ST. That could be just the thing. He placed it in the public domain/CC0 and told me I could put it up on Hackage if I want. I'll try to do that this week, but no promises. I could forward his email if you just want to try it out.</p>
<div class="gmail_quote">On May 14, 2016 2:31 PM, "Harendra Kumar" <<a href="mailto:harendra.kumar@gmail.com">harendra.kumar@gmail.com</a>> wrote:<br type="attribution"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">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)<div><br></div><div>Not sure if there is a way to write this code in IO monad which can reduce this overhead.<br><div><br></div><div>-harendra<br><br><br>On 14 May 2016 at 17:10, Harendra Kumar <<a href="mailto:harendra.kumar@gmail.com" target="_blank">harendra.kumar@gmail.com</a>> wrote:<br>><br>> You are right about the way IO code is generated because of the ordering semantics. The IO version builds the list entirely in a recursive fashion before returning it while the pure code builds it lazily. I wrote very simple versions to keep things simpler:<br>><br>> Pure version:<br>><br>> f [] = []<br>> f (x : xs) = x : f xs<br>><br>><br>> time 11.08 ms (10.86 ms .. 11.34 ms)<br>> Measured for a million elements in the list<br>><br>> 104,041,264 bytes allocated in the heap<br>> 16,728 bytes copied during GC<br>> 35,992 bytes maximum residency (1 sample(s))<br>> 21,352 bytes maximum slop<br>> 1 MB total memory in use (0 MB lost due to fragmentation)<br>><br>><br>> IO version:<br>> f [] = return []<br>> f (x : xs) = do<br>> rest <- f xs<br>> return $ x : rest<br>><br>> time 79.66 ms (75.49 ms .. 82.55 ms)<br>><br>> 208,654,560 bytes allocated in the heap<br>> 121,045,336 bytes copied during GC<br>> 27,679,344 bytes maximum residency (8 sample(s))<br>> 383,376 bytes maximum slop<br>> 66 MB total memory in use (0 MB lost due to fragmentation)<br>><br>> Even though this is a small program not doing much and therefore enhancing even small differences to a great degree, I am not sure if I can completely explain the difference in slowness of the order of 7.5x by just the recursive vs lazy building of the list. I am wondering if there is anything that is worth further investigating and improving here.<br>><br>> -harendra<br>><br>> On 12 May 2016 at 05:41, Dan Doel <<a href="mailto:dan.doel@gmail.com" target="_blank">dan.doel@gmail.com</a>> wrote:<br>> ><br>> > On Tue, May 10, 2016 at 4:45 AM, Harendra Kumar<br>> > <<a href="mailto:harendra.kumar@gmail.com" target="_blank">harendra.kumar@gmail.com</a>> wrote:<br>> > > Thanks Dan, that helped. I did notice and suspect the update frame and the<br>> > > unboxed tuple but given my limited knowledge about ghc/core/stg/cmm I was<br>> > > not sure what is going on. In fact I thought that the intermediate tuple<br>> > > should get optimized out since it is required only because of the realworld<br>> > > token which is not real. But it might be difficult to see that at this<br>> > > level?<br>> ><br>> > The token exists as far as the STG level is concerned, I think,<br>> > because that is the only thing ensuring that things happen in the<br>> > right order. And the closure must be built to have properly formed<br>> > STG. So optimizing away the closure building would have to happen at a<br>> > level lower than STG, and I guess there is no such optimization. I'm<br>> > not sure how easy it would be to do.<br>> ><br>> > > What you are saying may be true for the current implementation but in theory<br>> > > can we eliminate the intermediate closure?<br>> ><br>> > I don't know. I'm a bit skeptical that building this one closure is<br>> > the only thing causing your code to be a factor of 5 slower. For<br>> > instance, another difference in the core is that the recursive call<br>> > corresponding to the result s2 happens before allocating the<br>> > additional closure. That is the case statement that unpacks the<br>> > unboxed tuple. And the whole loop happens this way, so it is actually<br>> > building a structure corresponding to the entire output list in memory<br>> > rather eagerly.<br>> ><br>> > By contrast, your pure function is able to act in a streaming fashion,<br>> > if consumed properly, where only enough of the result is built to keep<br>> > driving the rest of the program. It probably runs in constant space,<br>> > while your IO-based loop has a footprint linear in the size of the<br>> > input list (in addition to having slightly more overhead per character<br>> > because of the one extra thunk), because it is a more eager program.<br>> ><br>> > And having an asymptotically larger memory footprint is more likely to<br>> > explain a 5x slowdown than allocating one extra thunk for each list<br>> > concatenation, I think. (Of course, it could also be some other<br>> > factor, as well.)<br>> ><br>> > You should probably run with +RTS -s (compiling with -rtsopts), and<br>> > see if the IO version has a much larger maximum residency.<br>> ><br>> > Anyhow, this is fundamental to writing the algorithm using IO. It's an<br>> > algorithm that's a sequence of steps that happen in order, the number<br>> > of steps is proportional to the input list, and part of those steps is<br>> > putting stuff in memory for the results.<br>> ><br>> > > So why is that? Why can't we generate (++) inline similar to (:)? How do we<br>> > > make this decision? Is there a theoretical reason for this or this is just<br>> > > an implementation artifact?<br>> ><br>> > The difference between these two is that (++) is a function call, and<br>> > (:) is a constructor. Constructors are a special case, and don't need<br>> > to have all the provisions that functions in general do. The best way<br>> > to learn what the differences are is probably to read the paper about<br>> > the STG machine.<br>> ><br>> > Hope this is a more fruitful lead, but it may be that there's not a<br>> > lot that can be done, without doing some baroque things to your<br>> > algorithm, because of the necessity of its using IO.<br>> ><br>> > -- Dan</div></div></div>
<br>_______________________________________________<br>
Glasgow-haskell-users mailing list<br>
<a href="mailto:Glasgow-haskell-users@haskell.org">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>