F. Lockwood Morris
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.
- 1 Cheney, C.J. A nonrecursive list compacting algorithm. Comm. ACM 13, 11 (Nov. 1970), 677-678. Google Scholar
Digital Library
- 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.Google Scholar
- 3 Fenichel, R.R., and Yochelson, J.C. A LISP garbage collector for virtual-memory computer systems. Comm. ACM 12, 11 (Nov. 1969), 611-612. Google ScholarDigital Library
- 4 Hansen, W.J. Compact list representation: Definition, garbage collection and system implementation. Comm. ACM 12, 9 (Sept. 1969), 499-507. Google ScholarDigital Library
- 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.Google Scholar
- 6 Knuth, D.E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms. Addison-Wesley, Reading, Mass., 1968, p. 421, Ex. 2.3.5.9 and p. 454, Ex. 2.5.33. Google ScholarDigital Library
- 7 Minsky, M.L. A LISP garbage collector using serial secondary storage. M.I.T. Artif. InteU. Memo No. 58 (rev.), M.I.T., Cambridge, Mass., Dec. 1963. Google ScholarDigital Library
- 8 Reynolds, J.C. Description of garbage collection in the COGENT programming system. Private communication.Google Scholar
- 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.Google Scholar
- 10 Steele, G.L. Multiprocessing Compactifying Garbage Collection. Comm. ACM 18, 9 (Sept. 1975), 495-508. Google ScholarDigital Library
- 11 Wegbreit, B. A generalized compactifying garbage collector. Computer J. 15, 3 (Aug. 1972), 204-208.Google ScholarCross Ref
Index Terms
- A time- and space-efficient garbage compaction algorithm
Recommendations
Multiprocessing compactifying garbage collection
Algorithms for a multiprocessing compactifying garbage collector are presented and discussed. The simple case of two processors, one performing LISP-like list operations and the other performing garbage collection continuously, is thoroughly examined. ...
Analysis of an algorithm for real time garbage collection
A real time garbage collection system avoids suspending the operations of a list processor for the long times that garbage collection normally requires by performing garbage collection on a second processor in parallel with list processing operations, ...
Comments