[Haskell-cafe] mapM is supralinear?

[Arseniy Alekseyev]

Malcolm, one should amortize the cost of the collection over the
amount of free space allocated rather than recovered (there are cases
when no space is recovered, would you call the GC cost infinite
then?).

If one does that, and also runs the expensive collection not too often
[1], the time amortizes to O(1) easily (notice that the amount
allocated between GCs can be kept proportional to H).

I don't know if GC used in GHC does indeed have amortized O(1) cost
per allocation, but if it doesn't, it should.

[1] - a sufficient condition would be that there exists some real
number q such that q > 1 and the next GC runs not sooner than when H
reaches H_0*q where H_0 is the heap size remaining after the last
collection.

On 27 September 2011 10:02, Malcolm Wallace <malcolm.wallace at me.com> wrote:
>
> 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
>
>