[gclist] Re: gclist-digest V1 #125

[Greg Morrisett]

At 06:05 AM 12/5/96 EST, you wrote:
>The effect of these properties is that in most situations where C uses
>dynamic memory allocations it is not needed in Ada. When using pointers
>to stack-allocated data it is not possible to create dangling references.
>All pointers in the stack pointing to the stack are backward pointers.
>
>So the only reason to use dynamic memory allocation is in cases where 
>having backward pointers is not enough. I'm very curious what the effects
>of this would be for the garbage hypotheses posted lately.

But stack allocation can often lead to space leaks because objects 
can only be freed in a lifo manner.  For instance, take any tail-
recursive procedure -- if you allocate objects on the stack frame that 
get passed to the next invokation of the procedure, then the entire stack 
frame, including the space for the transient objects, will be retained 
(unless you're willing to do a local compression of the stack frame which 
no one seems to actually do -- a really smart compiler would indeed 
allocate the long-lived objects towards the "base" of the stack, and 
the transient objects away from the base so that the stack can be
adjusted before the tail-call.)  In contrast, if those objects 
that do live across the procedure call are heap allocated, then 
the entire frame can be discarded and only those heap-allocated 
objects are retained.  There are other examples where, after a
procedure call, something deeper in the stack becomes garbage
(perhaps because you pass a pointer by reference and it gets updated
to point to some other object.)  Again, you'll retain the space
for the object until you return from that procedure.  

The work by Tofte & Co., on region inference indicates that these
pathalogical cases do arise, at least in ML code.

On another note, it's interesting to see how many studies of allocation
behavior take into account the stack -- a lot of data is allocated there
and could potentially be freed.  Heck, no C compiler in the world 
(except possibly Sun's) does tail-call elimination for non-self tail calls.

-Greg