Re: Compile Time Garbage Collection impossible?

the.real.doctor.zoidberg@gmail.com wrote:
> Why isn't Compile-Time-Garbage-Collection feasible?
[...]


Obviously, it is. But equally obviously, it isn't complete. :)


It's quite possible for a compiler to maintain a reference count for
heap-allocated objects. When *the compiler can tell* the count reaches
zero (say at the end of blocks) it's possible to plant a "free()".


But down to things like the halting problem, it's impossible to have
this cover all cases. At some point any automatic system (even your
head :) will not be able to decide -- is this garbage now, or not?


On such occasions it's traditional to put the reference count INTO the
object, and use a decr and test. And this, too, could be planted by a
compiler.


But we again come to problems of decidability -- it would not be
possible to have such automatically-planted decr-and-test maintain the
smallest heap possible or remove garbage as soon as possible, etc.


I know Prolog (based on an abstract machine) goes to what I'd call
extra-ordinary lengths to maintain a small amount of memory usage.
Most of this is via objects allocated on a stack.


But the system also tries to decide whether objects *should* be
allocated on a stack or heap, or whether it can speculatively allocate
on a stack and later -- if it needs to -- plant a test that may copy
it to the heap (when it determines at least 1 more ref to the object
has been screated in the meantime).


The strategy usually also needs the help of a periodic
garbage-collection on heap objects.

Return to the comp.compilers page.
Search the comp.compilers archives again.