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 <[email protected]> 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 > > _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
