[gclist] More GC comments, please?

[Nick Barnes]

At 1998-06-08 01:49:17 UT, Chris Smith writes:

> 1) Can anyone tell me if it (a) is feasible, and (b) has been done and
> documented somewhere, to implement a generational collector that copies
> the new generation, and marks and sweep older generations?

Yes, this has been done many times.  It's a reasonable design choice;
the main problem with it is that it means you have to implement two
different garbage collectors and manage their interaction.  This is
generally true of other hybrid schemes.  I don't have my books to
hand, otherwise I could give you a citation.  Doesn't Jones & Lins
discuss this in their chapter on generational collection?

> My latest idea (maybe good, maybe bad, but I've either been missing a lot 
> or it isn't widely discussed in the introductory GC lit) is to write a
> collector that collects the new object area in a single stop-and-copy
> manner, and concurrently works on collecting older objects via mark-sweep.

Yes.  This is not altogether dissimilar to the Nettles/O'Toole work
(with which I was peripherally involved).

> It seems to me that due to the low promotion rate of objects in the first
> generation, copying would be ideal specifically there.

Yes, copying is best-suited to the nursery.

> 2) Is it feasible to bound the time for execution of a small collection by
> bounding the size of the new object area?  The only place I've seen
> something like this discussed is in the Nettles/O'Toole article I just
> read, which implies that their desired bound (50 ms) could be done that
> way.  Would it be possible for a larger time slot, or is the collection
> cycle bad in the worst case?

You won't get a hard bound.  Most collection time is spent scanning,
and in almost all cases, almost all of your time is spent scanning
survivors, so you get a good soft bound, but you can't put a hard
bound on it because you can't put a hard bound on the root set (which
could be the whole heap).

> 3) A general question about promotion policies.  Has anyone considered
> what empirically happens to an object AFTER a pointer to it gets stored in
> an older generation?

This kind of thing is quite dependent on the mutator and the
generation.  In the nursery, for most mutators which have been
studied, the simple information that the program has _some_ interest
in _any_ object strongly correlates with that object's survival at the
next collection.  Most objects which die in the nursery die within a
few thousand machine cycles of being created.  But then there's a
trade-off involving your promotion cost, and the complexity of your
collector.  If you want to avoid the cost of maintaining
inter-generational pointers, you have to promote that object, _and all
its descendants_, to the generation in which you have found its
parent.  If you only have 1.5 or 2 generations, that part isn't too
hard.  But it's still a bunch more code, which will cause you endless
headaches until you've fixed the first round of defects.

At least in the first instance, I suggest keeping your collector as
simple as possible (which probably means promoting on survival from
the nursery), and experimenting with this sort of thing as a bolt-on
once you have the rest of your system working.

Nick B