[Haskell-cafe] Stacking State on State.....

[Phil]

On 01/03/2009 20:16, "Andrew Wagner" <wagner.andrew at 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,
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090301/8bb01367/attachment.htm