On 26 Sep 2011, at 23:14, Arseniy Alekseyev wrote:
> Garbage collection takes amortized O(1) per allocation, doesn't it?
No. For Mark-Sweep GC, the cost is proportional to
(H+R) / (H-R)
where H is the total heap size
R is the reachable (i.e. live) heap
This formula amortises the cost of a collection over the amount of free space
recovered.
For two-space copying collection, the cost is proportional to
R / ((H/2)-R)
In both cases, as R approaches H (or H/2), the cost of GC becomes rather large.
So in essence, the more live data you have, the more GC will cost.
Regards,
Malcolm
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
