article

A parallel, real-time garbage collector

Authors:

Guy E. BlellochAuthors Info & Claims

ACM SIGPLAN Notices, Volume 36, Issue 5

Pages 125 - 136

https://doi.org/10.1145/381694.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

Ueno KOhori ALippautz MChisnall D(2022)Concurrent and parallel garbage collection for lightweight threads on multicore processorsProceedings of the 2022 ACM SIGPLAN International Symposium on Memory Management10.1145/3520263.3534652(29-42)Online publication date: 14-Jun-2022
https://dl.acm.org/doi/10.1145/3520263.3534652
García AMay DNutting E(2021)Integrated Hardware Garbage CollectionACM Transactions on Embedded Computing Systems10.1145/345014720:5(1-25)Online publication date: 9-Jul-2021
https://dl.acm.org/doi/10.1145/3450147
Hauer THoffmann PLunney JArdelean DDiwan ABhagwan RPorter G(2020)Meaningful availabilityProceedings of the 17th Usenix Conference on Networked Systems Design and Implementation10.5555/3388242.3388283(545-558)Online publication date: 25-Feb-2020
https://dl.acm.org/doi/10.5555/3388242.3388283
Show More Cited By

Recommendations

A parallel, real-time garbage collector
PLDI '01: Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation

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 SIGPLAN Notices

ACM SIGPLAN Notices Volume 36, Issue 5

May 2001

330 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/381694

Issue’s Table of Contents

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

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 2001

Published in SIGPLAN Volume 36, Issue 5

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

177
Total Citations
View Citations
1,296
Total Downloads

Downloads (Last 12 months)26
Downloads (Last 6 weeks)3

Reflects downloads up to 13 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ueno KOhori ALippautz MChisnall D(2022)Concurrent and parallel garbage collection for lightweight threads on multicore processorsProceedings of the 2022 ACM SIGPLAN International Symposium on Memory Management10.1145/3520263.3534652(29-42)Online publication date: 14-Jun-2022
https://dl.acm.org/doi/10.1145/3520263.3534652
García AMay DNutting E(2021)Integrated Hardware Garbage CollectionACM Transactions on Embedded Computing Systems10.1145/345014720:5(1-25)Online publication date: 9-Jul-2021
https://dl.acm.org/doi/10.1145/3450147
Hauer THoffmann PLunney JArdelean DDiwan ABhagwan RPorter G(2020)Meaningful availabilityProceedings of the 17th Usenix Conference on Networked Systems Design and Implementation10.5555/3388242.3388283(545-558)Online publication date: 25-Feb-2020
https://dl.acm.org/doi/10.5555/3388242.3388283
Österlund ELöwe W(2015)Concurrent compaction using a field pinning protocolACM SIGPLAN Notices10.1145/2887746.275417750:11(56-69)Online publication date: 14-Jun-2015
https://dl.acm.org/doi/10.1145/2887746.2754177
Österlund ELöwe WHosking ABond M(2015)Concurrent compaction using a field pinning protocolProceedings of the 2015 International Symposium on Memory Management10.1145/2754169.2754177(56-69)Online publication date: 14-Jun-2015
https://dl.acm.org/doi/10.1145/2754169.2754177
Bacon DCheng PRajan V(2013)POPL 2003ACM SIGPLAN Notices10.1145/2502508.250252348:4S(58-71)Online publication date: 9-Jul-2013
https://dl.acm.org/doi/10.1145/2502508.2502523
YU SZHANG W(2010)REVIEW OF PARALLEL TECHNIQUES AND ITS IMPLICATION FOR JAVAJournal of Circuits, Systems and Computers10.1142/S021812661000676119:07(1465-1481)Online publication date: Nov-2010
https://doi.org/10.1142/S0218126610006761
Romanescu BLebeck ASorin DBracy A(2010)UNified Instruction/Translation/Data (UNITD) coherence: One protocol to rule them allHPCA - 16 2010 The Sixteenth International Symposium on High-Performance Computer Architecture10.1109/HPCA.2010.5416643(1-12)Online publication date: Jan-2010
https://doi.org/10.1109/HPCA.2010.5416643
Spoonhower DBlelloch GHarper RGibbons P(2010)Space profiling for parallel functional programsJournal of Functional Programming10.1017/S095679681000014620:5-6(417-461)Online publication date: 1-Nov-2010
https://dl.acm.org/doi/10.1017/S0956796810000146
Spoonhower DBlelloch GHarper RGibbons PHook JThiemann P(2008)Space profiling for parallel functional programsProceedings of the 13th ACM SIGPLAN international conference on Functional programming10.1145/1411204.1411240(253-264)Online publication date: 20-Sep-2008
https://dl.acm.org/doi/10.1145/1411204.1411240
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.

Figures

Tables

Media

View Issue’s Table of Contents