Research Seminar - March 31, 2000

Abstract

In this talk I will describe an efficient technique for supporting Baker's incremental garbage collection algorithm in language implementations that support dynamic dispatching. Incremental collectors such as Baker's eliminate the stop/go execution associated with bulk copying collection algorithms, allowing the system to place an upper bound on the time taken to perform a store operation.

I will describe a completely portable implementation of the scheme in v4.01 of the Glasgow Haskell Compiler (GHC) and will also discuss how the scheme might be adapted for dynamic object-oriented programming languages such as Java.

Experiments with a range of benchmark programs show that Baker's algorithm can be implemented in GHC with negligible overheads on program execution time (less than 4% average on the benchmarks tested) whilst yielding sub-millisecond average pause times. This represents a substantial improvement on other published implementations of Baker's algorithm, although some care is required when making comparisons, as will be discussed.

This is joint work with Lyndon While at UWA, Simon Peyton Jones and Simon Marlow at Microsoft Research, Cambridge, and Andrew Cheadle, formerly at Imperial College, but now at Telcordia NJ.