Article

Free access

Comparing mostly-copying and mark-sweep conservative collection

Authors:

Frederick Smith,

Greg MorrisettAuthors Info & Claims

ISMM '98: Proceedings of the 1st international symposium on Memory management

Pages 68 - 78

https://doi.org/10.1145/286860.286868

Published: 01 October 1998 Publication History

Abstract

Many high-level language compilers generate C code and then invoke a C compiler for code generation. To date, most, of these compilers link the resulting code against a conservative mark-sweep garbage collector in order to reclaim unused memory. We introduce a new collector, MCC, based on an extension of mostly-copying collection.We analyze the various design decisions made in MCC and provide a performance comparison to the most widely used conservative mark-sweep collector (the Boehm-Demers-Weiser collector). Our results show that a good mostly-copying collector can outperform a mature highly-optimized mark-sweep collector when physical memory is large relative to the live data. A surprising result of our analysis is that cache behavior can have a greater impact on overall performance than either collector time or allocation time.

References

[1]

American National Standards Institute, 1430 Broadway, New York, NY 10018, USA. American National Standard Programming Language C, ANSI X3.159- 1989, Dec. 14 1989.]]

[2]

A. W. Appel and D. B. MacQueen. Standard ML of New jersey. In M. Wirsing, editor, Third International Symposium on Programming Language Implementation and Logic Programming, pages 1-13, New York, Aug. 1991. Springer-Verlag. Volume 528 of Lecture Notes in Computer Science.]]

[3]

G. Attardi and T. Flagella. A customizable memory management framework. In USENIX Association, editor, Proceedings of the 199~ USENIX C++ Conference: April 11~1~, 1994, Cambridge, MA, pages 123- 142, Berkeley, CA, USA, Apr. 1994. USENIX.]]

Digital Library

[4]

G. Attardi, T. Flagella, and P. Iglio. Performance tuning in a customizable collector, in H. Baker, editor, Proceedings of International Workshop on Memory Management, Lecture Notes in Computer Science, Kinross, Scotland, Sept. 1995. Springer-Verlag.]]

Digital Library

[5]

J. F. Bartlett. Compacting garbage collection with ambiguous roots. Technical Report 88/2, Digital Equipment Corporation Western Research Laboratory, Palo Alto, California, Feb. 1988.]]

Digital Library

[6]

J. F. Bartlett. Mostly-copying garbage collection picks up generations and C++. Technical report, DEC WRL, Oct. 1989.]]

[7]

J. F. Bartlett. A generational, compacting collector for C++. in E. Jul and N.-C. Juul, editors, OOP- SLA/ECOOP '90 Workshop on Garbage Collection in Object-Oriented Systems, Oct. 1990.]]

[8]

H.-J. Boehm. Space-efficient conservative garbage collection. In A CM SIGPLAN Conference on Programming Language Design and Implementation, pages 197- 206, Albuquerque, June 1993.]]

Digital Library

[9]

H.-J. Boehm and D. R. Chase. A proposal for garbagecollector-safe C compilation. C Language Translation, 1992.]]

[10]

H.-J. Boehm and M. Weiser. Garbage collection in an uncooperative environment. Software Practice and Experience, 18(9):807-820, 1988.]]

Digital Library

[11]

J. Dean, G. DeFouw, D. Grove, V. Livinov, and C. Chambers. Vortex: An optimizing compiler for object-oriented languages. A CM SIGPLAN Notices, 31(10):83-100, Oct. 1996. Discusses performance of Vortex compiler for Cecil, C++, Java, and Modula-3.]]

Digital Library

[12]

A. Diwan, D. Tarditi, and E. Moss. Measuring subsystem performance of programs using copying garbage collection. In A CM Symposium on Principles of Programming Languages, pages 1-14, Portland Oregon, 1994.]]

Digital Library

[13]

A. Diwan, D. Tarditi, and E. Moss. Memory-system performance of programs with intensive heap allocation. Transactions on Computer Systems, 13(3):244- 273, Aug. 1995.]]

Digital Library

[14]

D. Edelson. A mark-and-sweep collector for c+~. In Nineteenth A CM Symposium on Principles of Programming Languages, pages 51-58, New Mexico, Jan. 1992.]]

Digital Library

[15]

M. W. Hicks, J. T. Moore, and S. M. Nettles. The measured cost of copying garbage collection mechanisms. In international Conference on Functional Programming, Amsterdam, June 1997.]]

Digital Library

[16]

R. E. Jones. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. Wiley, July 1996. With a chapter on Distributed Garbage Collection by R. Lins. Reprinted February 1996.]]

Digital Library

[17]

