Re: Garbage Collection in Ada

[dewar@merv.cs.nyu.edu (Robert Dewar)]

Lars asks

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.

- How large is the probability that this occurs?

   very hard to tell, but a program that relies on this not happening is
   inherently unreliable.

- How large is the probability that this state persists?

   unknown

- How large fraction of allocated memory will typically be
  falsely retained?

   unknown

- Is the set of retained blocks growing over time or will it
  level out at some point in time? If so where?

   could grow over time certainly

- other?

   other than the small possibility of freeing in-use blocks, and the
   consequent necessity to make sure you know what your compiler is
   doing and what your program is doing, I don't see any. 

How likely is it that Quicksort will crash due to stack overrun?

   This has zero probability in a properly written version. Only incompetent
   student implementations of Quicksort could fail with a stack overrun that
   was data dependent. You should know the technique (anyone should), you
   simply sort the small half first. This is an absolutely standard divide
   and conquer trick for keeping stack usage to logN.

How likely that a Skiplist will behave in a non optimal fashion?

   Any program depending on it NOT so behaving has a bug

How likely that a binary tree turns linear?

   Any program depending on this has chosen a wrong data structure!

How likely that a compiler has a bug that will make
your program fail one way or another?

   Well possible, but data dependent bugs are somewhat rarer, but certainly
   this is possible in a non-certified program.

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?

   Again, a program that depends on this without proper analysis has a bug

and many, many other similar hazards that a program is exposed to.

   Well programs can be "exposed" to many problems caused by incompetent
   engineering decisions. I would say that relying on a conservative
   garbage collector NOT to get unlucky is something that you can afford
   to do in one-off programs that don't need to be reliable, and perhaps
   even in typical PC software (so what if the word processor crashes once
   a week - that seems to be what people expect anyway).

   But, as in my original point, I don't see that many high reliability
   programs could rely on conservative GC for correctness, though possibly
   they could rely on it for average case performance requirements.

P.S. does lack of expertise mean you have no experience with conservative
collectors? For someone with no experience, you sure are an enthusiast :-)
I will admit I have no experience with them either, because I have never
had occasion to need or want unreliable garbage collection in any program
I have written. I have OFTEN relied on reliable garbage collection, and
consider this a very valuable feature for a very large range of programs.