Comparison of Compacting Algorithms for Garbage Collection

Abstract

The relative efficiencies of four compactors of varisized cells are estimated by constructing their timeformulas.These are symbolic formulas expressing execution times as functions of the time to perform common, elementary operations such as assignment, addition, subscripting, and loop overhead.By binding the variables to numeric values corresponding to a specific machine one can estimate program execution times without resorting to empirical tests.The first of the compactors (Lisp 2) requires additional storage for pointer readjustment.The second (based on the work of Haddon and Waite) attempts to reduce these storage requirements at the expense of processing time.The last two (Morris' and Jonkers') are recently proposed compactors that require minimal additional storage and that update pointers by first threading them into linear lists.The paper provides unified descriptions of the algorithms and presents curves expressing the relative efficiencies of the compactors when run on a specific machine (PDP-10).It is straightforward to modify the given formulas to estimate compactors' efficiencies when run on other computers.