An efficient, incremental, automatic garbage collector

ABSTRACT

This paper describes a new way of solving the storage reclamation problem for a system such as Lisp that allocates storage automatically from a heap, and does not require the programmer to give any indication that particular items are no longer useful or accessible. A reference count scheme for reclaiming non-self-referential structures, and a linearizing, compacting, copying scheme to reorganize all storage at the users discretion are proposed. The algorithms are designed to work well in systems which use multiple levels of storage, and large virtual address space. They depend on the fact that most cells are referenced exactly once, and that reference counts need only be accurate when storage is about to be reclaimed. A transaction file stores changes to reference counts, and a multiple reference table stores the count for items which are referenced more than once.

REFERENCES

• 1: Bobrow, D.G. Storage management in LISP. In Symbol Manpulation Languages and Techniques, D.G. Bobrow, Ed., North-Holland Pub. Co., Amsterdam, 1968.
• 2: Daniel G. Bobrow, A note on hash linking, Communications of the ACM, v.18 n.7, p.413-415, July 1975 [doi>10.1145/360881.360920]
• 3: Daniel G. Bobrow , Daniel L. Murphy, Structure of a LISP system using two-level storage, Communications of the ACM, v.10 n.3, p.155-159, March 1967 [doi>10.1145/363162.363185]
• 4: Douglas W. Clark , C. Cordell Green, An empirical study of list structure in Lisp, Communications of the ACM, v.20 n.2, p.78-87, Feb. 1977 [doi>10.1145/359423.359427]
• 5: Robert R. Fenichel , Jerome C. Yochelson, A LISP garbage-collector for virtual-memory computer systems, Communications of the ACM, v.12 n.11, p.611-612, Nov. 1969 [doi>10.1145/363269.363280]
• 6: Marvin Minsky, A LISP Garbage Collector Algorithm Using Serial Secondary Storage, Massachusetts Institute of Technology, Cambridge, MA, 1963
• 7: Van der Poel, W.L. A manual of HISP for the PDP-9. U. of Delft, Delft, Netherlands, 1974.

INDEX TERMS

Keywords:
Lisp, garbage collection, storage management