heap profiling

[Evan Laforge]

> Right, I wouldn't use DList for this.  Here's an alternative I use:
>
> data AList a = ANil | ASing a | Append (AList a) (AList a)
>
> lenA :: AList a -> Int
> lenA ANil          = 0
> lenA (ASing _)     = 1
> lenA (Append l r)  = lenA l + lenA r
>
> appendA ANil r = r
> appendA l ANil = l
> appendA l r    = Append l r
>
> Note how appendA is strict(ish) and eliminates ANils, so in a writer monad
> it shouldn't build up a space leak.  I'm sure you can write toList (don't
> use (++) though).

I hope you're not overestimating me :)  I thrashed around for a good
long time trying to get (++) to associate to the right, and then
stumbled across OrdList in ghc, which is apparently just this data
structure, with the addition of 'Many [a]'.

> I'd put the bang on ws:
>
>      m>>= k  = WriterT $ do
>          (a, w)  <- runWriterT m
>          (b, w') <- runWriterT (k a)
>          let !ws = w `mappend` w'
>          return (b, ws)
>
> The problem with this monad is that >>= isn't tail-recursive, so it will
> cause stack overflows on recursive monadic functions.  I suspect that a
> better alternative to the strict writer monad is the strict state monad in
> most cases, because its bind is tail-recursive.

Bang on 'ws' was my first instinct too, but it appeared to have no
effect.  I tried to work out a manual reduction for >>= to figure out
exactly what is being forced when, but I got a headache and decided to
do something more relaxing, like watch Primer.

Yes, I suppose Writer's >>= isn't tail recursive... which seems like a
disaster for >>=, since they are usually composed into very long
chains.  I know non-tail recursiveness isn't necessarily a disaster in
haskell because of laziness, but it seems like you need just one
strict monad in the stack, like ErrorT or IO and you are no longer
lazy.

I implemented LoggerT as a strict state monad, and I think it got
better, but there's still a lot of garbage coming from somewhere.
AppendList actually seems slower in the face of repeated appends than
(:) followed by reverse, as I mentioned in the other email.  Or it
could be I'm not measuring things right...

>> I also have a situation where -hb shows about 4mb of drag at the most,
>> but when I run with '-hc -hbdrag', I only see 10k peaks.  Shouldn't
>> filtering the graph by drag add up to as much drag as when the graph
>> isn't filtered?
>
> That sounds suspicious.  If you can make a self-contained example that
> demonstrates it and create a ticket, that would be a great help.

Ok, I'll try to reduce this to a manageable size.  It's the same code
that produces the deadlock while profiling, so perhaps that's related.


thanks again for the advice!