[gclist] Re: "This Old Space", with apologies to Will Clinger

[William D Clinger]

Nick Barnes wrote:
> Are you able to say more? You plainly have a "different generational
> collector", and a model to go with it. Can you tell us about them?

Henry Baker's example illustrated the superiority of my
2-generation "non-predictive" collector over conventional
generational and non-generational collectors for the radioactive
decay model.

I'll let Henry's explanation stand for now.  I have been revising
the full paper whose abstract Henry referenced, and will make it
available by June 1997 at the latest, as a technical report if
not a conference paper.

A non-predictive collector can use any basic gc algorithm, not
just the Cheney-Fenichel-Yochelson stop-and-copy algorithm of
Henry's example.

Henry Baker wrote:
> ...we should
> be able to get additional efficiency [from] larger
> numbers of generations, which Will does in his paper.

My paper doesn't really consider the efficiency to be gained
from more than two generations.  What I actually do in my paper
is to show how the amortized efficiency of a 2-generation
non-predictive collector varies as a function of the load factor
and the relative sizes of the two generations.  (Henry's example
assumed both have the same size.)

The amortized efficiency is asymptotically independent of the
half-life.

Mark Tillotson mentioned the following hypothetical example:
>         Total live heap:            30MB
>         Spare memory:                5MB
>         youngest generation size:  0.1MB
>         allocation-rate:             1MB/s
>         promotional-rate from youngest gen: 0.005MB/s
>           (I'm positing 0.5% survival rate after 100K of allocation)

These numbers are statistically impossible for the radioactive
decay model.  If only 0.5% of the most recently allocated 100K
of allocation survive, then the model implies that the _total_
live heap is just over 5000 bytes, not the 30MB shown above.
To put it differently, 30MB of live heap implies a half-life
of over 20 megabytes of allocation, which implies nearly 100%
survival after 100K of allocation.  (See the derivation of
n = 1/(1-p) in Henry's message.  n is the total live storage,
and p is related to the half-life h by p = 2^(-1/h).)

Let me repeat Henry's caveat:  Real world heaps have statistics
very different from those of the radioactive decay model.  The
radioactive decay model is primarily useful for Gedanken
experiments that improve our theoretical understanding of
generational garbage collection.

I believe this improved theoretical understanding will lead to
practical collectors whose worst case performance is better
than that of current generational collectors, but this has not
yet been demonstrated.

William D Clinger