Article

A parallel, real-time garbage collector

Authors:

Guy E. BlellochAuthors Info & Claims

PLDI '01: Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation

Pages 125 - 136

https://doi.org/10.1145/378795.378823

Published: 01 May 2001 Publication History

Abstract

We describe a parallel, real-time garbage collector and present experimental results that demonstrate good scalability and good real-time bounds. The collector is designed for shared-memory multiprocessors and is based on an earlier collector algorithm [2], which provided fixed bounds on the time any thread must pause for collection. However, since our earlier algorithm was designed for simple analysis, it had some impractical features. This paper presents the extensions necessary for a practical implementation: reducing excessive interleaving, handling stacks and global variables, reducing double allocation, and special treatment of large and small objects. An implementation based on the modified algorithm is evaluated on a set of 15 SML benchmarks on a Sun Enterprise 10000, a 64-way UltraSparc-II multiprocessor. To the best of our knowledge, this is the first implementation of a parallel, real-time garbage collector.

The average collector speedup is 7.5 at 8 processors and 17.7 at 32 processors. Maximum pause times range from 3 ms to 5 ms. In contrast, a non-incremental collector (whether generational or not) has maximum pause times from 10 ms to 650 ms. Compared to a non-parallel, stop-copy collector, parallelism has a 39% overhead, while real-time behavior adds an additional 12% overhead. Since the collector takes about 15% of total execution time, these features have an overall time costs of 6% and 2%.

References

[1]

Henry G. Baker. List processing in real-time on a serial computer. Communications of the ACM, 21(4):280-94, 1978. Also AI Laboratory Working Paper 139, 1977.

Digital Library

[2]

Guy E. Blelloch and Perry Cheng. On bounding time and space for multiprocessor garbage collection. In Proc. ACM SIGPLAN Conference onProgramming Languages Design and Implementation, ACM SIGPLAN Notices, pages 104-117, Atlanta, May 99. ACM Press.

Digital Library

[3]

Guy E. Blelloch, Perry Cheng, and Phil Gibbons. Room synchronizations. In ACM Symposium on Parallel Algorithms and Architecture. ACM Press, July 2001.

Digital Library

[4]

C. J. Cheney. A non-recursive list compacting algorithm. Communications of the ACM, 13(11):677-8, November 1970.

Digital Library

[5]

Perry Cheng. Scalable Real-time Parallel Garbage Collection for Symmetric Multiprocessors. PhD thesis, Carnegie Mellon University, 2001.

Digital Library

[6]

Perry Cheng, Robert Harper, and Peter Lee. Generational stack collection and profile-driven pretenuring. In Proc. ACM SIGPLAN Conference on Programming Languages Design and Implementation, ACM SIGPLAN Notices, Montreal, June 1998. ACM Press.

Digital Library

[7]

Edsgar W. Dijkstra, Leslie Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens. On-the-fly garbage collection: An exercise in cooperation. In Lecture Notes in Computer Science, No. 46. Springer-Verlag, New York, 1976.

Digital Library

[8]

Edsgar W. Dijkstra, Leslie Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens. On-the-fly garbage collection: An exercise in cooperation. Communications of the ACM, 21(11):965-975, November 1978.

Digital Library

[9]

Damien Doligez and Georges Gonthier. Portable, unobtrusive garbage collection for multiprocessor systems. In Proc. ACM Symposium on Principles of Programming Languages, ACM SIGPLAN Notices. ACM Press, January 1994.

Digital Library

[10]

Damien Doligez and Xavier Leroy. A concurrent generational garbage collector for a multi-threaded implementation of ML. In Proc. ACM Symposium on Principles of Programming Languages, ACM SIGPLAN Notices, pages 113-123. ACM Press, January 1993.

Digital Library

[11]

Tamar Domani, Elliot Kolodner, and Erez Petrank. A generational on-the-fly garbage collector for Java. In Proc. ACM SIGPLAN Conference onProgramming Languages Design and Implementation, pages 274-284, May 2000.

Digital Library

[12]

Toshio Endo. A scalable mark-sweep garbage collector on large-scale shared-memory machines. Master's thesis, University ofTokyo, February 1998.

[13]

Steven L. Engelstad and James E. Vandendorpe. Automatic storage management for systems with real time constraints. In Paul R. Wilson and Barry Hayes, editors, OOPSLA/ECOOP '91 Workshop on Garbage Collection in Object-Oriented Systems, Addendum to OOPSLA'91 Proceedings, October 1991.

Digital Library

[14]

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

[15]

Christine Flood, Dave Detlefs, Nir Shavit, and Catherine Zhang. Parallel garbage collection for shared memory multiprocessors. In Proc. USENIX JVM Conference, April 2001.

Digital Library

[16]

Seth Goldstein. Lazy Threads: Compiler and Runtime Structures for Fine-Grained Parallel Programming. PhD thesis, University of California at Berkeley, Fall 1997.

Digital Library

[17]

A. Gottlieb, B. D. Lubachevsky, and L. Rudolph. Basic techniques for the efficient coordination of very large numbers of cooperating sequqnetial processors. ACM Trans. on Programming Languages and Systems, 5(2):164-189, April 1983.

Digital Library

[18]

Robert H. Halstead. Multilisp: A language for concurrent symbolic computation. ACM Transactions on Programming Languages and Systems, 7(4):501-538, October 1985.

Digital Library

[19]

Maurice Herlihy and J. Eliot B Moss. Lock-free garbage collection for multiprocessors. IEEE Transactions on Parallel and Distributed Systems, 3(3), May 1992.

Digital Library

[20]

Martin Larose and Marc Feeley. A compacting incremental collector and its performance in a production quality compiler. In Richard Jones, editor, Proc. International Symp. on Memory Management, volume 34(3) of ACM SIGPLAN Notices, pages 1-9, Vancouver, October 1998. ACM Press.

