Henry Lieberman
Abstract
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 to reclaim storage for these objects more quickly. The garbage collector should spend proportionately less effort reclaiming objects with longer lifetimes. We present a garbage collection algorithm that (1) makes storage for short-lived objects cheaper than storage for long-lived objects, (2) that operates in real time—object creation and access times are bounded, (3) increases locality of reference, for better virtual memory performance, (4) works well with multiple processors and a large address space.
- 1 Allen, J. Anatomy of Lisp. McGraw-Hill, New York, 1979. Google Scholar
Digital Library
- 2 Attardi, G., and Hewitt, C. Knowledge embedding in the description system OMEGA. Presented at the American Association for Artificial Intelligence Conf., Stanford Univ., Stanford, Calif., 1980.Google Scholar
- 3 Baker, H. Actor systems for real time computation. Tech. Rept. TR-197, MIT Lab. for Computer Science, Cambridge, Mass., 1978. Google ScholarDigital Library
- 4 Baker, H.G. List processing in real time on a serial computer. Commun. ACM 21, 4 (April 1978) 280-294. Google ScholarDigital Library
- 5 Baker, H. The paging behavior of the Cheney list copying algorithm. Tech. Note 1, Symbolics, Inc., Cambridge, Mass., 1980.Google Scholar
- 6 Bishop, P. Computer systems with a very large address space and garbage collection. Tech. Rept. TR-178, MIT Lab. for Computer Science, Cambridge, Mass., May 1977.Google Scholar
- 7 Bobrow, D., and Winograd, T. An overview of KRL: A language for knowledge representation. Cognitive Science 1, (1977).Google Scholar
- 8 Burstall, R.M., and Darlington, J.L. A transformation system for developing recursive programs. I. ACM 24, 1 (Jan. 1977), 24-77. Google ScholarDigital Library
- 9 deKleer, J., Doyle, J., Rich, C., Steele, G., and Sussman, G. AMORD--A deductive procedure system. Memo 435, MIT Artificial Intelligence Lab., Cambridge, Mass., Jan. 1978.Google Scholar
- 10 Dautsch, LP., and Bobrow, D.G. An efficient, incremental, automatic garbage collector. Commun. ACM 19, 9 (Sept. 1976), 522-526. Google ScholarDigital Library
- 11 Dijkstra, E., Lamport, Let el. On-the-fly garbage collection: An exercise in cooperation. Commun. ACM 21, 11 (Nov. 1978}, 966-975. Google ScholarDigital Library
- 12 Friedman, D., and Wise, D. Garbage collecting a heap which includes a scatter table. Inf. Process. Lett. 5, 6 {Dec. 1976).Google Scholar
- 13 Greenblatt, R., Knight, T., Holloway, J., and Moon, D. A Lisp Machine. Presented at the Workshop on Computer Architecture for Non- Numeric Processing. Pacific Grove, Calif., March 1980. Google ScholarDigital Library
- 14 Guibas, L., and Wyatt, D. Compilation and delayed evaluation in APL. Presented at the 5th ACM Conf. Principles of Programming Languages, 1978. Google ScholarDigital Library
- 15 Hewitt, C. Viewing control structures as patterns of passing messages. In P. Winston and R. Brown (F, ds.), Artificial Intelligence: An MIT Perspective, MIT Press, Cambridge, Mass., 1979.Google Scholar
- 16 Hewitt, C. The Apiary network architecture for knowledgeable systems. In Prec. 1980 Lisp Conf., Stanford Univ., Stanford, Calif., 1980. Google ScholarDigital Library
- 17 Ingalls, D. The smalhalk-76 programming system: Design and implementation. Presented at the 5th ACM Conf. Principles of Programming Langnages, 1978. Google ScholarDigital Library
- 18 Kornfeld, W. Ether--A parallel problem solving system. Presented at the 6th Joint Conf. Artificial Intelligence, Tokyo, Japan, Aug. 1979.Google Scholar
- 19 Knnth, D. Garbage collection in real time. Class handout for course CS144C, Stanford Univ., Stanford, Calif., Spring 1981.Google Scholar
- 20 Liebemmn, H. A preview of act 1. Al Memo 625, M1T Artificial Intelligence Lab., Cambridge, Mass., 1980.Google Scholar
- 21 Lucassen, J.M. Improvements to the Liebarman-Hewitt garbage collector. Term Paper for MIT course 6.845, May 1981.Google Scholar
- 22 Moon, D. MacLisp Reference Manual. MIT Lab. for Computer Science, Cambridge, Mass., 1980.Google Scholar
- 23 Moses, J. The function of Function In Lisp. Memo, ACM SIGSAM Bull., July, 1970. Google ScholarDigital Library
- 24 Snyder, A. An object-oriented machine architecture. Tech. Rept. TR-209, MIT Lab for Computer Science, Cambridge, Mass., 1979.Google Scholar
- 25 Weinreh, D., and Moon, D. Lisp Machine Manual. MIT Artificial Intelligence Lab., Cambridge, Mass., 1978. Google ScholarDigital Library
- 26 White, J. Memory management in a gigantic Lisp environment, or GC considered harmful. In Proc. 1980 Lisp Conf., Stanford, Calif. Google ScholarDigital Library
Index Terms
- A real-time garbage collector based on the lifetimes of objects
Recommendations
Exploiting the efficiency of generational algorithms for hardware-supported real-time garbage collection
SAC '07: Proceedings of the 2007 ACM symposium on Applied computingGenerational garbage collectors are more efficient than their non-generational counterparts. Unfortunately, however, generational algorithms require both write barriers and write barrier handlers and therefore degrade worst-case performance.
In this ...
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. ...
Real-time replication garbage collection
We have implemented the first copying garbage collector that permits continuous unimpeded mutator access to the original objects during copying. The garbage collector incrementally replicates all accessible objects and uses a mutation log to bring the ...
Comments