Article

Free access

Contaminated garbage collection

Authors:

Dante J. Cannarozzi,

Michael P. Plezbert,

Ron K. CytronAuthors Info & Claims

PLDI '00: Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation

Pages 264 - 273

https://doi.org/10.1145/349299.349334

Published: 01 May 2000 Publication History

Abstract

We describe a new method for determining when an object can be garbage collected. The method does not require marking live objects. Instead, each object X is dynamically associated with a stack frame M, such that Xis collectable when M pops. Because X could have been dead earlier, our method is conservative. Our results demonstrate that the method nonetheless identifies a large percentage of collectable objects. The method has been implemented in Sun's Java Virtual Machine interpreter, and results are presented based on this implementation

References

[1]

A.V. Aho, R. Sethi, and J.D. Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley, Reading, Mass., 1986.

Digital Library

[2]

Andrew Appel. Empirical and analytic study of stack versus heap cost for languages with closures. Journal of Functional Programming, 6(1):47-74, 1996.

[3]

Hans-Juergen Boehm. Space efficient conservative garbage collection. SIGPLAN Notices, 28(6):197- 206, June 1993. Proceedings of the A CM SIGPLAN '93 Conference on Programming Language Design and Implementation.

Digital Library

[4]

US Census. Tiger mapping service, the "coast to coast" digital map database. Technical report, US Census Bureau, 1999. http://tiger.census.gov/.

[5]

D. R. Chase. Garbage Collection and Other Optimizations. PhD thesis, Dept. of Computer Sci., Rice U., Houston, TX, August 1987.

Digital Library

[6]

Trishul Chilimbi and James Larus. Using generational garbage collection to implement cache-conscious data placement. Proceedings of the International Symposium on Memory Management, 1998.

Digital Library

[7]

Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction to Algorithms. The MIT Press, Cambridge, Mass., 1990.

Digital Library

[8]

SPEC Corporation. Java spec benchmarks. Technical report, SPEC, 1999. Available by purchase from SPEC.

[9]

Scott Haug. Automatic storage optimization via garbage collection. Master's thesis, Washington University, 1999.

[10]

Richard L. Hudson, Ron Morrison, J. Eliot B. Moss, and David S. Munro. Garbage collecting the world: One car at a time. In OOPSLA '97 A CM Conference on Object-Oriented Systems, Languages and Applications Twelth Annual Conference, volume 32(10) of ACM SIGPLAN Notices. ACM Press, October 1997.

Digital Library

[11]

Tim Lindholm and Frank Yellin. The Java Virtual Machine Specification. Addison-Wesley, 1997.

Digital Library

[12]

Alastair Reid, John McCorquodale, Jason Baker, Wilson Hsieh, and Joseph Zachary. The need for predictable gc. Proceedings of the Second Workshop on Compiler Support for System Software, 1999.

[13]

Cristina Ruggieri and Thomas P. Murtagh. Lifetime analysis of dynamically allocated objects. In Conference Record of the Fifteenth Annual A CM Symposium on Principles of Programming Languages, pages 285-293, San Diego, California, January 1988.

Digital Library

[14]

Jacob Seligmann and Steffen Grarup. Incremental mature garbage collection using the train algorithm. Proceedings of ECOOP '95, pages 235-252, 1995.

Digital Library

[15]

Darko Stefanovic. Properties of Age-Based Automatic Memory Reclamation Algorithms. PhD thesis, University of Massachusetts, Amherst, 1999.

Digital Library

[16]

Mads Torte. A brief introduction to regions. Proceedings of the International Symposium on Memory Management (ISMM), pages 186-195, 1998.

Digital Library

[17]

Mads Tofte and Jean-Pierre Talpin. Implementation of the typed call-by-value A-calculus using a stack of regions. In Conference Record of POPL '94: 21st A CM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 188-201, Portland, Oregon, January 1994.

Digital Library

[18]

Paul R. Wilson. Uniprocessor garbage collection techniques (Long Version). Submitted to ACM Computing Surveys, 1994.

[19]

Paul R. Wilson, Mark S. Johnstone, Michael Neely, and David Boles. Dynamic storage allocation: A survey and critical review. In Henry Baker, editor, Proceedings of International Workshop on Memory Management, volume 986 of Lecture Notes in Computer Science, Kinross, Scotland, September 1995. Springer-Verlag.

Digital Library

[20]

Kwang Keun Yi and Williams Ludwell Harrison. Interprocedural data flow analysis for compile-time memory management. Technical Report CSRD 1244, University of Illinois at Urbana-Champaign, Center for Supercomputing Research and Development, Urbana, IL 61801, USA, August 1992.

Cited By

Liu SYen PMao YLin YChandra EChen M(2020)HeadBlasterACM Transactions on Graphics10.1145/3386569.339248239:4(84:1-84:12)Online publication date: 12-Aug-2020
https://dl.acm.org/doi/10.1145/3386569.3392482
Hornus SKuipers TDevillers OTeillaud MMartínez JGlisse MLazard SLefebvre S(2020)Variable-width contouring for additive manufacturingACM Transactions on Graphics10.1145/3386569.339244839:4(131:1-131:17)Online publication date: 12-Aug-2020
https://dl.acm.org/doi/10.1145/3386569.3392448
Pellis DWang HKilian MRist FPottmann HMüller C(2020)Principal symmetric meshesACM Transactions on Graphics10.1145/3386569.339244639:4(127:1-127:17)Online publication date: 12-Aug-2020
https://dl.acm.org/doi/10.1145/3386569.3392446
Show More Cited By

