Complexity bug in garbage collector?

Simon Marlow simonmar at
Thu Apr 14 16:42:50 EDT 2005

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:
> 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.


More information about the Glasgow-haskell-users mailing list