TITLE: what is conservative garbage collection

(Newsgroups: comp.lang.c++.moderated)


RESPONSE: nagle@netcom.com (John Nagle), 17 Jul 96

     Hans Boehm has published a number of papers on the subject, and
if you read them, it will be clear what's going on.

     The basic idea of conservative garbage collection is that whenever
you find a binary value in memory that might be a pointer, you consider
whatever it points to to be in use.  This works better than you might
expect, because most random 32-bit values won't be in the allocated
address space.  Obviously, some text strings will be interpreted as
pointers and will result in excess memory being held, but in practice that
doesn't seem to increase memory consumption much.

     This works because 32 bits address 4GB, but typical programs have
only a few megabytes of free store.  If, for example, you have 1 MB of
free store, a random 32-bit value has only one chance in 4000 of being
a possible pointer.  

      The false-pointer problem
increases with the fraction of memory in use.  Worse, it increases faster
than linearly.  As free store in use increases, not only are there 
are more possible false pointers, but the odds of a random value being 
interpreted also increases.  If you have 100 MB of free store, the odds 
are only 1 in 40, and there are 25 million possible pointers to examine. 
At some large free store size, conservative garbage collection will
stop working.  But that size is big.