RE: Complexity bug in garbage collector?
On 29 July 2005 12:53, Josef Svenningsson wrote: My machine was definitely swapping when I aborted the program. Can that have any effect on the timings? yes, there's your problem. It's still a nice regular-looking curve though, which is mildly surprising. Simon ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Complexity bug in garbage collector?
On 4/14/05, Simon Marlow [EMAIL PROTECTED] 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 -MVERY 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
___
Glasgow-haskell-users mailing list
Glasgow-haskell-users@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Complexity bug in garbage collector?
Hi all, 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? Cheers, /Josef ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
RE: Complexity bug in garbage collector?
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 ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
