[Haskell-cafe] mapM is supralinear?
malcolm.wallace at me.com
Tue Sep 27 11:02:35 CEST 2011
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.
More information about the Haskell-Cafe