A comparison of three garbage collection algorithms

Abstract. The running cost of garbage collection is studied as a function of the amount of available store. A performance model originally proposed by Hoare is modified to support experiments with three garbage collection methods: reference count, mark/scan and two-space copy. By also taking the boundary effects into account, we show that adding more store to a list processing system with a non-reference counting garbagecollector does not always make it run faster. We present an explanation for this anomaly in the behaviour of garbage collection algorithms and discuss some of its consequences.