article

Free access

A real-time garbage collector based on the lifetimes of objects

Authors:

Henry Lieberman,

Carl HewittAuthors Info & Claims

Communications of the ACM, Volume 26, Issue 6

Pages 419 - 429

https://doi.org/10.1145/358141.358147

Published: 01 June 1983 Publication History

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.

References

[1]

Allen, J. Anatomy of Lisp. McGraw-Hill, New York, 1979.

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.

[3]

Baker, H. Actor systems for real time computation. Tech. Rept. TR-197, MIT Lab. for Computer Science, Cambridge, Mass., 1978.

Digital Library

[4]

Baker, H.G. List processing in real time on a serial computer. Commun. ACM 21, 4 (April 1978) 280-294.

Digital Library

[5]

Baker, H. The paging behavior of the Cheney list copying algorithm. Tech. Note 1, Symbolics, Inc., Cambridge, Mass., 1980.

[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.

[7]

Bobrow, D., and Winograd, T. An overview of KRL: A language for knowledge representation. Cognitive Science 1, (1977).

[8]

Burstall, R.M., and Darlington, J.L. A transformation system for developing recursive programs. I. ACM 24, 1 (Jan. 1977), 24-77.

Digital 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.

[10]

Dautsch, LP., and Bobrow, D.G. An efficient, incremental, automatic garbage collector. Commun. ACM 19, 9 (Sept. 1976), 522-526.

Digital Library

[11]

Dijkstra, E., Lamport, Let el. On-the-fly garbage collection: An exercise in cooperation. Commun. ACM 21, 11 (Nov. 1978}, 966-975.

Digital Library

[12]

Friedman, D., and Wise, D. Garbage collecting a heap which includes a scatter table. Inf. Process. Lett. 5, 6 {Dec. 1976).

[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.

Digital Library

[14]

Guibas, L., and Wyatt, D. Compilation and delayed evaluation in APL. Presented at the 5th ACM Conf. Principles of Programming Languages, 1978.

Digital 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.

[16]

Hewitt, C. The Apiary network architecture for knowledgeable systems. In Prec. 1980 Lisp Conf., Stanford Univ., Stanford, Calif., 1980.

Digital Library

[17]

Ingalls, D. The smalhalk-76 programming system: Design and implementation. Presented at the 5th ACM Conf. Principles of Programming Langnages, 1978.

Digital Library

[18]

Kornfeld, W. Ether--A parallel problem solving system. Presented at the 6th Joint Conf. Artificial Intelligence, Tokyo, Japan, Aug. 1979.

[19]

Knnth, D. Garbage collection in real time. Class handout for course CS144C, Stanford Univ., Stanford, Calif., Spring 1981.

[20]

Liebemmn, H. A preview of act 1. Al Memo 625, M1T Artificial Intelligence Lab., Cambridge, Mass., 1980.

[21]

Lucassen, J.M. Improvements to the Liebarman-Hewitt garbage collector. Term Paper for MIT course 6.845, May 1981.

[22]

Moon, D. MacLisp Reference Manual. MIT Lab. for Computer Science, Cambridge, Mass., 1980.

[23]

Moses, J. The function of Function In Lisp. Memo, ACM SIGSAM Bull., July, 1970.

Digital Library

[24]

Snyder, A. An object-oriented machine architecture. Tech. Rept. TR-209, MIT Lab for Computer Science, Cambridge, Mass., 1979.

[25]

Weinreh, D., and Moon, D. Lisp Machine Manual. MIT Artificial Intelligence Lab., Cambridge, Mass., 1978.

Digital Library

[26]

White, J. Memory management in a gigantic Lisp environment, or GC considered harmful. In Proc. 1980 Lisp Conf., Stanford, Calif.

Digital Library

Cited By

Tavakolisomeh SShimchenko MÖsterlund EBruno RFerreira PWrigstad TBruno RMoss E(2023)Heap Size Adjustment with CPU ControlProceedings of the 20th ACM SIGPLAN International Conference on Managed Programming Languages and Runtimes10.1145/3617651.3622988(114-128)Online publication date: 19-Oct-2023
https://dl.acm.org/doi/10.1145/3617651.3622988
Tabassum FIslam MUr Rahman MMajumder J(2023)A Comprehensive Study on Different Optimizations of Pure Reference Counting Garbage Collectors2023 International Conference on Computational Intelligence, Networks and Security (ICCINS)10.1109/ICCINS58907.2023.10450100(1-6)Online publication date: 22-Dec-2023
https://doi.org/10.1109/ICCINS58907.2023.10450100
Tavakolisomeh SBruno RFerreira P(2023)BestGC: An Automatic GC SelectorIEEE Access10.1109/ACCESS.2023.329439811(72357-72373)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3294398
Show More Cited By

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 computing

Generational 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. ...
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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Communications of the ACM

Communications of the ACM Volume 26, Issue 6

June 1983

54 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/358141

Editor:
Peter J. Denning
NASA Ames Research Center, Moffett Field, CA

Issue’s Table of Contents

Copyright © 1983 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1983

Published in CACM Volume 26, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

486
Total Citations
View Citations
2,546
Total Downloads

Downloads (Last 12 months)308
Downloads (Last 6 weeks)44

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tavakolisomeh SShimchenko MÖsterlund EBruno RFerreira PWrigstad TBruno RMoss E(2023)Heap Size Adjustment with CPU ControlProceedings of the 20th ACM SIGPLAN International Conference on Managed Programming Languages and Runtimes10.1145/3617651.3622988(114-128)Online publication date: 19-Oct-2023
https://dl.acm.org/doi/10.1145/3617651.3622988
Tabassum FIslam MUr Rahman MMajumder J(2023)A Comprehensive Study on Different Optimizations of Pure Reference Counting Garbage Collectors2023 International Conference on Computational Intelligence, Networks and Security (ICCINS)10.1109/ICCINS58907.2023.10450100(1-6)Online publication date: 22-Dec-2023
https://doi.org/10.1109/ICCINS58907.2023.10450100
Tavakolisomeh SBruno RFerreira P(2023)BestGC: An Automatic GC SelectorIEEE Access10.1109/ACCESS.2023.329439811(72357-72373)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3294398
Chen JJiang TYu DHu H(2023)Pattern-based circular reference detection in PythonScience of Computer Programming10.1016/j.scico.2023.102932227(102932)Online publication date: Apr-2023
https://doi.org/10.1016/j.scico.2023.102932
(2023)BibliographyEngineering a Compiler10.1016/B978-0-12-815412-0.00023-1(793-813)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00023-1
Cooper KTorczon L(2023)Implementing ProceduresEngineering a Compiler10.1016/B978-0-12-815412-0.00012-7(275-325)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00012-7
Zhao WBlackburn SMcKinley KJhala RDillig I(2022)Low-latency, high-throughput garbage collectionProceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3519939.3523440(76-91)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519939.3523440
Sarkar AKrook RSvensson BSheeran MKuchen HSinger J(2021)Higher-order concurrency for microcontrollersProceedings of the 18th ACM SIGPLAN International Conference on Managed Programming Languages and Runtimes10.1145/3475738.3480716(26-35)Online publication date: 29-Sep-2021
https://dl.acm.org/doi/10.1145/3475738.3480716
Mahdavi MAbedjan Z(2020)BaranProceedings of the VLDB Endowment10.14778/3407790.340780113:12(1948-1961)Online publication date: 14-Sep-2020
https://dl.acm.org/doi/10.14778/3407790.3407801
Jain AHorowitz ASchoeller FLeigh SMaes PSra M(2020)Designing Interactions Beyond Conscious ControlProceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies10.1145/34118294:3(1-23)Online publication date: 4-Sep-2020
https://dl.acm.org/doi/10.1145/3411829
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents