Report Number: CS-TR-94-1510
Institution: Stanford University, Department of Computer Science
Title: Key Objects in Garbage Collection
Author: Hayes, Barry
Date: March 1994
Abstract: When the cost of global garbage collection in a system grows
large, the system can be redesigned to use generational
collection. The newly-created objects usually have a much
shorter half-life than average, and by concentrating the
collector's efforts on them a large fraction of the garbage
can be collected at a tiny fraction of the cost.
The objects that survive generational collection may still
become garbage, and the current practice is to perform
occasional global garbage collections to purge these objects
from the system, and again, the cost of doing these
collections may become prohibitive when the volume of memory
increases. Previous research has noted that the objects that
survive generational collection often are born, promoted, and
collected in large clusters.
In this dissertation I show that carefully selected
semantically or structurally important key objects can be
drawn from the clusters and collected separately; when a key
object becomes unreachable, the collector can take this as a
hint to collect the cluster from which the key was drawn.
To gauge the effectiveness of key objects, their use was
simulated in ParcPlace's Objectworks\Smalltalk system. The
objects selected as keys were those that, as young objects,
had pointers to them stored into old objects. The collector
attempts to create a cluster for each key by gathering
together all of the objects reachable from that key and >From
no previous key.
Using this simple heuristic for key objects, the collector
finds between 41% and 92% of the clustered garbage in a suite
of simple test programs. Except for one program in the suite,
about 95% of the time these key objects direct the collector
to a cluster that is garbage. The exception should be heeded
in improving the heuristics. In a replay of an interactive
session, key object collection finds 59% of the clustered
garbage and 66% of suggested targets are indeed garbage.