Abstract
We describe an efficient and flexible generation-scavenging garbage collector toolkit. Our methodology succeeds in systems where the cost associated with any single operation is bounded by a small time constant. The collector maintains several "generations" of objects. Newly created objects are all put in the "youngest generation" and when the space allocated for that generation is full, the collector uses the root set to reclaim dead objects from the youngest generation only, leaving the older generations untouched. Objects that survive after several collections of the youngest generation are "promoted" to the older generation. In this way, the collector assures that recently created regions contain high percentages of garbage and have garbage collected frequently. The framework has been implemented in a library and tested against formidable real world applications. Hence the proposed system eliminates the possibility of storage-management bugs, making the design of complex, object-oriented systems much easier. This can be accomplished with almost no change to the language itself and only small changes to existing implementations, while retaining compatibility with existing class libraries.