Dual-Mode Garbage Collection

Patrick M Sansom
Depat. of Computing Science,
University of Glasgow,
Glasgow, Scotland
[email protected]

December 1991

Abstract

The garbage collector presented in this paper makes use of two well known compaction garbage collection algorithms with very different performance characteristics: Cheney's two-space copying collector and Jonker's sliding compaction collector. We propose a scheme which allows either collector to be used. The run-time memory requirements of the program being executed are used to determine the most appropriate collector. This enables us to achieve a fast collector for heap requirements less than half of the heap memory but allows the heap utilization to increase beyond this threshold. Using these ideas we develop a particularly attractive extension to Appel's generational collector.

We also describe a particularly fast implementation of the garbage collector which avoids interpreting the structure and current state of closures by attaching specific code to heap objects. This code knows the structure and current state of the object and performs the appropriate actions without having to test any flag or arity fields. The result is an implementation of these collection schemes which does not require any additional storage to be associated with the heap objects.

(An earlier version of this paper appeared in Proceedings of the Workshop on the Parallel Implementation of Functional Languages, Southampton, Tecnical Report CSTR 91-07, Dept. of Computing Science, University of Southampton, June 1991.)

1 Introduction

Many programming environments have a heap storage management system with automatic garbage collection. In these systems storage that is no longer referenced from outside the heap is automatically reused. It is now widely accepted that, for good performance, it is essential to allocate storage from a contiguous block of memory, rather than a free list (Appel [1987]). It is also highly convenient when allocating variable-sized objects. To be able to do this the garbage collector is required to compact objects into one block, so the remaining memory is left in a contiguous block ready for allocation.

The main contribution of this paper is to present a collection scheme which brings together two very different collectors: Cheney's two-space collector (Cheney [1970]) and Jonkers' compacting collector (Jonkers [1979]), in a way that utilises the desirable characteristics of both