gc locality and the gc toolkit

Paul Wilson made a number of good observations about the history and
behavior of various gc algorithms, especially w.r.t. locality. I want to
add a little bit to that and toot my group's horn a little about a gc
package we're developing. This package, which we call the Language
Independent Garbage Collector Toolkit, gives a language implementor a lot
of the pieces to do generational collection. I need to describe some
details to get to the part relevant to locality, so bear with me:


The toolkit allows a variable number of generations. At each scavenge,
some generation and all younger generations are scavenged; the choice of
the oldest generation to process at each scavenge is made by a user
supplied policy routine. Generations are further broken down into STEPs. A
step is a set of objects that are treated as being of the same age. A
typical/expected arrangement is for a generation to have several steps and
to promote from each step to the next step at each scavenge. Having K
steps then means that promotion from that generation requires K scavenges
of that generation. In any case, steps avoid any high water mark
comparison, not to mention age bits in objects (think of it as a BIBOP
approach to age tracking). The number of steps in a generation may vary.
Finally, a step consists of a variable number of fixed size BLOCKS. When a
block fills up you either allocate another one, or cause a scavenge. There
is a separate large object space (LOS) to handle objects best treated
without copying.


Suppose a given generation has a 10% survival rate (i.e., 10% of the
objects survive any given scavenge), and has N blocks of objects before a
scavenge. A semi-space collector would use 2N blocks' worth of space, in
two semi-spaces, each of which is required to be contiguous. The tollkit
collector will use 1.1N blocks and the blocks themselves can be anywhere
since one block is as good as another. At lower survival rates this will
dramatically increase locality.


In addition, the NURSERY (the space where objects are first created) is a
single contiguous space, with overflow optionally detected by a page trap
rather than requiring an explicit limit check. The nursery is reused on
each scavenge. This is as advocated by Wilson, Ungar, and others, to
increase locality.


What strikes me is how the various pieces fit together. You get the 1.1
versus 2 behavior because we use fixed size blocks, which requires a large
object space, which allows nursery overflow to be done with a trap
(because "small" objects are bounded in size so the allocation cannot
cross the guard pages).


We plan to make the toolkit available when it is shaken down, and we have
submitted an article on it for publication. Please don't send mail asking
for the toolkit; I'll make an announcement when we're ready. If you're
really interested in more details, I can send a PostScript version of a
tech report on the toolkit via email (sorry, we're not set up for
anonymous ftp; maybe in a while we'll arrange that). Regards -- Eliot Moss
--
J. Eliot B. Moss, Assistant Professor
Department of Computer Science
Lederle Graduate Research Center
University of Massachusetts
Amherst, MA 01003
(413) 545-4206, 545-1249 (fax); Moss@cs.umass.edu
--

Return to the comp.compilers page.
Search the comp.compilers archives again.