[gclist] Age based promotion

[David Chase]

>> I called the problem you describe
>>  "Nepotism" -- the fact that some old dead object
>> drags young, also dead objects across into tenured status merely
>> by dint of a relationship ;-).

At 12:08 AM 12/17/98 -0800, Simon Peyton-Jones wrote:
>Well, (ii) does not make anything live longer than it would
>have otherwise.  If an old dead object points to a young object, then
>the latter will live till the former's generation is gc'd.  Promoting
>the young one doesn't make it live any longer; it simply prevents
>it being copied to and fro mean while, which must be a good thing.

>Are there any descriptions about how to do this 'eager promotion'?
>As I indicated message, it is not obvious to me how to implement it.

>My argument for (ii) breaks down for objects that are mutated often.
>Have you or anyone else measured this effect?

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?
The second set contains old-to-new pointers, but you have no
reason to believe that they are likely to be modified in the
near term.

Then, in the next GC, you start with the second remembered set,
and promote the first level (or more?) of referenced young objects.
This will add new objects to that second set for the next GC (you
could implement transitive promotion simply by scanning the set
till done, but I'm not sure you want to do this). 

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.

One thing that I'm not at all clear on is by how much these newly-old
and new objects differ in their age; if it's simply a matter of avoiding
one round of copying after already having performed N (that is, if
the newly-old and new differ in age by only one GC) then what
I propose won't win you anything.

Another tweak on this would be to subtract the members of the first
remembered set from the second remembered set, since that indicates
modification, and we assume that modification is likely again in
the future.

If you were using software card-marking, it would be relatively
easy to implement this using different card values -- use one set
of values to mark an object that was just-promoted and contains
old-to-new pointers, and use a different set of values to indicate
that an old object was modified to perhaps point to young.  The
modification cards will overwrite the promotion-induced cards,
and you get your subtraction for free, at the expense of two sweeps
over the card table at GC.

Note that if your system "knows" that all the fields of an object
are write-once or write-rarely, then it might use a different mark
than it does for those modifications that could be more frequent.

David Chase
NaturalBridge LLC