[gclist] Re: gclist-digest V1 #125

[David Chase]

> From: Greg Morrisett <jgm@CS.Cornell.EDU>
> 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. 

Oddly enough, I was browsing my dissertation yesterday (looking to
see what I said about Clark's measurements) and way near the end, I
talk about the loop case of this.  If it's a tail-recursive procedure,
then you ought to (1) make the loop explicit, and then (2) attempt to 
deal with the allocation (that you'd like to have on the stack) as
a case of a short-lived (non-cyclic) in-loop allocation.  There's
several cases to consider:

  (a) allocation has constant size -- hoist it out of the loop

  (b) the union of the short-lived allocation lifetimes is also
      non-cyclic -- record stack height on entry to loop, and reset
      it traversing edges exiting the union of the short lifetimes.

  (c) the union contains a cycle -- employ some heuristic to remove
      lifetimes from the cycle, because removing the optimal number
      is an NP-complete problem (see dissertation for proof).

> 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.

Certainly Sun's does this.  I thought they did it pre-3.0 (the one 
I worked on, shipped in early 1994) and I know that they did it in 
the 3.0 compilers.  Note that if you get too clever in your use of 
the stack (take its address, for instance) or pass too many parameters, 
or use parameters of particular types, then this optimization won't 
happen (some of these operations make implicit use of the stack, 
and keep it alive "across" the tail call).  Actually, I thought that
everyone who could do this, did do this; if it is as rare as you
imply, I'm surprised.

speaking for myself,

David Chase