Re: Compile Time Garbage Collection impossible?

the.real.doctor.zoidberg@gmail.com wrote:
> Why isn't Compile-Time-Garbage-Collection feasible?
> [...]
>
> [Local objects are usually stack allocated and freed at end of scope.
> You need GC when you do dynamic allocation, and chain stuff into lists
> and trees of data structures. -John]


Basically, John's comment points exactly to the problems that you'll
encounter on the path to automatic, static memory management.


While most data structures that consist of only a single object are
easy to identify so that the compiler can insert a 'delete' statement
for it, once a data structure consists of multiple objects (think of
a linked list or a tree), program analyses are too coarse to tell
single elements of the structure apart. Consider two modules, one
acting as a producer and the other one acting as a consumer, which
cooperate via a linked list of 'jobs' - I've yet to see a program
analysis which can analyze only the most simple code which implements
this and find out when a /single/ item of the list can be deallocated.


In general, this won't be possible for any arbitrary program --- see
G. Ramalingam's paper titled "The undecidability of aliasing".


Still ...


We've presented the paper mentioned below which shows our approach to
static compile-time automatic memory management. We are able to treat
/all/ objects that are allocated by the program, and, by construction,
we /always/ delete each object exactly once. The paper shows that this
/can/ be done, but it also shows that there are limits to what you can
do. Of course, I'll welcome every proof that the limits are less strict
than what we say they are --- the very conference on which the paper
was presented had a couple of interesting approaches that let you
understand some (seemingly) simple code fragments such as the
reversal of a linked list. Maybe we'll see more work in this direction,
so that eventually, a compiler might have the ability to produce
a program that statically manages memory without the need for a runtime
GC, for most reasonable programs (for a suitable definition of
'reasonable' :).


If you can't find the paper online, feel free to contact me and ask
for a copy.


cheers,
Florian

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