article

Free access

Space efficient conservative garbage collection

Author:

Hans-Juergen BoehmAuthors Info & Claims

ACM SIGPLAN Notices, Volume 28, Issue 6

Pages 197 - 206

https://doi.org/10.1145/173262.155109

Published: 01 June 1993 Publication History

Abstract

We call a garbage collector conservative if it has only partial information about the location of pointers, and is thus forced to treat arbitrary bit patterns as though they might be pointers, in at least some cases. We show that some very inexpensive, but previously unused techniques can have dramatic impact on the effectiveness of conservative garbage collectors in reclaiming memory. Our most significant observation is that static data that appears to point to the heap should not result in misidentified references to the heap. The garbage collector has enough information to allocate around such references. We also observe that programming style has a significant impact on the amount of spuriously retained storage, typically even if the collector is not terribly conservative. Some fairly common C and C++ programming style significantly decrease the effectiveness of any garbage collector. These observations suffice to explain some of the different assessments of conservative collection that have appeared in the literature.

References

[1]

Standard X3.159-1989, American National $tan. dard for Information Systems - Programming Language - C, American National Standards Institute, Inc.

[2]

Atkinson, Russ, Alan Demers, Carl Hauser, Christian Jacobi, Peter Kessler, and Mark Weiser, "Experiences Creating a Portable Cedar", Proceedings of the A CM SIGPLAN '89 Conference on Programming Language Design and Implementation, $IG- PLAN Notices 2j, 7 (July 1989), pp. 322-329.

Digital Library

[3]

Bartlett, Joel F. "Compacting garbage collection with ambiguous roots", Lisp Pointers 1, 6 (April- June 1988), pp. 3-12.

[4]

Bartlett, Joel F., Scheme -> C a Portable Schemeto-C Compiler, WRL Research Report 89/1, Digital Equipment Corporation Western Research Laboratory, January 1989.

[5]

Bartlett, Joel F., Mostly Copying Garbage Collection Picks Up Generations and C++, Technical Report TN-12, Digital Equipment Corporation Western Research Laboratory, October 1989.

[6]

Bekkers, Y., O. Ridoux, and L. Ungaro, "Dynamic Memory Management for Sequential Logic Programming Languages, Proceedings of the International Workshop on Memory Management, St. Malo, France, September 1992, Springer LNCS 637, pp. 82-102.

Digital Library

[7]

Boehm, Hans-J., and David Chase, "A Proposal for Garbage-Collector-Safe C Compilation", The Journal of C Language Translation d, 2 (December 1992), pp. 126-141.

[8]

Boehm, H., A. Demers, and S. Shenker,"Mostly Parallel Garbage Collection", Proceedings of the A CM $IGPLAN '9I Conference on Programming Language Design and Implementation, SIGPLAN Notices 26, 6 (June 1991), pp. 157-164.

Digital Library

[9]

Boehm, Hans-J. and Mark Weiser, "Garbage collection in an uncooperative environment", Software Practice ~4 E~perience 18, 9 (Sept. 1988), pp. 807- 820.

Digital Library

[10]

Chailloux, Emmanuel, "A Conservative Garbage Collector with Ambiguous Roots for Static Typechecking Languages", Proceedings of the International Workshop on Memory Management, St. Malo, France, September 1992, Springer LNCS 637, pp. 218-229.

Digital Library

[11]

Cridlig, Regis, "An Optimizing ML to C Compiler'', A CM SIGPLAN Workshop on ML and its Applications, San Francisco, June 1992, David MacQueen, chair.

[12]

A. Demers, M. Weiser, B. Hayes, H. Boehm, D. Bobrow, S. Shenker, "Combining Generational and Conservative Garbage Collection: Framework and Implementations", Proceedings of the Seventeenth Annual A CM Symposium on Principles of Programming Languages, January 1990, pp. 261-269.

Digital Library

[13]

Detlefs, David L., "Concurrent Garbage Collection for C++", in Advanced Programming Language implementation, Peter Lee, ed., MIT Press, 1991.

[14]

