Re: Compile Time Garbage Collection impossible?

Torben Ęgidius Mogensen wrote:
> the.real.doctor.zoidberg@gmail.com writes:
>
>> Why isn't Compile-Time-Garbage-Collection feasible?
>
> The short answer is that while CTGC is possible, it can not collect
> all the data that a run-time GC (RTGC) can (or, at least not as
> early).


Well, that's not quite right. One weak point of run-time GC is that a
pointer to some structure can make it seem to be accessible (i.e.
it's not syntactic garbage) while the program doesn't access it again
(i. e. it is semantic garbage). With CT GC, you can often identify
semantic garbage and free it while the RT GC would have to leave it
allocated. There's no hard-and-fast rule to say which of the two will
perform better --- sometimes, CT GC wins, sometimes RT GC works
better.


> All automatic memory management rely on predicting when a value will
> no longer be accessed. [...] So you need a conservative approximation
> [...]


Any program analysis computes such a safe approximation. It is a
question of the quality of the analysis whether the approximation is
close enough to the run-time behavior of the program. With the
exception of linear types (which you have mentioned), it is easy to
"fool" a program analysis into believing that objects are reachable
although they aren't - just rewrite a structure (a tree or a graph) so
that at any point at run-time, only few nodes are actually reachable,
and see the analysis assume that all nodes ever allocated of that
structure need to remain allocated until the end of the procedure(s).


> Most RTGC methods [...] be followed.


Yes, exactly. Sometimes, you have to fight semantic garbage by hand.


> At compile-time, you don't have access to the continuation, [...]
  > The question is if it can be precise enough.


A global program analysis can provide pretty good results. They will
be better for an easily analyzable language (think Java) than for a
non-typesafe language (think C or C++). The real question, in my
experience, is whether a global analysis can be made to scale up to
huge systems that have millions of lines of code.


> [...] the programmer may have to program with regions
> in mind, sometimes doing things somewhat differently than he would
> with RTGC. Region analysis [...]


The approaches for ML (or other functional languages) aren't
applicable to imperative languages, and no, even monads won't help
here.


Programming "with regions in mind" is very much like programming with
explicit, manual memory management in mind, except that you don't get
to deallocate single objects (which, come to think of it, isn't much
of a restriction). Programming with "what will the compiler do with
this program" in mind would seem to be more of a torture, though.


> You can also use CTGC in combination with RTGC [...]


Yes, any analysis (including the ones you mentioned) that helps the RT
GC will always be welcome in a compiler/runtime environment, as long
as the 'illusion' of automatic memory management is being upheld.


cheers,
Florian
--

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