Re: Garbage Collection in Ada

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

I will argue yet again that there is no fundamental difference in
reliability between conservative collection and a general purpose
vendor-supplied nonmoving memory allocator with explicit deallocation.
To guarantee that your program doesn't run out of memory, you would have
to prove that a certain amount of memory suffices.  I'm not an expert on
Ada implementations, but in C this is impossible for many reasons:

1.  The worst-case memory requirements of ANY general purpose malloc
implementation are quite bad.  This is a mathematical theorem.  The only
way to limit this is to restrict object sizes.

2.  Many vendor malloc implementations have even worse worst-case
behaviour, sometimes much worse.

3.  Vendors rarely specify the allocation algorithm.  So it's not
possible to tune for the algorithm even in nonportable code.

4.  Independent of fragmentation issues, language standards don't
sprcify padding, allocator overhead, etc.

Random corrections/observations:

- I know of no commercial system vendors that include a conservative GC.
There are many third-party language implementations that include a GC
that's at least partially conservative (e.g. SRC Modula-3, NAG Fortran
90, Sun's Java, Sather, ...)

- I don't believe it's realistically possible for a C compiler to
exclusive-or the pointer location into the pointer value (or to use
self-relative pointers).  Copying pointer-containing unions becomes
essentially impossible.  (This is irrelevant to the discussion, but ...)

- "Virtual origins" work fine with a conservative GC, so long as you
also keep the naive pointer representation.  This is likely to be cheap 
(at most one extra store).

- The latest draft of the C++ standard requires new and delete to be
replaceable.  (This is also irrelevant, I think ...)

- There are a number of measurements of accidentally retained memory by
conservative GC.  It's usually smaller than fragmentation losses, which
aren't very big either.  That says nothing about worst-case bounds.  

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