Combining Single-Space and Two-Space

Compacting Garbage Collectors?

Patrick M Sansomy

University of Glasgow

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 single-space 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.

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 [1]. 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.

? This paper appears in Funtional Programming, Glasgow 1991, Workshops in Computing, Springer Verlag, 1992. A more detailed version of this paper, entitled Dual-Mode Garbage Collection", may be found in [8].
y Author's address: Department of Computing Science, The University, Glasgow, G12 8QQ, UK. E-mail: [email protected]