G. Morrisett. Compiling with Types. PhD thesis, School of Computer Science, Carnegie Mellon University, December 1995.]]

[18]

G. Muller, B. Moura, F. Bellard, and C. Consel. Harissa: a flexible and efficient java environment mixing bytecode and compiled code. In Usenix Conference on Object-Oriented Technlogies and Systems, Oregon, June 1996.]]

Digital Library

[19]

Objective caml. http://pauillac, inria.fr/ocaml/.]]

[20]

T. A. Proebsting, G. Townsend, P. Bridges, J. H. Hartman, T. Newsham, ~nd S. A. Watterson. Toba: Java for applications: A way ahead of time (WAT) compiler. Technical Report TR97-01, The Department of Computer Science, University of Arizona, Jan. 8 1997. Wed, 08 Jan 97 00:00:00 GMT.]]

Digital Library

[21]

C. Reade. Elements of Functional Programming. Addison-Wesley, Reading, 1989.]]

Digital Library

[22]

M. Serrano and P. Weis. Bigloo: a portable and optimizing compiler for strict functional languages. Lecture Notes in Computer Science, 983:366-81, 1995.]]

Digital Library

[23]

Z. Shao and A. W. Appel. Space-efficient closure representations. In A CM Conference on Lisp and Functional Programming, pages 150-161, Orlando, June i994.]]

Digital Library

[24]

Z. Shao and A. W. Appel. A type-based compiler for Standard ML. In A CM SIGPLAN Conference on Programming Language Design and Implementation, pages 116-129, La Jolla, June 1995.]]

Digital Library

[25]

F. Smith and G. Morrisett. Mostly copying collection: A viable alternative to conservative mark-sweep. Technical report, Cornell, 1997.]]

Digital Library

[26]

D. Tarditi. Design and Implementation of Code Optimizations for a TypeDirected Compiler for Standard ML. PhD thesis, School of Computer Science, Carnegie Mellon University, December 1996.]]

[27]

D. Tarditi, A. Acharya, and P. Lee. No assembly required: Compiling standard ML to C. Technical Report CMU-CS-90-187, School of Computer Science, Carnegie Mellon University, Nov. 90.]]

[28]

D. Tarditi, G. Morrisett, P. Cheng, C. Stone, R. Harper, and P. Lee. TIL: A type directed optimizing compiler for ML. in Proceedings of the A CM SIGPLAN '96 Conference on Programming Language Design and Implementation, pages 181-192, Philadelphia, Pennsylvania, 21- May 1996.]]

Digital Library

[29]

D. Tarditi, G. Morrisett, P. Cheng, C. Stone, R. Harper, and P. Lee. TIL: A type-directed optimizing compiler for ML. A CM SIGPLAN Notices, 31(5):181-192, May 1996.]]

Digital Library

[30]

K. G. Waugh, P. McAndrew, and G. Michaelson. Parallel implementations from function prototypes: a case study. Technical Report Computer Science 90/4, Heriot-Watt University, Edinburgh, Aug. 1990.]]

[31]

P. R. Wilson. Uniprocessor garbage collection techniques. In Y. Bekkers and J. Cohen, editors, International Workshop on Memory Management, number 637 in Lecture Notes in Computer Science, pages 1-42, St. Malo, Sept. 1992. Springer-Verlag.]]

[32]

P. R. Wilson. Garbage collection. Computing Surveys, 1995. Expanded version of {31}. Draft available via anonymous internet FTP from cs.utexas.edu as pub/gaxbage/biguurv.ps, in revision, to appear.]]

[33]

B. Zorn. The measured cost of conservative garbage collection. Software Practice and Experience, 23:733- 756, 1993.]]

Digital Library

Cited By

Banerjee SDevecsery DChen PNarayanasamy S(2020)Sound garbage collection for C using pointer provenanceProceedings of the ACM on Programming Languages10.1145/34282444:OOPSLA(1-28)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428244
Shahriyar RBlackburn SMcKinley K(2014)Fast conservative garbage collectionACM SIGPLAN Notices10.1145/2714064.266019849:10(121-139)Online publication date: 15-Oct-2014
https://dl.acm.org/doi/10.1145/2714064.2660198
Shahriyar RBlackburn SMcKinley KBlack AMillstein T(2014)Fast conservative garbage collectionProceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications10.1145/2660193.2660198(121-139)Online publication date: 15-Oct-2014
https://dl.acm.org/doi/10.1145/2660193.2660198
Show More Cited By

Index Terms

Comparing mostly-copying and mark-sweep conservative collection

Recommendations

Comparing mostly-copying and mark-sweep conservative collection

