Re: Garbage Collection in Ada

[Hans-Juergen Boehm <boehm@mti.sgi.com>]

Robert A Duff wrote:
> 
> In article <3265BD97.41C6@mti.sgi.com>,
> Hans-Juergen Boehm  <boehm@mti.sgi.com> wrote:
> >For systems I've seen it does inhibit some optimizations, ar least to
> >the extent that proper use of a conservative collector inhibits
> >optimizations.  Especially in multithreaded systems, there must be a
> >recognizable pointer to every accessible object at every program point
> >at which a GC might occur.  Often this is between every pair of
> >instructions.  In a nonconservative system you could generate
> >arbitrarily complex tables to allow reconstruction of those pointers.
> 
> I would think it would be simpler and more efficient to represent this
> information as executable code.  That is, the compiler generates a
> procedure for each type, and for each stack frame, that knows how to
> find all the pointers.  It could take the PC as a parameter, so it could
> deal with optimizations where, for example, register R1 contains a
> pointer sometimes, and an integer other times.
> 
That seems to be the consensus.  Whether or not it's right probably
depends on the context.  There appear to be systems around that lose performance
by generating code instead of tables.  There are at least 2 reasons it may be
undesirable:

1. Code size.  Even generating traversal procedures for user-defined data
structures is not free.  (The SRC Modula 3 implementation does this, so it
should even be possible to quantify the effect.)  Things get much worse if
you have to generate a traversal procedure for every client procedure frame,
and if the result of that procedure depends on the PC value.  Even table sizes
for code with limited GC interruption points are nontrivial (see the paper by
Diwan, Moss, and Hudson in PLDI 92).  I would guess that generating such code
for really arbitrary interruption points with full optimization would more
than double code size.  (Actually this is impossible in a few odd cases.  See the
above paper.)

2. Too much procedure call overhead, especially for structures composed of many
small user-defined types.  How much of an issue this is depends on the details
of the compilation system.  But it's usually easier to optimize tables with
whole program information than code.  Since table interpretation can be
cheap, this may dominate.

> Anyway, I don't understand why you would want a conservative collector,
> unless you're dealing with an uncooperative language/compiler (like C).
> If the language "requires" gc, then there's every opportunity to have a
> well-defined interface between generated code and gc, so why be
> conservative?
> 

There are several reasons to go with a collector that acts conservatively by
default, but can make use of type information:

1. C intercallability.
2. The compiler-collector interface is much simpler, at least for the fall-back case.
You might get code compiled by one compiler to link against code compiled by another.
3. You can scan the top stack frame conservatively.  Then you only need to have
pointer location information at call sites, potentially reducing table (or traversal
code) size substantially.
4. You don'y have to get the type information right for hand-coded routines in the
runtime.  In my experience, this is a significant source of persistent GC bugs.  It
also makes it easier to debug other type descriptor problems.


-- 
Standard disclaimer ...
Hans-Juergen Boehm
boehm@mti.sgi.com