Complexity bug in garbage collector?

[Josef Svenningsson]

On 4/14/05, Simon Marlow <simonmar at microsoft.com> wrote:
> On 14 April 2005 15:35, Josef Svenningsson wrote:
> 
> > I've had some fun chasing around a couple of space leaks lately. One
> > of the graphs that I produced looked like this:
> > www.cs.chalmers.se/~josefs/coresa.ps
> >
> > Notice the shape of the graph. It shows a perfect squareroot function.
> > But my program should be allocating at a constant rate. From previous
> > experience this suggests that there is a time complexity bug in the
> > garbage collector. This makes it take time proportional to the square
> > of the amount of allocated memory. Can someone confirm this?
> 
> The X axis of the heap profile is mutator time: that is runtime
> excluding GC time, so you wouldn't see any non-linear GC effects in the
> shape of the heap profile anyway.  You'll be able to confirm this by
> comparing the time on the profile to the wall-clock time, and checking
> the output from +RTS -sstderr is useful too.
> 
> It's possible you're seeing cache effects: as the working set grows
> larger, the program slows down.  The shape does look a bit too perfect
> to be cache effects, though.
> 
I don't think the cache has much to do with what I'm seeing. I think
the program is mostly allocating and that is (as far as I remember)
much easier to handle efficiently with the cache than reading.

> I wouldn't rule out any bugs (of course :-), so please send us further
> evidence if you find it.
> 
OK, I've cooked up this little program to study the behaviour a little closer:
\begin{code}
module Main where

main = print $ strictId [1..]

strictId list = let (c,c') = work list c'
                in c
  where work [] y' = (y',[])
	work (x:xs) y' = (v,x:v')
	  where (v,v') = work xs y'
\end{code}

This program just allocates like crazy til it dies. The funny looking
strictId function is just the strict identity function on lists. (Yes,
there are simpler ways to achieve the same thing. I just think the
above function is particularly sweet :-)

I do the following:
$ ghc -prof -auto-all --make Main.hs
$ main.exe +RTS -hd -M<VERY MUCH>

The resulting graph is suspiciously similar in shape to the one of my
previous program. The garbage collector is still my primary suspect, I
simply don't know how to explain the graph otherwise.

/Josef