Henry G. Baker
Abstract
A real-time list processing system is one in which the time required by the elementary list operations (e.g. CONS, CAR, CDR, RPLACA, RPLACD, EQ, and ATOM in LISP) is bounded by a (small) constant. Classical implementations of list processing systems lack this property because allocating a list cell from the heap may cause a garbage collection, which process requires time proportional to the heap size to finish. A real-time list processing system is presented which continuously reclaims garbage, including directed cycles, while linearizing and compacting the accessible cells into contiguous locations to avoid fragmenting the free storage pool. The program is small and requires no time-sharing interrupts, making it suitable for microcode. Finally, the system requires the same average time, and not more than twice the space, of a classical implementation, and those space requirements can be reduced to approximately classical proportions by compact list representation. Arrays of different sizes, a program stack, and hash linking are simple extensions to our system, and reference counting is found to be inferior for many applications.
- 1 Arnborg, S. Storage administration in a virtual memory SIMULA system. BIT 12 (1972), 125-141.Google Scholar
Cross Ref
- 2 Arnborg, S. Optimal memory management in a system with garbage collection. BIT 14 (1974), 375-381.Google ScholarCross Ref
- 3 Barbacci, M. A LISP Processor for C.ai. Memo CMU-CS-71-103, Comptr. Sci. Dept., Carnegie-Mellon. Pittsburgh, Pa., 1971.Google Scholar
- 4 Bennett, C.H. Logical reversibility of computation. IBM J. Res. Develop. 17 (1973), 525.Google ScholarDigital Library
- 5 Birtwistle, G.M., Dahl, O.-J., Myhrhaug, B, and Nygaard, K. Simula Begin. Auerbach, Philadelphia, Pa., 1973. Google ScholarDigital Library
- 6 Bishop, P.B. Garbage collection in a very large address space. Working Paper l 11, M.I.T.A.I. Lab., M.I.T., Sept. 1975.Google Scholar
- 7 Bishop, P.B. Computer systems with a very large address space and garbage collection. Ph.D. Th., TR-178, MIT Lab. for Compter Sci., Cambridge, Mass., May 1977. Forthcoming.Google Scholar
- 8 Bobrow, D.G. and Wegbreit, B. A model and stack implementation of multiple environments. Comm. A CM 16, 10 (Oct. 1973), 591-603. Google ScholarDigital Library
- 9 Bobrow, D.G. A note on hash linking. Comm. ACM 18, 7 (July 1975), 413--415. Google ScholarDigital Library
- 10 Campbell, J.A. Optimal use of storage in a simple model of garbage collection. Inform. Processing Letters 3, No. 2 (Nov., 1974), 37-38.Google ScholarCross Ref
- 11 Cheney, C.J. A nonrecursive list compacting algorithm. Comm. ACM 13, 11 (Nov. 1970), 677-678. Google ScholarDigital Library
- 12 Clark, D.W., and Green, C.C. An empirical study of list structure in LISP. Comm. ACM 20, 2 (Feb. 1977), 78-87. Google ScholarDigital Library
- 13 Collins, G.E. A method for overlapping and erasure of lists. Comm. ACM 3, 12 (Dec. 1960), 655--657. Google ScholarDigital Library
- 14 Dalai, O.-J., and Nygaard, K. SIMULA--an ALGOL-based simulation language. Comm. ACM 9, 9 (Sept. 1966), 671-678. Google ScholarDigital Library
- 15 Deutsch, L.P., and Bobrow, D.G. An efficient, incremental, automatic garbage collector. Comm. ACM 19, 9 (Sept. 1976), 522-526. Google ScholarDigital Library
- 16 Dijkstra, E.W., Lamport, L., Martin, A.J., Scholten, C. S., Steffens, E.F.M. On-the-fly garbage collection: An exercise in cooperation. E.W. Dijkstra note EWD496, June 1975.Google Scholar
- 17 Dijkstra, E.W. After many a sobering experience. E.W. Dijkstra note EWD500.Google Scholar
- 18 Fenichel, R.R., and Yoehelson, J.C. A LISP garbage-coUector for virtual-memory computer systems. Comm. ACM 12, 11 (Nov. 1969), 611-612. Google ScholarDigital Library
- 19 Greenblatt, R. LISP Machine Progress Report memo 444, A.I. Lab., M.I.T., Cambridge, Mass., Aug. 1977.Google Scholar
- 20 Greenblatt, R. Private communication, Feb. ! 977.Google Scholar
- 21 Hoare, C.A.R. Optimization of store size for garbage collection. Inform. Processing Letters 2 (1974), 165-166.Google ScholarCross Ref
- 22 Knuth, D.E. The Art of Computer Programming, Vol. 1: FundamentalAlgorithms. Addison-Wesley, Reading, Mass. 1968. Google ScholarDigital Library
- 23 Lamport, L. Garbage collection with multiple processes: An exercise in parallelism. CA-7602-25 ! 1, Mass. Computer Associates, Wakefield, Mass., Feb. 1976.Google Scholar
- 24 Lamport, L. On-the-fly garbage collection: Once more with rigor. CA-7508-1611, Mass. Computer Associates, Wakefield, Mass., Aug. 1975.Google Scholar
- 25 McCarthy, J., et al. LISP 1.5 Programmer's Manual. M.I.T. Press, Cambridge, Mass., 1965. Google ScholarDigital Library
- 26 Minsky, M.L. A LISP garbage collector algorithm using serial secondary storage. Memo 58, M.I.T.A.I. Lab., M.I.T., Cambridge, Mass., Oct. 1963. Google ScholarDigital Library
- 27 Moon, D.A. MACLISP Reference Manual. Project MAC, M.I.T., Cambridge, Mass., December 1975.Google Scholar
- 28 Muller, K.G. On the feasibility of concurrent garbage collection. Ph.D. Th., Tech. Hogeschool Delft, The Netherlands, March 1976 (in English).Google Scholar
- 29 Schonhage, A. Real-time simulation of multidimensional Turing machines by storage modification machines. TM-37, Project MAC, M.I.T., Cambridge, Mass., Dec. 1973. Google ScholarDigital Library
- 30 Steele, G.L. Jr. Multiprocessing compactifying garbage collection. Comm. ACM 18, 9 (Sept. 1975), 495-508. Google ScholarDigital Library
- 31 Steele, G.L. Jr. Private communication, March 1977.Google Scholar
- 32 Teitelman, W., et al. INTERLISP Reference Manual. Xerox Palo Alto Res. Ctr., Palo Alto, Calif., 1974.Google Scholar
- 33 Wadler, P.L. Analysis of an algorithm for real-time garbage collection. Comm. ACM 19, 9 (Sept. 1976), 491-500. Google ScholarDigital Library
- 34 Weizenbaum, J. Symmetric list processor. Comm. A CM 6, 9 (Sept. 1963), 524--544. Google ScholarDigital Library
Index Terms
- List processing in real time on a serial computer
Recommendations
A real-time garbage collector based on the lifetimes of objects
In previous heap storage systems, the cost of creating objects and garbage collection is independent of the lifetime of the object. Since objects with short lifetimes account for a large portion of storage use, it is worth optimizing a garbage collector ...
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