Re: GC statistics (was Re: big project ported)

[Godmar Back <gback at cs dot utah dot edu>]

> 
> >>>>> "Tom" == Tom Reilly <treilly@allaire.com> writes:
> 
> Tom> This is a shot in the dark but would it be possible to reduce the
> Tom> work the garbage collector has to do by allocating temporary
> Tom> objects that live within the scope of a method call on the stack?
> 
> It is possible, but the compiler has to prove that the object can't be
> captured.  We don't do this kind of analysis right now.  I don't think
> we even know how much of a win it would be.  I'd be interested in
> hearing statistics on this.  (Actually, I thought I read a paper on
> this that said it wasn't a big enough win to bother doing.  Now I'm
> not sure if I'm just dreaming that.)
> 

There has indeed been some work on stack allocation in Java. [1,2]
There has been a lot of previous work in the context of other languages
such as ML.

At this point, my personal upshot is that its impact varies from application
to application (surprise), but that its efficacy is greatly influenced
by the following factors:

+ the aggressiveness with which the compiler resolves method calls.
  Method resolution depends on accurate type information, and this
  in turn depends on a effective class hierarchy analysis and an
  aggressive inter-procedural analysis.  For instance, the compiler
  must know all assignments to a given member variable to determine
  its type.

  For most examples I worked with on an non-public project, it was
  astonishing in how few cases the compiler would pick up possibilities
  for stack allocation without performing this type of analysis.

+ the performance of the allocator/collector.  It can turn out that
  allocating (and zeroing out!) small pieces of stack space is slower
  than the allocation performance of a fast linear allocator, especially 
  a copying one which does not need to touch short-lived objects ever
  again.

There is definitely cases in which stack allocation is a clear winner.
For instance, Spec98's db benchmark has an inner loop where a 
stack-allocatable Vector enumeration is obtained.  (Not that such benchmarks 
should influence what anybody's working on)

Except more work on this in the future.

	- Godmar


[1] http://www.cs.utah.edu/flux/papers/gc-wcsss99-abs.html
[2] http://www.research.microsoft.com/apl/