Digital Library

[21]

John McCarthy. Recursive functions of symbolic expressions and their computation by machine. Communications of the ACM, 3:184-195, 1960.

Digital Library

[22]

Scott M. Nettles and James W. O'Toole. Real-time replication-based garbage collection. In Proc. ACM SIGPLAN Conference onProgramming Languages Design and Implementation, volume 28(6) of ACM SIGPLAN Notices. ACM Press. June 1993.

Digital Library

[23]

Guy L. Steele. Multiprocessing compactifying garbage collection. Communications of the ACM, 18(9):495-508, September 1975.

Digital Library

[24]

Tarditi, Morrisett, Cheng, Stone, Harper, and Lee. TIL: A type-directed optimizing compiler for ML. In Proc. ACM SIGPLAN Conference onProgramming Languages Design and Implementation, pages 181-192, 1996.

Digital Library

[25]

David M. Ungar and David A. Patterson. Berkeley Smalltalk: Who knows where the time goes? In Glenn Krasner, editor, Smalltalk-80: Bits of History, Words of Advice, pages 189-206. Addison-Wesley, 1983.

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
Westrick SArora JAcar U(2022)Entanglement detection with near-zero costProceedings of the ACM on Programming Languages10.1145/35476466:ICFP(679-710)Online publication date: 31-Aug-2022
https://dl.acm.org/doi/10.1145/3547646
Ma HLiu SWang CQiao YBond MBlackburn SKim MXu GJhala RDillig I(2022)Mako: a low-pause, high-throughput evacuating collector for memory-disaggregated datacentersProceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3519939.3523441(92-107)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519939.3523441
Show More Cited By

Recommendations

A parallel, real-time garbage collector

We describe a parallel, real-time garbage collector and present experimental results that demonstrate good scalability and good real-time bounds. The collector is designed for shared-memory multiprocessors and is based on an earlier collector algorithm [...
A generational on-the-fly garbage collector for Java
PLDI '00: Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation

An on-the-fly garbage collector does not stop the program threads to perform the collection. Instead, the collector executes in a separate thread (or process) in parallel to the program. On-the-fly collectors are useful for multi-threaded applications ...
Concurrent, parallel, real-time garbage-collection
ISMM '10

With the current developments in CPU implementations, it becomes obvious that ever more parallel multicore systems will be used even in embedded controllers that require real-time guarantees. When garbage collection is used in these systems, parallel ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '01: Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation

June 2001

331 pages

ISBN:1581134142

DOI:10.1145/378795

Chairmen:
Michael Burke
IBM T.J. Watson Research Center
,
Mary Lou Soffa
Univ. of Pittsburgh

ACM SIGPLAN Notices Volume 36, Issue 5
May 2001
330 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/381694
Editors:
Cindy Norris,
James B. Bergin
Issue’s Table of Contents

Copyright © 2001 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 May 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PLDI01

Sponsor:

SIGPLAN

PLDI01: ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation

Utah, Snowbird, USA

Acceptance Rates

PLDI '01 Paper Acceptance Rate 30 of 144 submissions, 21%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

176
Total Citations
View Citations
1,289
Total Downloads

Downloads (Last 12 months)30
Downloads (Last 6 weeks)2

Reflects downloads up to 20 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
Westrick SArora JAcar U(2022)Entanglement detection with near-zero costProceedings of the ACM on Programming Languages10.1145/35476466:ICFP(679-710)Online publication date: 31-Aug-2022
https://dl.acm.org/doi/10.1145/3547646
Ma HLiu SWang CQiao YBond MBlackburn SKim MXu GJhala RDillig I(2022)Mako: a low-pause, high-throughput evacuating collector for memory-disaggregated datacentersProceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3519939.3523441(92-107)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519939.3523441
Cai ZBlackburn SBond MMaas M(2022)Distilling the Real Cost of Production Garbage Collectors2022 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS)10.1109/ISPASS55109.2022.00005(46-57)Online publication date: May-2022
https://doi.org/10.1109/ISPASS55109.2022.00005
Arora JWestrick SAcar U(2021)Provably space-efficient parallel functional programmingProceedings of the ACM on Programming Languages10.1145/34342995:POPL(1-33)Online publication date: 4-Jan-2021
https://dl.acm.org/doi/10.1145/3434299
MacQueen DHarper RReppy J(2020)The history of Standard MLProceedings of the ACM on Programming Languages10.1145/33863364:HOPL(1-100)Online publication date: 12-Jun-2020
https://dl.acm.org/doi/10.1145/3386336
Béra CMiranda EBoix EMarr SFumero J(2019)Lazy pointer update for low heap compaction pause timesProceedings of the 15th ACM SIGPLAN International Symposium on Dynamic Languages10.1145/3359619.3359741(15-27)Online publication date: 20-Oct-2019
https://dl.acm.org/doi/10.1145/3359619.3359741
Degenbaev ULippautz MPayer HSinger JXu H(2019)Concurrent marking of shape-changing objectsProceedings of the 2019 ACM SIGPLAN International Symposium on Memory Management10.1145/3315573.3329978(89-102)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3315573.3329978
Degenbaev UEisinger JHara KHlopko MLippautz MPayer H(2018)Cross-component garbage collectionProceedings of the ACM on Programming Languages10.1145/32765212:OOPSLA(1-24)Online publication date: 24-Oct-2018
https://dl.acm.org/doi/10.1145/3276521
Ugawa TRitson CJones R(2018)Transactional SapphireACM Transactions on Programming Languages and Systems10.1145/322622540:4(1-56)Online publication date: 10-Dec-2018
https://dl.acm.org/doi/10.1145/3226225
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents