Reducing Pause Times With Clustered Collection

Clustered Collection reduces garbage collection pauses in programs with large amounts of live data. A full collection of millions of live objects can pause the program for multiple seconds. Much of this work, however, is repeated from one collection to the next, particularly for programs that modify only a small fraction of their object graphs between collections. Clustered Collection reduces redundant work by identifying regions of the object graph which, once traced, need not be traced by subsequent collections. Each of these regions, or “clusters, ” consists of objects reachable from a single head object. If the collector can reach a cluster’s head object, it skips over the cluster, and resumes tracing at the pointers that leave the cluster. If a cluster’s head object is not reachable, or an object within a cluster has been written, the cluster collector may have to trace within the cluster. Clustered Collection is complete despite not tracing within clusters: it frees all unreachable objects. Clustered Collection is implemented as modifications to the Racket collector. Mea