Re: Garbage Collection in Ada

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

Robert I. Eachus wrote:
> 
>    My observations are based on simulations which in some cases run
> more than a week--of CPU time.  The characteristics of my experience
> are: heap allocated objects containing a large amount of non-pointer
> state, including random values and in some cases the state of a random
> number generator.  This is the worst case environment for a
> conservative collector.
My experience has been that for the vast majority of applications,
conservative collection behaves well and spurious retention is not an
issue.  All evidence suggests that they are perfectly stable over long
runs.  You will occasionally see spurious retention.  But the expected
number of additional spurious pointers reachable from a spuriously
retained object is < 1, so things stabilize.

Every once in a while I hear about an application for which
that's not true.  Typically these store large amounts of more or less
random data in the heap.  The state of a single random number generator
(or 100 random number generators) is not an issue.  2 megabytes of
compressed bitmaps are an issue.  In all such cases of which I am aware
there was a straightforward solution to the problem:  Inform the
collector that these objects contain no pointers, or contain pointers in
only a few positions.  In one case it was easier to change the data
format slightly.  I believe all of the modifications were trivial
compared to the difficulty of using manual deallocation.

Again, I believe all of this is largely irrelevant for an Ada
implementation.  If you are concerned about this issue, it's easy to
allocate objects with the correct layout information for HEAP objects.
The hooks currently in our collector are probably even sufficient to
implement this.

> 
>     Hans-Juergen Boehm described a much different environment:
> 
> > Please try it for yourself.  Until April I was reading my mail on a
> > conservatively garbage collected system that couldn't possibly have
> > stayed up for weeks by this chain of reasoning.  (It did.)  Many other
> > systems that are in routine use couldn't possibly work either.
> 
>      Heap memory values in such an environment will tend to contain
> valid pointer values and substrings of mostly English ASCII text.  It
> is possible that in Boehm's environment, no legal pointer corresponds
> to any printable substring.

Actually bitmaps are also quite common.  Character strings and some
bitmaps were allocated with a pointerfree allocation primitive, so this
wasn't an issue.  (This was easy to arrange, since they were allocated
in very few distinct places.)  Thread stacks, static data, and mixed
structures in the heap were scanned conservatively.  The Cedar
environment was (and probably still is) used for a number of
applications including some fairly long-running CPU-intensive ones.


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