Index Terms

Contaminated garbage collection
1. Software and its engineering
  1. Software creation and management
    1. Designing software
      1. Software implementation planning
        Software design techniques
    2. Software development process management
2. Theory of computation
  1. Logic
  2. Models of computation

Recommendations

Age-based garbage collection
OOPSLA '99: Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications

Modern generational garbage collectors look for garbage among the young objects, because they have high mortality; however, these objects include the very youngest objects, which clearly are still live. We introduce new garbage collection algorithms, ...
Age-based garbage collection

Modern generational garbage collectors look for garbage among the young objects, because they have high mortality; however, these objects include the very youngest objects, which clearly are still live. We introduce new garbage collection algorithms, ...
Older-first garbage collection in practice: evaluation in a Java Virtual Machine
MSP '02: Proceedings of the 2002 workshop on Memory system performance

Until recently, the best performing copying garbage collectors used a generational policy which repeatedly collects the very youngest objects, copies any survivors to an older space, and then infrequently collects the older space. A previous study that ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '00: Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation

August 2000

358 pages

ISBN:1581131992

DOI:10.1145/349299

Chairman:
Monica Lam

ACM SIGPLAN Notices Volume 35, Issue 5
May 2000
357 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/358438
Editor:
A. Michael Berman
Rowan Univ., Glassboro, NJ
Issue’s Table of Contents

Copyright © 2000 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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 2000

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PLDI00

Sponsor:

PLDI00: ACM SIGPLAN 2000 Conference on Programming Language and Design and Implementation

June 18 - 21, 2000

British Columbia, Vancouver, Canada

Acceptance Rates

PLDI '00 Paper Acceptance Rate 30 of 173 submissions, 17%;

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

31
Total Citations
View Citations
658
Total Downloads

Downloads (Last 12 months)74
Downloads (Last 6 weeks)12

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu SYen PMao YLin YChandra EChen M(2020)HeadBlasterACM Transactions on Graphics10.1145/3386569.339248239:4(84:1-84:12)Online publication date: 12-Aug-2020
https://dl.acm.org/doi/10.1145/3386569.3392482
Hornus SKuipers TDevillers OTeillaud MMartínez JGlisse MLazard SLefebvre S(2020)Variable-width contouring for additive manufacturingACM Transactions on Graphics10.1145/3386569.339244839:4(131:1-131:17)Online publication date: 12-Aug-2020
https://dl.acm.org/doi/10.1145/3386569.3392448
Pellis DWang HKilian MRist FPottmann HMüller C(2020)Principal symmetric meshesACM Transactions on Graphics10.1145/3386569.339244639:4(127:1-127:17)Online publication date: 12-Aug-2020
https://dl.acm.org/doi/10.1145/3386569.3392446
Jiang CWang CRist FWallner JPottmann H(2020)Quad-mesh based isometric mappings and developable surfacesACM Transactions on Graphics10.1145/3386569.339243039:4(128:1-128:13)Online publication date: 12-Aug-2020
https://dl.acm.org/doi/10.1145/3386569.3392430
Mehta DSotnychenko OMueller FXu WElgharib MFua PSeidel HRhodin HPons-Moll GTheobalt C(2020)XNectACM Transactions on Graphics10.1145/3386569.339241039:4(82:1-82:17)Online publication date: 12-Aug-2020
https://dl.acm.org/doi/10.1145/3386569.3392410
Ye HKwan KSu WFu H(2020)ARAnimatorACM Transactions on Graphics10.1145/3386569.339240439:4(83:1-83:12)Online publication date: 12-Aug-2020
https://dl.acm.org/doi/10.1145/3386569.3392404
Shidal JGottlieb ZCytron RKavi KSinger JKulkarni MHarris T(2014)Trash in cacheProceedings of the workshop on Memory Systems Performance and Correctness10.1145/2618128.2618133(1-9)Online publication date: 13-Jun-2014
https://dl.acm.org/doi/10.1145/2618128.2618133
(2013)Model-based sparse component analysis for multiparty distant speech recognitionACM SIGMultimedia Records10.1145/2584671.25846775:4(8-9)Online publication date: 1-Dec-2013
https://dl.acm.org/doi/10.1145/2584671.2584677
(2013)VIREO-VHACM SIGMultimedia Records10.1145/2584671.25846755:4(6-8)Online publication date: 1-Dec-2013
https://dl.acm.org/doi/10.1145/2584671.2584675
Khedker USanyal AKarkare A(2007)Heap reference analysis using access graphsACM Transactions on Programming Languages and Systems10.1145/1290520.129052130:1(1-es)Online publication date: 1-Nov-2007
https://dl.acm.org/doi/10.1145/1290520.1290521
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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

Media

Figures

Other

Tables

View Table of Contents