Re: Garbage Collection

[boehm@titan.rice.edu (Hans Boehm)]

In reference to g-rh@cca.CCA.COM (Richard Harter)'s question:
>        There is problably something I am missing, but I don't quite see
>how you can implement garbage collection in C without collateral assumptions
>-- how is the garbage collector supposed to know that that a block is free?

  This is usually, but not always, possible.  The idea is to use a traditional
non-compacting mark-sweep collector.  On a UN*X system, we start by scanning
the registers, stack, data, and (statically allocated) bss segments for
any addresses of valid allocated objects.  We subsequently scan allocated
objects we find in the same way.  For a typical C program, all reachable
objects can be found in this manner.  (Storing exclusive or'ed pointer
values, tagged pointers, and similiar programming tricks, as well as some
rarely used (for C) compiler optimization techniques may break this scheme.)
  In theory, we may end up marking a few unreachable objects as reachable
as well, since integers may be misinterpreted as pointers.  The collector
can be designed so that the only result of this is excess storage retention.
(This does require that we don't compact.)  In my experience, I have never
seen any indication of such unnecessary retention in practice.  There is
an argument to be made that no garbage collector is completely immune
from this phenomenon.
  The fact that the collector has to perform a fairly complicated (but still
O(1)) check for pointer validity does slow it down a little.  On a Sun 3/260,
with a 2 Meg heap, half of which is in use, we normally see collection times of
about 3 seconds.  (This assumes longword aligned pointers and small data and
static bss areas.)  All of this is largely irrelevant if the
collector is used as a debugging tool to detect storage leaks.
  More details can be found in Mark Weiser's and my upcoming Software P&E
article entitled "Garbage Collection in an Uncooperative Environment".

Hans-J. Boehm
boehm@rice.edu