[gclist] generational promotion heuristics

[Simon Marlow]

Chris Smith writes:
> Apologies in advance if this is a dumb or well-known and well-answered
> problem.  Has anyone compiled any empirical results on heuristics for
> promotion in generational garbage collection besides just the 
> number of
> collections that an object has survived?  I'm specifically interested
> right now in deciding promotion based on the number of references from
> other objects... the number is easily found while collecting since all
> references are essentially traced anyway.

Sure, but you have to count references which entails storing an extra
integer along with each object.  This overhead could be pretty high.
Furthermore, if the garbage collector promotes or copies objects as soon as
they are found to be referenced, having to count references would turn an
evacuate/scavenge algorithm into a mark/evacuate/scavenge three-pass
algorithm.

A slightly different idea, but our generational collector in the Glasgow
Haskell Compiler tries to avoid promoting certain objects that we know will
soon be updated (or assigned to), in order to cut down the number of
old-to-new inter-generational pointers.  This was found to be a big win in
certain cases - we could save heaving a huge chunk of data into the old
generation if the object being updated becomes garbage after a short period
of time.

We also promote objects early if they are found to be already referenced,
directly or indirectly, from the old generation.  This saves some
intermediate copies since the object is sure to be promoted eventually
anyway.

[ GHC's homepage is at
http://www.research.microsoft.com/users/t-simonm/ghc/, a paper on our
garbage collector is in the works. ]

Cheers,
	Simon