[Haskell-cafe] mapM is supralinear?

[Malcolm Wallace]

On 27 Sep 2011, at 11:23, Arseniy Alekseyev wrote:

> Malcolm, one should amortize the cost of the collection over the
> amount of free space allocated rather than recovered

They are the same thing.  You can only allocate from the space that has been recovered.  It is true that generational GC has a nursery area of largely constant size, which is always used for fresh allocation, but that is usually considered an optimisation (albeit a considerable one), which does not fundamentally change the underlying asymptotic costs of the major collections.  When you have large heap residency, the proportion of time spent in GC increases.

> (there are cases
> when no space is recovered, would you call the GC cost infinite
> then?).

Indeed I would.  When that happens, usually the program aborts without completing its computation, so the computation is infinitely delayed. 

Regards,
    Malcolm