🚀 go-pugleaf

acha@CS.CMU.EDU (Anurag Acharya) writes:
>... garbage collection needs time proportional to the
>amount of live data (best case -- mark and sweep needs time proportional
>to the all space available to the program). 

(I hate to start this thread again, especially since it's irrelevant to
the previous discussion, but ...)
As far as I know, the above statement about mark-sweep collection is
only meaningful and correct if:

1. Allocation and initialization time is not considered,
2. Concurrent or incremental collection is not considered.  (Otherwise it
becomes hard  and pointless to distinguish the collector and the allocator.)
3. The M/S collector is not allowed to defer sweeping to allocation
time, e.g. by using a bit map representation of the free list.
4. The collector does not attempt to maintain the heap size as a fixed
multiple of the amount of live data (otherwise there's no asymptotic
difference between the two).

(1) seems rather arbitrary.  There are great arguments for violating (2)
through (4), and I don't know of any good arguments for not implementing
at least (3) (and (4) under a real OS).

Thus, I think a more informative version of the standard statement
about asymptotic complexity of mark/sweep collection is:

It's possible to implement mark-sweep collection so badly that garbage
collector pause time is proportional to all space available to the
program.

Of course, there are other arguments why mark-sweep collection might
to e.g. copying collection under the right circumstances.  But I think
the asymptotic complexity argument is 95% bogus.

Hans-J. Boehm
(boehm@parc.xerox.com)
Standard disclaimer ...