A time- and space-efficient garbage compaction algorithm

ABSTRACT

Given an area of storage containing scattered, marked nodes of differing sizes, one may wish to rearrange them into a compact mass at one end of the area while revising all pointers to marked nodes to show their new locations. An algorithm is described here which accomplishes this task in linear time relative to the size of the storage area, and in a space of the order of one bit for each pointer. The algorithm operates by reversibly encoding the situation (that a collection of locations point to a single location) by a linear list, emanating from the pointed-to location, passing through the pointing locations, and terminating with the pointed-to location's transplanted contents.

REFERENCES

• 1: C. J. Cheney, A nonrecursive list compacting algorithm, Communications of the ACM, v.13 n.11, p.677-678, Nov 1970 [doi>10.1145/362790.362798]
• 2: Conrad, W.R. A compactifying garbage collector for ECL's nonhomogeneous heap. Tech. Rep. 2-74, Ctr. for Res. in Compt. Tech., Harvard U., Cambridge, Mass., Feb. 1974.
• 3: 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]
• 4: Wilfred J. Hansen, Compact list representation: definition, garbage collection, and system implementation, Communications of the ACM, v.12 n.9, p.499-507, Sept. 1969 [doi>10.1145/363219.363225]
• 5: Hart, T.P., and Evans, T.G. Notes on implementing LISP for the M-460 computer. In The Programming Language LISP: Its Operation and Applications, Berkeley, E. C. and Bobrow, D. G., Eds., Information International, Cambridge, Mass., 1964, pp. 191-203.
• 6: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 7: Marvin Minsky, A LISP Garbage Collector Algorithm Using Serial Secondary Storage, Massachusetts Institute of Technology, Cambridge, MA, 1963
• 8: Reynolds, J.C. Description of garbage collection in the COGENT programming system. Private communication.
• 9: Saunders, R.A. The LISP system for the Q-32 computer. In The Programming Language LISP: Its Operation and Applications, Berkeley, E. C. and Bobrow, D. G., Eds., Information International, Cambridge, Mass., 1964, pp. 220-231.
• 10: Guy L. Steele, Jr., Multiprocessing compactifying garbage collection, Communications of the ACM, v.18 n.9, p.495-508, Sept. 1975 [doi>10.1145/361002.361005]
• 11: Wegbreit, B. A generalized compactifying garbage collector. Computer J. 15, 3 (Aug. 1972), 204-208.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Garbage collection

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

  E. Data

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
compactification, compaction, data structures, free storage, garbage collection, list processing, pointers, record structures, relocation, storage allocation, storage reclamation