[Haskell-cafe] mapM is supralinear?

[Malcolm Wallace]

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