[gclist] Name that hypothesis

Nick Barnes nickb@harlequin.co.uk
Wed, 04 Dec 1996 11:06:53 +0000


> > Subject: [gclist] Name that hypothesis
> > What is the name of the following hypothesis?
> >
> > 	"Most references in a system point backwards in time, i.e. from
> > 	 younger objects to older objects."
> >
> > In the GC community we all know this, and many of us use it
> > frequently, but we don't seem to have agreed on a name for it.
> >
> It seems to me that this is actually
> 
> 1) Much stronger than required by a generational collector, and
> 2) False for a significant fraction of nonfunctional programs.

Yes, but it is true in a large set of systems. I agree that to get an
efficiency win out of this in a generational collector, one actually
only needs this much weaker form:

	"Most inter-generational references point from a younger
	 generation to an older generation."

(If this is true, collecting a young generation is much cheaper than
collecting an old generation, which is a good thing because one wants
to collect young generations more often than old generations, because
the generational hypothesis tells you that young generations contain
more garbage).

But this is highly specialized to the GC implementation. The "ordering
hypothesis" is a predicate on mutators, which a memory manager may
take advantage of if it is true.

I'd like to emphasize here that I'm interested in these properties or
hypotheses as aspects of different mutators, so that one can classify
mutators according to their suitability to particular GC strategies.
I'm not saying that they are all true for all systems. None of them
are true for all systems, not even the generational hypothesis.

Nick B