Garbage collection is a technology that solves a practical programming problem, namely that of reclaiming unused heap storage. Manual management of heap storage is notoriously error prone and garbage collection can help to simplify programming significantly. Most new programming languages incorporate garbage collection, and despite advances in computer hardware, the performance of garbage collection continues to matter.

So-called generational collection has helped to improve the efficiency of garbage collection in fast-allocating programs by focusing on collecting young garbage, but has done little to reduce the cost of collecting a heap containing large amounts of older data. A new generational technique, older-first collection, shows promise in its ability to manage also older data.

This dissertation reports on an implementation study that compares two older-first collectors to traditional (younger-first) generational collectors. In general, the older-first collectors perform adequately and are often effective at reducing the first-order cost of collection relative to younger-first collectors. Older-first collectors are particularly effective at managing data with queue-like or random lifetimes and heaps containing large amounts of live data.

However, the older-first collectors are brittle in the sense that their performance may degrade quickly on some kinds of large linked data structures. My implementations incorporate techniques that restore robustness by effectively disabling older-first collection in cases where degradation occurs, and this dissertation discusses further measures the collectors may take to avoid performance degradation.

Document: final.ps.gz (994KB)
Benchmark programs, processing code, and Larceny: programs.tar.gz (4.3MB)