A comprehensive analytical model for garbage collection algorithms

1 August 1991

journal article
Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices

Vol. 26 (8) , 50-59
https://doi.org/10.1145/122598.122602

Abstract

We present an analytical model that allows to compare all known garbage collection (GC) algorithms w.r.t. various performance measures. The overhead functions are natural and accurate ; natural in the sense that they are given in terms of easy to measure and tune parameters, accurate in the sense that they account for all relevant sources of time and space overhead of the different algorithms. Space overhead accounted for includes mark bits, mark stack, reference count bits/tables, entry tables for area-GC, object tables etc. as well as storage fragmentation. Time overhead components are e.g. time to mark/scan/copy nodes, update reference counts, check for forwarding pointers, synchronization costs etc.

This publication has 3 references indexed in Scilit:

Generation Scavenging
Published by Association for Computing Machinery (ACM) ,1984
A real-time garbage collector based on the lifetimes of objects
Communications of the ACM, 1983
Garbage Collection of Linked Data Structures
ACM Computing Surveys, 1981