More Web Proxy on the site http://driver.im/

Article

Free access

Comparing mark-and sweep and stop-and-copy garbage collection

Author:

Benjamin ZornAuthors Info & Claims

LFP '90: Proceedings of the 1990 ACM conference on LISP and functional programming

Pages 87 - 98

https://doi.org/10.1145/91556.91597

Published: 01 May 1990 Publication History

Abstract

Stop-and-copy garbage collection has been preferred to mark-and-sweep collection in the last decade because its collection time is proportional to the size of reachable data and not to the memory size. This paper compares the CPU overhead and the memory requirements of the two collection algorithms extended with generations, and finds that mark-and-sweep collection requires at most a small amount of additional CPU overhead (3-6%) but, requires an average of 20% (and up to 40%) less memory to achieve the same page fault rate. The comparison is based on results obtained using trace-driven simulation with large Common Lisp programs.

References

[1]

Andrew Appel, John Ellis, and Kai Li. Real-time concurrent collection on stock multiprocessors. In SIC. PLAN'88 Conference on Programming Language Design and Implementation, pages 11-20, Atlanta, CA, June 1988. $IGPLAN, ACM Press.

Digital Library

[2]

Andrew W. Appel. Simple generational garbage collection and fast allocation. Software--Practice and Expe. rience, 19(2):171-183, February 1989.

Digital Library

[3]

H. D. Baecker. Garbage collection for virtual mereory computer systems. Communications of the A CM, 15(11):981-986, November 1972.

Digital Library

[4]

C. $. Cheney. A nonrecursive list compacting algorithm. Communications of the A CM, 13(11):677-678, Novembet 1970.

Digital Library

[5]

Jacques Cohen and Alexandru Nicolau. Comparison of compacting algorithms for garbage collection. A CM Transactions on Programming Languages and Systems, 5(4):512-553, October 1983.

Digital Library

[6]

Robert Courts. Improving locality of reference in a garbage-collecting memory management system. Cornmunications of the A CM, 31(9):1128-1138, September 1988.

Digital Library

[7]

D. Julian M. Davies. Memory occupancy patterns in garbage collection systems. Communication~ of the ACM, 27(8):819-825, August 1984.

Digital Library

[8]

Alan Demers, Mark Weiser, Barry Hayes, Hans Boehm, Daniel Bobrow, and Scott $henker. Combining generational and conservative garbage collection: Framework and implementations. In Conference Record of the Seventeenth AGM Symposium on Principles of Programming Lanyuages, pages 261-269, January 1990.

Digital Library

[9]

Robert R. Fenichel and Jerome C. Yochelson. A Lisp garbage-collector for virtual memory computer systems. Communications of the ACM, 12(11):611-612, November 1969.

Digital Library

[10]

Franz incorporated. Allegro Common Lisp User Guide, Release 3.0 (beta) edition, April 1988.

[11]

Henry Lieberman and Carl Hewitt. A real-time garbage collector based on the lifetimes of objects. Comrnunications of the ACM, 26(6):419-429, June 1983.

Digital Library

[12]

John McCarthy. Recursive functions of symbolic expressions and their computations by machinet part I. Communications of the A CM, 3(4):184-195, April 1960.

Digital Library

[13]

David A. Moon. Garbage collection in a large Lisp system. In Conference Record of the 1984 A CM Symposium on LISP and Functional Programming, pages 235-246~ Austin, Texas, August 1984.

Digital Library

[14]

I. A. Newman and M. C. Woodward. Alternative approaches to multiprocessor garbage collection. In Proceedings of the 1982 International Conference on Parallel Processing, pages 205-210, Ohio State University, Columbus, OH, August 1982. IEEE.

[15]

C.-J. Peng and G. S. Sold. Cache memory design considerations to support languages with dynamic heap allocation. Technical Report 860, Computer Sciences Dept., Univ. of Wisconsin--Madison, July 1989.

[16]

Robert A. Shaw. improving garbage collector performance in virtual memory. Technical Report CSL-TR- 87-323, Stanford University, March 1987.

[17]

Robert A. Shaw. Empirical Analysis of a Lisp System. PhD thesis, Stanford University, Stanford, CA, February 1988. Also appears as Computer Systems Laboratory tech report CSL-TR-88-351.

Digital Library

[18]

Patrick G. Sobalvarro. A lifet~e-based garbage collector for LISP systems on general purpose computers. Bachelor's thesis, MIT, 1988.

[19]

George Taylor. Ratio of MIP$ R$000 instructions to heap references. Personal communication, October 1989.

[20]

David Ungar. Generation scavenging: A non-disruptive high performance storage reclamation algorithm. In SIGSOFT/SIGPLA N Practical Programming Environrnentz Conference, pages 157-167, April 1984.

Digital Library

[21]

David Ungar and Frank Jackson. Tenuring policies for generation-based storage reclamation. In OOPSLA '88 Conference Proceedingz, pages 1-17. ACM, September 1988.

Digital Library

[22]

Duvid M. Ungar. The Design and Evaluation of A High Performance Srnalltalk System. PhD thesis, University of Callforn/a at Berkeley, Berkeley, CA, March 1986. Also appears as tech ~eport UCB/CSD 86/287.

Digital Library

[23]

Taiichi Yuaza and Masami Hagiya. The KCL Report. Research Institute for Mathematical Sciences, University of Kyoto.

[24]

