On 01/03/2009 20:16, "Andrew Wagner" <[email protected]> wrote: 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 http://book.realworldhaskell.org/read/profiling-and-optimization.html .
Yes, I¹ve been going through this very example to try to ascertain where the problem lies: Profiling gives an almost identical program flow for both: Three stacks: http://pastebin.com/m18e530e2 Two Stacks: http://pastebin.com/m2ef7c081 The output from ³sstderr² shows the garbage collector in overdrive for Three Stacks: Three Stacks: http://pastebin.com/m5f1c93d8 Two Stacks: http://pastebin.com/m2f5a625 Also note the huge memory usage for Three Stacks! If I heap profile¹ this I can see that within the first few seconds the Three Stacks¹ approach grabs ~85MB, it then peaks after 100 seconds. It then starts to reclaim the memory until the end of the program.... Slowly but surely. The ~85MB is due to a Constant Applicative Form as I understand it these are values with no arguments that have a one-off cost. I assume this means they are things that are not assigned to a variable. On the other hand the graph for the Two Stack approach is a mess that is it jumps all over the place which I can only interpret as things are being allocated and de-allocated very quickly. Three Stacks heap: http://www.beadling.co.uk/mc2_3stacks.pdf Two Stacks heap: http://www.beadling.co.uk/mc2_2stacks.pdf 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. 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. This is counterintuitive to what I had hoped 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? I¹d still expect to see a spike or a peak in the Two State approach, but we see nothing of the sort. If anyone can offer up a better explanation, I¹d be interested to hear it! Thanks again, Phil,
_______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
