[Haskell-cafe] Re: XML (HXML) parsing :: GHC 6.8.3 space leak from 2000

[Simon Marlow]

Lev Walkin wrote:

> I wondered why would a contemporary GHC 6.8.3 exhibit such a leak?
> After all, the technique was known in 2000 (and afir by Wadler in '87)
> and one would assume Joe English's reference to "most other Haskell
> systems" ought to mean GHC.

Thanks for this nice example - Don Stewart pointed me to it, and  Simon PJ 
and I just spent some time this morning diagnosing it.

Incedentally, with GHC 6.8 you can just run the program with "+RTS -hT" to 
get a basic space profile, there's no need to compile it for profiling - 
this is tremendously useful for quick profiling jobs.  And in this case we 
see the the heap is filling up with (:) and Tree constructors, no thunks.

Here's the short story:  GHC does have the space leak optimisation you 
refer to, and it is working correctly, but it doesn't cover all the cases 
you might want it to cover.  In particular, optimisations sometimes 
interact badly with the space leak avoidance, and that's what is happening 
here.  We've known about the problem for some time, but this is the first 
time I've seen a nice small example that demonstrates it.

>     -- Lazily build a tree out of a sequence of tree-building events
>     build :: [TreeEvent] -> ([UnconsumedEvent], [Tree String])
>     build (Start str : es) =
>             let (es', subnodes) = build es
>                 (spill, siblings) = build es'
>             in (spill, (Tree str subnodes : siblings))
>     build (Leaf str : es) =
>             let (spill, siblings) = build es
>             in (spill, Tree str [] : siblings)
>     build (Stop : es) = (es, [])
>     build [] = ([], [])

So here's the long story.  Look at the first equation for build:

 >     build (Start str : es) =
 >             let (es', subnodes) = build es
 >                 (spill, siblings) = build es'
 >             in (spill, (Tree str subnodes : siblings))

this turns into

       x = build es
       es' = fst x
       subnodes = snd x

       y = build es'
       spill = fst y
       siblings = snd y

now, it's the "siblings" binding we're interested in, because this one is 
never demanded - in this example, "subnodes" ends up being an infinite list 
of trees, and we never get to evaluate "siblings".  So anything referred to 
by siblings will remain in the heap.

The space-leak avoidance optimisation works on all those "fst" and "snd" 
bindings: in a binding like "siblings = snd y", when y is evaluated to a 
pair, the GC will automatically reduce "snd y", so releasing the first 
component of the pair.  This all works fine.

But the optimiser sees the above code and spots that es' only occurs once, 
in the right hand side of the binding for y, and so it inlines it.  Now we have

       x = build es
       subnodes = snd x

       y = build (fst x)
       spill = fst y
       siblings = snd y

Now, usually this is a good idea, but in this case we lost the special 
space-leak avoidance on the "fst x" expression, because it is now embedded 
in an expression.  In fact in this case the thunk goes away entirely, 
because build is strict.

But now, when the program runs, the thunk for siblings retains y, which 
retains x, which evaluates to a pair, the second component of which 
evaluates to an infintely growing list of Trees (the first components is a 
chain of "fst y" expressions that constantly get reduced by the GC and 
don't take up any space).

We don't know of a good way to fix this problem.  I'm going to record this 
example in a ticket for future reference, though.

Cheers,
	Simon