Many high-level language compilers generate C code and then invoke a C compiler for code generation. To date, most, of these compilers link the resulting code against a conservative mark-sweep garbage collector in order to reclaim unused memory. We ...
Mostly-Copying Collection: A Viable Alternative to Conservative Mark-Sweep
Mark-sweep or copying?: a "best of both worlds" algorithm and a hardware-supported real-time implementation
ISMM '07: Proceedings of the 6th international symposium on Memory management

Copying collectors offer a number of advantages over their mark-sweep counterparts. First, they do not have to deal with mark stacks and potential mark stack overflows. Second, they do not suffer from unpredictable fragmentation overheads since they ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISMM '98: Proceedings of the 1st international symposium on Memory management

October 1998

200 pages

ISBN:1581131143

DOI:10.1145/286860

Chairmen:
Simon Peyton Jones
Univ. of Glasgow, Glasgow, Scotland, UK
,
Richard Jones
Univ. of Kent at Canterbury, Canterbury, UK

ACM SIGPLAN Notices Volume 34, Issue 3
March 1999
195 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/301589
Chairmen:
Simon Peyton Jones
Univ. of Glasgow
,
Richard Jones
Univ. of Kent at Canterbury
Issue’s Table of Contents

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

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1998

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ISMM98

Sponsor:

SIGPLAN

ISMM98: International Symposium on Memory Management 1998

October 17 - 19, 1998

British Columbia, Vancouver, Canada

Acceptance Rates

Overall Acceptance Rate 72 of 156 submissions, 46%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
610
Total Downloads

Downloads (Last 12 months)135
Downloads (Last 6 weeks)16

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Banerjee SDevecsery DChen PNarayanasamy S(2020)Sound garbage collection for C using pointer provenanceProceedings of the ACM on Programming Languages10.1145/34282444:OOPSLA(1-28)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428244
Shahriyar RBlackburn SMcKinley K(2014)Fast conservative garbage collectionACM SIGPLAN Notices10.1145/2714064.266019849:10(121-139)Online publication date: 15-Oct-2014
https://dl.acm.org/doi/10.1145/2714064.2660198
Shahriyar RBlackburn SMcKinley KBlack AMillstein T(2014)Fast conservative garbage collectionProceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications10.1145/2660193.2660198(121-139)Online publication date: 15-Oct-2014
https://dl.acm.org/doi/10.1145/2660193.2660198
Ueno KOhori AOtomo TChakravarty MHu ZDanvy O(2011)An efficient non-moving garbage collector for functional languagesProceedings of the 16th ACM SIGPLAN international conference on Functional programming10.1145/2034773.2034802(196-208)Online publication date: 19-Sep-2011
https://dl.acm.org/doi/10.1145/2034773.2034802
Ueno KOhori AOtomo T(2011)An efficient non-moving garbage collector for functional languagesACM SIGPLAN Notices10.1145/2034574.203480246:9(196-208)Online publication date: 19-Sep-2011
https://dl.acm.org/doi/10.1145/2034574.2034802
Shen XMao FTian KZhang E(2009)The study and handling of program inputs in the selection of garbage collectorsACM SIGOPS Operating Systems Review10.1145/1618525.161853143:3(48-61)Online publication date: 31-Jul-2009
https://dl.acm.org/doi/10.1145/1618525.1618531
Rafkind JWick ARegehr JFlatt MKolodner HSteele G(2009)Precise garbage collection for CProceedings of the 2009 international symposium on Memory management10.1145/1542431.1542438(39-48)Online publication date: 19-Jun-2009
https://dl.acm.org/doi/10.1145/1542431.1542438
Mao FZhang EShen XHosking ABacon DKrieger O(2009)Influence of program inputs on the selection of garbage collectorsProceedings of the 2009 ACM SIGPLAN/SIGOPS international conference on Virtual execution environments10.1145/1508293.1508307(91-100)Online publication date: 11-Mar-2009
https://dl.acm.org/doi/10.1145/1508293.1508307
Baker JCunei AKalibera TPizlo FVitek J(2009)Accurate garbage collection in uncooperative environments revisitedConcurrency and Computation: Practice and Experience10.1002/cpe.139121:12(1572-1606)Online publication date: 13-Feb-2009
https://doi.org/10.1002/cpe.1391
Baker JCunei APizlo FVitek J(2007)Accurate garbage collection in uncooperative environments with lazy pointer stacksProceedings of the 16th international conference on Compiler construction10.5555/1759937.1759944(64-79)Online publication date: 26-Mar-2007
https://dl.acm.org/doi/10.5555/1759937.1759944
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

Media

Figures

Other

Tables

View Table of Contents