[gclist] Compiler lifetime analysis

[William D Clinger]

The best case would be if the compiler can prove that an object only has
    local scope, and therefore replace the call to the allocator with stack
    allocation....

A great many compilers for garbage-collected languages do this,
at least for certain classes of objects such as closures and flonums.

If you regard the traditional stack-based representation of a
continuation as a special case of this optimization (which I do),
then almost every compiler does this.

The best case actually occurs when the compiler can replace heap
allocation with register allocation.

    Also, could many general GC allocators make use of a lifetime hint when
    the object is allocated?

Yes.  Many Lisp systems have made use of such hints.  As Paul Wilson
pointed out, it is less obvious that such hints should be used with a
modern generational collector.  One reason is that, in practice, the
average cost of allocation tends to be far less with generational
collectors, so there is less reason to bother with such hints.

>This is exactly what you want:
>
>   Barrett, David and Zorn, Benjamin. Using Lifetime Predictors to
>   Improve Memory Allocation Performance. Proceedings of the SIGPLAN
>   '93 Conference on Programming Language Design and
>   Implementation, 187-196.  Albuquerque, New Mexico, June 1993.

This paper describes "an algorithm for lifetime prediction that
accurately predicts the lifetimes of 42-99% of all objects allocated".
This is an interesting claim because, for the fast-allocating C
programs on which it is based, there is a much simpler algorithm that
accurately predicts the lifetimes of 91-100% of all objects.  This
simpler algorithm just predicts that _every_ newly allocated object
will die young.

The Barrett-Zorn algorithm makes sense when the cost of misprediction
is much greater in one direction than in another, as happens with
some non-copying collectors.  One of the reasons generational
copying collectors work so well is that they use a trivial (therefore
fast) algorithm to predict lifetimes, and copying is a fairly cheap
way to recover from mispredictions.

Will