Re: Garbage Collection in Ada

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

Robert Dewar wrote:

> Personally, although these kind of conservative collectors are a partial
> solution useful in some circumstances, I don't find them acceptable for
> serious solution of the GC problem. If you count on  a conservative
> collector to free storage, you have a very unreliable program, since
> you could find on some particular run that you were just unlucky and
> a junk integer value held a critical large block in memory, causing
> the program to crash and burn.
> 
> If you don't mind a program with this kind of unreliability, then this
> approach may work, but for me, the only really viable approach, and the
> only one worth putting real effort into in the Ada context is a proper
> full GC that know what is a pointer and what is not.
> 

Let's compare the options here:

1. Traditional manual memory management
- No guarantees about space usage, since the language definition makes
  no guarantees.
- Space usage may be unexpectedly large on certain inputs due to
  fragmentation effects.  The worst-case space usage of any general
  purpose allocator is at least N logN, where N is the amount of live
  heap data.  If this occurred in practice, the customer would probably
  be unhappy.  And many commonly used allocators have much worse
  worst-case performance than that.

2. Conservative garbage collection
- No guarantees about space usage, since the language definition makes
  no guarantees.
- Space usage may be unexpectedly large on certain inputs due to
  fragmentation effects or due to misidentified pointers.

3. Nonconservative garbage collection
- No guarantees about space usage, since the language definition makes
  no guarantees.
- If you use a compacting collector, you can bound heap size to a
  constant factor times live data size (which is not true for
  either of the above), but you'll pay for it in other ways.

Thus I would claim that if you really need hard space bounds your
options are severely limited (e.g. no general purpose dynamic memory
allocation or perhaps a compacting collector + platform specific tools
to bound stack use, etc.)



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