<div dir="ltr">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><div><br>time                11.08 ms   (10.86 ms .. 11.34 ms)<br>Measured for a million elements in the list</div><div><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><div>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.</div><div><br></div><div>-harendra<br><br>On 12 May 2016 at 05:41, Dan Doel <<a href="mailto:dan.doel@gmail.com">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">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<br></div></div></div>