Re: Garbage Collection in Ada

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

Mitch Gart wrote:
> 
> Lars Farm (lars.farm@ite.mh.se) wrote:
> 
> : Your dislike (apparently shared by other Ada people) for conservative
> : collectors has raised a couple of questions that I can not answer
> : ...
> What I don't like is the idea that the GC will have to go through ALL
> data memory (and registers) looking for pointers.  The time it takes
> to make a scan is proportional to total memory size rather than proportional
> to the number of pointers in use, or proportional to the number of
> heap blocks, or proportional to some other reasonable value.
> 
"Conservative" GC is not an all or nothing proposition.  I don't think
anyone would claim that the collector should not take advantage of
easily available information.  It should be easy enough to have an Ada
compiler generate address ranges that contain only statically allocated
pointerfree Ada variables.  Those could easily be skipped by the
collector.  As Fergus Henderson points out this is even easier for
pointerfree heap objects.  On the other hand, there are certain kinds of
pointer information that are harder to come by.  I would argue that it's
often beneficicial to scan the following regions conservatively:

1. C allocated data and stack frames.  The C code may be part of the
language run-time system.

2. Stack frames, and especially the top one.  Generating descriptors is
hard work, error-prone, and takes space.

(Most collectors for a work-station environment actually try to keep the
GC cost per allocation fixed.  If there is too much static data that
must be scanned we grow the heap to reduce collection frequency.  Since
this happens mostly if the heap is a small fraction of the data size,
the space cost is usually tolerable.)
-- 
Standard disclaimer ...
Hans-Juergen Boehm
boehm@mti.sgi.com