Re: Garbage Collection in Ada

[lars.farm@ite.mh.se (Lars Farm)]

Robert Dewar <dewar@merv.cs.nyu.edu> wrote:

> Are there really programs that count on conservative GC working?

Ok, you don't like conservative collectors. Could you please explain in
a bit more detail why conservative collectors are so bad.

I don't have the expertise needed to confirm or refute your statements.
It seems to me that for a conservative collector to falsely retain a
block of memory there has to be a bitpattern somewhere in the root set
(stack, globals, registers, currently allocated blocks,(?)) that can be
interpreted as (1) a pointer to one of the currently allocated blocks
that is (2) unreachable from the root set (no longer any user pointers
to it) (3) not yet reused by the collector.

Your dislike (apparently shared by other Ada people) for conservative
collectors has raised a couple of questions that I can not answer. I
would like to get some feel for how bad this really is. 

- How large is the probability that this occurs?
- How large is the probability that this state persists?
- How large fraction of allocated memory will typically be
  falsely retained?
- Is the set of retained blocks growing over time or will it 
  level out at some point in time? If so where?
- other?

This leads to larger memory consumption. This may or may not be a
problem. To put the problem into perspective one could perhaps compare
to other common engineering compromises in computing. How likely is it
that Quicksort will crash due to stack overrun? How likely that a
Skiplist will behave in a non optimal fashion? How likely that a binary
tree turns linear? How likely that a compiler has a bug that will make
your program fail one way or another? How much RAM is wasted because one
makes redundant copies of a datastructures just to know when to release
RAM without GC instead of sharing the datastructure with GC? and many,
many other similar hazards that a program is exposed to.

I believe, perhaps wrongly, that the "problems" of a conservative GC is
on or even below that scale. Is it? or is it much worse? The impression
I get from your posts is that you would place the problems of a
conservative collector way over the common problems we face daily.


-- 
Lars Farm, lars.farm@ite.mh.se