On 01/03/2009 20:16, "Andrew Wagner" <wagner.andrew@gmail.com> 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,