Benjamin Zorn. Comparatiue Performance Evaluatior~ of Garbage Collection Algorithrn~. PhD thesis, University of CaLifornia at Berkeley, Berkeley, CA, November 1989. Also appears as tech report UCB/CSD 89/544.

Digital Library

[25]

Benjamin Zorn, Paul Hilfinger, Kinson Ho, and James Larus. SPUR Lisp: Design and implementation. Technical Report UCB/CSD 87/373, Computer Science Division (EECS), University of California, Berkeley, Octobcr 1987.

Digital Library

Cited By

Norlinder JÖsterlund EBlack-Schaffer DWrigstad T(2024)Mark–Scavenge: Waiting for Trash to Take Itself OutProceedings of the ACM on Programming Languages10.1145/36897918:OOPSLA2(2268-2295)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689791
Raza AChrysogelos PAnadiotis AAilamaki A(2023)One-shot Garbage Collection for In-memory OLTP through Temporality-aware Version StorageProceedings of the ACM on Management of Data10.1145/35886991:1(1-25)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.1145/3588699
Islam MRahman ARana S(2023)Performance Analysis of Modern Garbage Collectors using Big Data Benchmarks in the JDK 20 Environment2023 5th International Conference on Sustainable Technologies for Industry 5.0 (STI)10.1109/STI59863.2023.10464900(1-6)Online publication date: 9-Dec-2023
https://doi.org/10.1109/STI59863.2023.10464900
Show More Cited By

Index Terms

Comparing mark-and sweep and stop-and-copy garbage collection
1. Software and its engineering

Recommendations

Mark-copy: fast copying GC with less space overhead
OOPSLA '03: Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications

Copying garbage collectors have a number of advantages over non-copying collectors, including cheap allocation and avoiding fragmentation. However, in order to provide completeness (the guarantee to reclaim each garbage object eventually), standard ...
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 ...
Mark-copy: fast copying GC with less space overhead
Special Issue: Proceedings of the OOPSLA '03 conference

Copying garbage collectors have a number of advantages over non-copying collectors, including cheap allocation and avoiding fragmentation. However, in order to provide completeness (the guarantee to reclaim each garbage object eventually), standard ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

LFP '90: Proceedings of the 1990 ACM conference on LISP and functional programming

May 1990

348 pages

ISBN:089791368X

DOI:10.1145/91556

Chairman:
Gilles Kahn

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

SIGAI: ACM Special Interest Group on Artificial Intelligence
SIGPLAN: ACM Special Interest Group on Programming Languages
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation
INRIA: Institut Natl de Recherche en Info et en Automatique

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1990

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

LFP90

Sponsor:

LFP90: ACM Conference on Lisp and Functional Programming

June 27 - 29, 1990

Nice, France

Acceptance Rates

Overall Acceptance Rate 30 of 109 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

55
Total Citations
View Citations
1,768
Total Downloads

Downloads (Last 12 months)200
Downloads (Last 6 weeks)20

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Norlinder JÖsterlund EBlack-Schaffer DWrigstad T(2024)Mark–Scavenge: Waiting for Trash to Take Itself OutProceedings of the ACM on Programming Languages10.1145/36897918:OOPSLA2(2268-2295)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689791
Raza AChrysogelos PAnadiotis AAilamaki A(2023)One-shot Garbage Collection for In-memory OLTP through Temporality-aware Version StorageProceedings of the ACM on Management of Data10.1145/35886991:1(1-25)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.1145/3588699
Islam MRahman ARana S(2023)Performance Analysis of Modern Garbage Collectors using Big Data Benchmarks in the JDK 20 Environment2023 5th International Conference on Sustainable Technologies for Industry 5.0 (STI)10.1109/STI59863.2023.10464900(1-6)Online publication date: 9-Dec-2023
https://doi.org/10.1109/STI59863.2023.10464900
Noor JAl-Nabhan NIslam A(2023) RemOrphan : Object Storage Sustainability Through Rem oving Offline-Processed Orphan Garbage Data IEEE Access10.1109/ACCESS.2023.331921711(107049-107067)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3319217
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
Lee DWon YPark YLee SHung CCerny TShin DBechini A(2020)Two-tier garbage collection for persistent objectProceedings of the 35th Annual ACM Symposium on Applied Computing10.1145/3341105.3373986(1246-1255)Online publication date: 30-Mar-2020
https://dl.acm.org/doi/10.1145/3341105.3373986
Gnana Jeevan AMaluk Mohamed M(2018)SOGC: Implementing surrogate object garbage collector management for a Mobile Cloud EnvironmentConcurrency and Computation: Practice and Experience10.1002/cpe.494331:4Online publication date: 17-Sep-2018
https://doi.org/10.1002/cpe.4943
Yamaguchi S(2017)IEICE Communications Society Magazine10.1587/bplus.11.17911:3(179-185)Online publication date: 2017
https://doi.org/10.1587/bplus.11.179
Tong LLau F(2013)Skew-space garbage collectionScience of Computer Programming10.1016/j.scico.2011.06.00378:5(445-457)Online publication date: 1-May-2013
https://dl.acm.org/doi/10.1016/j.scico.2011.06.003
Cledat RKumar TPande S(2011)Efficiently speeding up sequential computation through the n-way programming modelACM SIGPLAN Notices10.1145/2076021.204810946:10(537-554)Online publication date: 22-Oct-2011
https://dl.acm.org/doi/10.1145/2076021.2048109
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 Table of Conten