[gclist] Age based promotion

[David Chase]

At 08:10 AM 12/17/98 -0800, Simon Peyton-Jones wrote:
>> Supposing you keep two flavors of remembered set, one for those
>> old objects modified to point to young (and hence likely to be
>> modified again to point to different young) and the other for
>> those objects promoted which happen to contain pointers to young?

>Thanks for the algorithm you suggest.  By suggesting it, you imply that this
>issue is not well covered in the literature, which confirms what
>I thought.

True, but it was almost immediately obvious to someone
somewhat skilled in the art :-).  Whether it will be
profitable in practice or not is another matter entirely.
It could be that someone tried this, it failed, and they
neglected to publish their negative result.  And then
another someone else, etc, etc.  Somebody needs to start
the Journal of Hard Knocks, for experiments that didn't
turn out as hoped.

>> I don't think that transitive promotion is a good idea, since I can
>> imagine (and I think I've seen) certain programming styles for which
>> this would be a relatively disastrous policy.

>Dave Ungar said this too.  Can either of you give some idea of what
>sort of programs would behave badly?  The kind where old things are
>modified often?

Some systems contain a few very old things that are frequently modified;
imagine, if you will, that a "thread" is an object, and so is an 
"activation record", and the thread contains a reference to its 
top-most activation record.  The thread is very old, the activation
record is usually very young but varies in age.  When a GC occurs,
there's a medium-sized possibility that an activation record mid-way
down the stack will be promoted from young to old, and you clearly
do not want to recursively promote all the younger portion of the
stack, as well as all the objects referenced from local variables
on that stack; that's often young and/or frequently modified.  GC
is not always used to reclaim activation records, but sometimes
it is, and stacks used like this are a moderately common data
structure in their own right (think of worklists in iterative
algorithms, for instance).

Essentially, this is a case where the objects promoted ARE likely
to be modified in the near future.  Only promoting one level into
the nepotism set will cost you some for these programs, but not
as much as promoting the entire show.  This is something that could
probably be measured, if any of us had the time, but the measurements
are also unlikely to generalize (Haskell implementations probably
look rather different from Java implementations, for instance).

David Chase
NaturalBridge LLC