Complexity bug in garbage collector?

[Simon Marlow]

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 wouldn't rule out any bugs (of course :-), so please send us further
evidence if you find it.

Cheers,
	Simon