Edelson, Daniel, "A Mark-and-Sweep Collector for C++", Conference Record of the Nineteenth Annual A CM $I(TPLAN-SIGA CT Symposium on Principles of Programming Languages, Albuquerque, New Mexico, January 1992, pp. 51-58.

Digital Library

[15]

Goldberg, Benjamin, and Michael Gloger, "Polymorphic Type Reconstruction for Garbage Collection without Tags", Proceedings of the 199~ ACM Conference on Lisp and Functional Programming, pp. 53-65.

Digital Library

[16]

Hastings, Reed, and Bob Joyce, "Fast Detection of Memory Leaks and Access Errors", Proceedings of the Winter '92 USENIX conference, pp. 125-136.

[17]

Omohundro, Stephen M., The Sather Language, ICSI, Berkeley, 1991.

[18]

Rose, John R., and Hans Muller, "Integrating the Scheme and C languages", Proceedings of the 1992 A CM Conference on Lisp and Functional Programming, pp. 247-259.

Digital Library

[19]

Rovner, Paul, "On Adding Garbage Collection and Runtime Types to a Strongly-Typed Statically Checked, Concurrent Language", Technical Report CSL-84-7, Xerox Palo Alto Research Center, Palo Alto, CA, July 1985.

[20]

Ungar, David M., "Generation Scavenging: A Non- Disruptive High Performance Storage Reclamation Algorithm", A CM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, SIGPLAN Notices 19, 5 (May 1984), pp. 157-167.

Digital Library

[21]

Schelter, W. F., and M. Ballantyne, "Kyoto Common Lisp", AI Expert 3 3 (1988), pp. 75-77.

Digital Library

[22]

Weiser, Mark, Alan Demers, and Carl Hauser, "The Portable Common Runtime Approach to interoperability", Proceedings 13th A CM Symposium on Operating Systems Principles, December 1989.

Digital Library

[23]

Wentworth, E. P., "Pitfalls of Conservative Garbage Collection", Software Practice ~4 Emperience 20, 7 (July 1990)pp. 719-727.

Digital Library

[24]

Wilson, Paul R., "Uniprocessor Garbage Collection Techniques", Proceedings of the international Workshop on Memory Management, St. Malo, France, September 1992, Springer LNCS 637, pp. 1-42.

Digital Library

[25]

Zorn, Benjamin, "The Measured Cost of Conservative Garbage Collection", University of Colorado at Boulder, Department of Computer Science Technical Report CU-CS-573-92.

Cited By

Frisella MSanchez SSchwarzkopf MBaumann ACrooks NSchwarzkopf M(2023)Towards Increased Datacenter Efficiency with Soft MemoryProceedings of the 19th Workshop on Hot Topics in Operating Systems10.1145/3593856.3595902(127-134)Online publication date: 22-Jun-2023
https://dl.acm.org/doi/10.1145/3593856.3595902
(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
Show More Cited By

Index Terms

Space efficient conservative garbage collection
1. Computer systems organization
2. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language types

Recommendations

Fast conservative garbage collection
OOPSLA '14

Garbage collectors are exact or conservative. An exact collector identifies all references precisely and may move referents and update references, whereas a conservative collector treats one or more of stack, register, and heap references as ambiguous. ...
Space efficient conservative garbage collection
PLDI '93: Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation

We call a garbage collector conservative if it has only partial information about the location of pointers, and is thus forced to treat arbitrary bit patterns as though they might be pointers, in at least some cases. We show that some very inexpensive, ...
Fast conservative garbage collection
OOPSLA '14: Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications

Garbage collectors are exact or conservative. An exact collector identifies all references precisely and may move referents and update references, whereas a conservative collector treats one or more of stack, register, and heap references as ambiguous. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 28, Issue 6

June 1993

313 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/173262

Editor:
Richard Wexelblat
IDA/CSED, Alexandria, VA

Issue’s Table of Contents

PLDI '93: Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation
August 1993
313 pages
ISBN:0897915984
DOI:10.1145/155090
Editor:
Robert Cartwright
Rice Univ., Houston, TX

Copyright © 1993 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 1993

Published in SIGPLAN Volume 28, Issue 6

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

206
Total Citations
View Citations
1,355
Total Downloads

Downloads (Last 12 months)228
Downloads (Last 6 weeks)36

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Frisella MSanchez SSchwarzkopf MBaumann ACrooks NSchwarzkopf M(2023)Towards Increased Datacenter Efficiency with Soft MemoryProceedings of the 19th Workshop on Hot Topics in Operating Systems10.1145/3593856.3595902(127-134)Online publication date: 22-Jun-2023
https://dl.acm.org/doi/10.1145/3593856.3595902
(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
Magalhães JLiao CPereira F(2022)Automatic inspection of program state in an uncooperative environmentSoftware: Practice and Experience10.1002/spe.314652:12(2727-2758)Online publication date: 31-Aug-2022
https://doi.org/10.1002/spe.3146
Jeon MLee MOh H(2020)Learning graph-based heuristics for pointer analysis without handcrafting application-specific featuresProceedings of the ACM on Programming Languages10.1145/34282474:OOPSLA(1-30)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428247
Milanova A(2020)FlowCFL: generalized type-based reachability analysis: graph reduction and equivalence of CFL-based and type-based reachabilityProceedings of the ACM on Programming Languages10.1145/34282464:OOPSLA(1-29)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428246
Coblenz MAldrich JMyers BSunshine J(2020)Can advanced type systems be usable? An empirical study of ownership, assets, and typestate in ObsidianProceedings of the ACM on Programming Languages10.1145/34282004:OOPSLA(1-28)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428200
Kim SZhang KMcGrenere JBooth KJacova C(2020)A Comparison of Touchscreen and Mouse for Real-World and Abstract Tasks with Older AdultsACM Transactions on Accessible Computing10.1145/341805713:4(1-26)Online publication date: 15-Oct-2020
https://dl.acm.org/doi/10.1145/3418057
Chatterjee NThakur SDas P(2015)Resource Management in Native Languages Using Dynamic Binary Instrumentation (PIN)Advanced Computing and Systems for Security10.1007/978-81-322-2653-6_8(107-119)Online publication date: 19-Nov-2015
https://doi.org/10.1007/978-81-322-2653-6_8
Giuffrida CIorgulescu CTanenbaum ARéveillère LCherkasova LTaïani F(2014)Mutable checkpoint-restartProceedings of the 15th International Middleware Conference10.1145/2663165.2663328(133-144)Online publication date: 8-Dec-2014
https://dl.acm.org/doi/10.1145/2663165.2663328
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 Publication

Figures

Tables

Media

View Issue’s Table of Contents