Re: Question about garbage collection

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

Bob Duff said

<<I agree.

All gc's are necessarily conservative, in that they don't always collect
all memory the program will never use again.  To be perfect, the gc
would need to predict the future, which is of course impossible.
>>

I did not mean to be contentious in using the word true, so let's use the
word octopus instead

I define octopus GC (OGC for short from now on)
to be a scheme in which memory is only retained if
there is a live pointer through which some future execution path of
the program might access the memory, and I specificaly exclude the notion
of static or dynamic analysis of future possible behavior.

So a block is live if it is a root, or, recursively if it is referenced
by a pointer in a live block.

OGC is for example implemented in typical SNOBOL4 and Algol-68 compilers.

The point about OGC is that you can analyze maximum memory usage patterns
of your program, just as you can in a program in which all memory allocation
is explicit.

The issue of compaction is enirely orthogonal. One can have compaction in
malloc/free regimes, or compaction in GC regimes. It tends to be the case
that compaction goes with GC, but that is by no means fundamental in either
direction.

If there is no compaction, then your analysis must take into account
fragnmentation effects in either case.

Bob said

<<Methinks the primary reason for GC is to avoid dangling pointers.
And the secondary reason is to avoid memory leaks.>>

That's an odd way of putting it, but I see what you mean. Obviously it is
possible to avoid both DP's and ML's with a conventional malloc/free regime.
Apparently what you are saying is that you would prefer to be at the mercy
of bugs in the runtime GC rather than bugs in your own code :-)

With regard to avoiding ML's, conservative garbage collection is NOT
guaranteed to be effective. Once there is one uncollected garbage block,
it can be the source of bogus roots to other uncollected garnage blocks,
and this process can recur without limit. Yes, it is unlikely to do so,
but if you want to guarantee absence from ML's, conservative GC is not
attractive. OGC on the other hand allows a relatively simple high level
analysis.