From: daveg@synaptics.com (Dave Gillespie)
Newsgroups: comp.lang.c++
Subject: Re: Garbage Collection for C++
Date: 20 Aug 92 09:38:46 GMT
	<DAVEG.92Aug13025629@synaptx.synaptics.com>
	<TMB.92Aug16164940@arolla.idiap.ch>
	<1992Aug18.021453.24394@news.mentorg.com>
	<TMB.92Aug18123919@arolla.idiap.ch>
Organization: Synaptics, Inc., San Jose, CA
In-reply-to: tmb@arolla.idiap.ch's message of 18 Aug 92 16:39:19 GMT

In article <TMB.92Aug18123919@arolla.idiap.ch> tmb@arolla.idiap.ch (Thomas M. Breuel) writes:

> I hope we can agree that GC costs you nothing if it doesn't run
> (malloc and free in the presence of GC don't look very different from
> the way they do now).

Well, as long as you don't introduce tagged pointers, maintain a
linked list of all GC pointers, or anything like that.  (And I think
most of us would agree that you'd want to avoid all those things if
you possibly can, and it looks like you can pretty easily.)

> Conservative GC with a "free" function is a safety net. If you don't
> run out of storage, you don't know it's even there. If you do run out
> of storage, it lets your program continue to run when it would
> otherwise have crashed.

In particular, it's a very useful safety net:  If the GC has a mode
when it reports how many bytes were collected, it can aid debugging
of a program that is supposed to be 100% careful about deleting
things manually.  If the GC finds anything to collect, then you
must have dropped somethings somewhere.

Combined with a manual way to invoke the GC on demand, this is a
tool on a par with the malloc_verify operations some libraries
provide.

>    [...]  Suppose such an object contains 6 pointers. In your conservative
>    scheme, those 6 pointers must then be checked because they might refer
>    to GC objects. If those pointers are declared non-GC, the GC doesn't even
>    have to think about them; it can go straight on to the next memory block.
>    Depending on the proportion of GC to non-GC, this could be a major saving.

> If I read your paragraph correctly, you suggest that instead of
> carrying out the usual GC marking phase on both the GC heap and the
> non-GC heap, the non-GC heap is scanned once, linearly.

To make this practical, you'd need three heap classes:  Objects that
the GC can collect; non-collectable objects that still may contain
pointers to collectable objects (this would be the safest default
type of allocation); and non-collectable objects that are known not
to contain pointers to collectable objects.

If you have a "non-GC" declaration, the compiler can automatically
decide when a given "new" can use this third heap area.  Even without
that, it can certainly use the third area for any type that contains
no pointers at all (say, big arrays of ints or doubles).

The GC doesn't have to scan the third area at all.  Suppose you have
an image-processing program that allocates various data structures,
along with some huge one-megabyte arrays of numbers.  The three-area
approach allows the GC to completely ignore these numeric arrays.

> Furthermore, your scheme
> requires the collector to distinguish between non-GC and GC pointers
> during collection; the cost of doing so is probably roughly equivalent
> to the cost of checking the "marked" bit on a block.

That's probably true, but with three-area allocation, classes which
contain *only* non-GC pointers can be optimized at compile-time.  In
practice most systems would probably ignore the non-GC declaration
except for the case where all the pointers are declared non-GC.

								-- Dave
--
Dave Gillespie
  daveg@synaptics.com, uunet!synaptx!daveg
  or: daveg@csvax.cs.caltech.edu
Newsgroups: comp.lang.c++