research-article

A fully concurrent garbage collector for functional programs on multicore processors

Authors:

Katsuhiro Ueno,

Atsushi OhoriAuthors Info & Claims

ICFP 2016: Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming

Pages 421 - 433

https://doi.org/10.1145/2951913.2951944

Published: 04 September 2016 Publication History

Abstract

This paper presents a concurrent garbage collection method for functional programs running on a multicore processor. It is a concurrent extension of our bitmap-marking non-moving collector with Yuasa's snapshot-at-the-beginning strategy. Our collector is unobtrusive in the sense of the Doligez-Leroy-Gonthier collector; the collector does not stop any mutator thread nor does it force them to synchronize globally. The only critical sections between a mutator and the collector are the code to enqueue/dequeue a 32 kB allocation segment to/from a global segment list and the write barrier code to push an object pointer onto the collector's stack. Most of these data structures can be implemented in standard lock-free data structures. This achieves both efficient allocation and unobtrusive collection in a multicore system. The proposed method has been implemented in SML#, a full-scale Standard ML compiler supporting multiple native threads on multicore CPUs. Our benchmark tests show a drastically short pause time with reasonably low overhead compared to the sequential bitmap-marking collector.

References

[1]

A. W. Appel. Simple generational garbage collection and fast allocation. Softw. Pract. Exper., 19(2):171–183, 1989.

Digital Library

[2]

S. Auhagen, L. Bergstrom, M. Fluet, and J. Reppy. Garbage collection for multicore NUMA machines. In Proceedings of the 2011 ACM SIGPLAN Workshop on Memory Systems Performance and Correctness, pp. 51–57, 2011.

Digital Library

[3]

H. Azatchi, Y. Levanoni, H. Paz, and E. Petrank. An on-the-fly mark and sweep garbage collector based on sliding views. In Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, pp. 269–281, 2003.

Digital Library

[4]

G. E. Blelloch and P. Cheng. On bounding time and space for multiprocessor garbage collection. In Proceedings of the ACM SIGPLAN 1999 Conference on Programming Language Design and Implementation, pp. 104–117, 1999.

Digital Library

[5]

P. Cheng and G. E. Blelloch. A parallel, real-time garbage collector. In Proceedings of the ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation, pp. 125–136, 2001.

Digital Library

[6]

C. Click, G. Tene, and M. Wolf. The pauseless GC algorithm. In Proceedings of the 1st ACM/USENIX International Conference on Virtual Execution Environments, pp. 46–56, 2005.

Digital Library

[7]

D. Detlefs, C. Flood, S. Heller, and T. Printezis. Garbage-first garbage collection. In Proceedings of the 4th international symposium on Memory management, pp. 37–48, 2004.

Digital Library

[8]

E. W. Dijkstra, L. Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens. On-the-fly garbage collection: an exercise in cooperation. Commun. ACM, 21:966–975, 1978.

Digital Library

[9]

D. Doligez and G. Gonthier. Portable, unobtrusive garbage collection for multiprocessor systems. In Proceedings of the 21st ACM SIGPLANSIGACT symposium on Principles of programming languages, pp. 70– 83, 1994.

Digital Library

[10]

D. Doligez and X. Leroy. A concurrent, generational garbage collector for a multithreaded implementation of ML. In Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pp. 113–123, 1993.

Digital Library

[11]

T. Domani, E. K. Kolodner, and E. Petrank. A generational on-the-fly garbage collector for Java. In Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, pp. 274–284, 2000.

Digital Library

[12]

C. H. Flood, D. Detlefs, N. Shavit, and X. Zhang. Parallel garbage collection for shared memory multiprocessors. In Proceedings of the 2001 Symposium on JavaTM Virtual Machine Research and Technology Symposium - Volume 1, pp. 21–21, 2001.

Digital Library

[13]

Y. Levanoni and E. Petrank. An on-the-fly reference-counting garbage collector for Java. ACM Trans. Program. Lang. Syst., 28(1):1–69, 2006.

Digital Library

[14]

S. Marlow, T. Harris, R. P. James, and S. Peyton Jones. Parallel generational-copying garbage collection with a block-structured heap. In Proceedings of the 7th international symposium on Memory management, pp. 11–20, 2008.

Digital Library

[15]

S. Marlow and S. Peyton Jones. Multicore garbage collection with local heaps. In Proceedings of the international symposium on Memory management, pp. 21–32, 2011.

Digital Library

[16]

Y. Ossia, O. Ben-Yitzhak, I. Goft, E. K. Kolodner, V. Leikehman, and A. Owshanko. A parallel, incremental and concurrent GC for servers. In Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, pp. 129–140, 2002.

Digital Library

[17]

F. Pizlo, D. Frampton, E. Petrank, and B. Steensgaard. Stopless: a real-time garbage collector for multiprocessors. In Proceedings of the 6th international symposium on Memory management, pp. 159–172, 2007.

Digital Library

[18]

F. Pizlo, L. Ziarek, P. Maj, A. L. Hosking, E. Blanton, and J. Vitek. Schism: fragmentation-tolerant real-time garbage collection. In Proceedings of the 2010 ACM SIGPLAN conference on Programming language design and implementation, pp. 146–159, 2010.

Digital Library

[19]

SML# project. http://www.pllab.riec.tohoku.ac.jp/smlsharp/.

[20]

K. Ueno, A. Ohori, and T. Otomo. An efficient non-moving garbage collector for functional languages. In Proceedings of the 16th ACM SIGPLAN international conference on Functional programming, pp. 196–208, 2011.

Digital Library

[21]

T. Yuasa. Real-time garbage collection on general-purpose machines. J. Syst. Softw., 11(3):181–198, 1990.

Digital Library

Cited By

Elsman M(2023)Garbage-Collection Safety for Region-Based Type-Polymorphic ProgramsProceedings of the ACM on Programming Languages10.1145/35912297:PLDI(221-243)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591229
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
Koparkar CRainey MVollmer MKulkarni MNewton R(2021)Efficient tree-traversals: reconciling parallelism and dense data representationsProceedings of the ACM on Programming Languages10.1145/34735965:ICFP(1-29)Online publication date: 19-Aug-2021
https://dl.acm.org/doi/10.1145/3473596
Show More Cited By

Index Terms

A fully concurrent garbage collector for functional programs on multicore processors
1. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

A fully concurrent garbage collector for functional programs on multicore processors
ICFP '16

This paper presents a concurrent garbage collection method for functional programs running on a multicore processor. It is a concurrent extension of our bitmap-marking non-moving collector with Yuasa's snapshot-at-the-beginning strategy. Our collector ...
A parallel, incremental, mostly concurrent garbage collector for servers

Multithreaded applications with multigigabyte heaps running on modern servers provide new challenges for garbage collection (GC). The challenges for “server-oriented” GC include: ensuring short pause times on a multigigabyte heap while minimizing ...
An on-the-fly mark and sweep garbage collector based on sliding views
Special Issue: Proceedings of the OOPSLA '03 conference

With concurrent and garbage collected languages like Java and C# becoming popular, the need for a suitable non-intrusive, efficient, and concurrent multiprocessor garbage collector has become acute. We propose a novel mark and sweep on-the-fly algorithm ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICFP 2016: Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming

September 2016

501 pages

ISBN:9781450342193

DOI:10.1145/2951913

General Chairs:
Jacques Garrigue
Nagoya University, Japan
,
Gabriele Keller
University of New South Wales, Australia
,
Program Chair:
Eijiro Sumii
Tohoku University, Japan

ACM SIGPLAN Notices Volume 51, Issue 9
ICFP '16
September 2016
501 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/3022670
Editor:
Matthew Fluet
Issue’s Table of Contents

Copyright © 2016 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: 04 September 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Japan Society for the Promotion of Science

Conference

ICFP'16

Sponsor:

SIGPLAN

ICFP'16: ACM SIGPLAN International Conference on Functional Programming

September 18 - 24, 2016

Nara, Japan

Acceptance Rates

Overall Acceptance Rate 333 of 1,064 submissions, 31%

Upcoming Conference

ICFP '25

Sponsor:
sigplan

ACM SIGPLAN International Conference on Functional Programming

October 12 - 18, 2025

Singapore , Singapore

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
350
Total Downloads

Downloads (Last 12 months)32
Downloads (Last 6 weeks)4

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Elsman M(2023)Garbage-Collection Safety for Region-Based Type-Polymorphic ProgramsProceedings of the ACM on Programming Languages10.1145/35912297:PLDI(221-243)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591229
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
Koparkar CRainey MVollmer MKulkarni MNewton R(2021)Efficient tree-traversals: reconciling parallelism and dense data representationsProceedings of the ACM on Programming Languages10.1145/34735965:ICFP(1-29)Online publication date: 19-Aug-2021
https://dl.acm.org/doi/10.1145/3473596
Krauter NRaaf PBraam PSalkhordeh RErdweg SBrinkmann A(2021)Persistent software transactional memory in HaskellProceedings of the ACM on Programming Languages10.1145/34735685:ICFP(1-29)Online publication date: 19-Aug-2021
https://dl.acm.org/doi/10.1145/3473568
ELSMAN MHALLENBERG N(2021)Integrating region memory management and tag-free generational garbage collectionJournal of Functional Programming10.1017/S095679682100001031Online publication date: 22-Feb-2021
https://doi.org/10.1017/S0956796821000010
Gamari BDietz LDing CMaas M(2020)Alligator collector: a latency-optimized garbage collector for functional programming languagesProceedings of the 2020 ACM SIGPLAN International Symposium on Memory Management10.1145/3381898.3397214(87-99)Online publication date: 16-Jun-2020
https://dl.acm.org/doi/10.1145/3381898.3397214
Elsman MHallenberg N(2020)On the Effects of Integrating Region-Based Memory Management and Generational Garbage Collection in MLPractical Aspects of Declarative Languages10.1007/978-3-030-39197-3_7(95-112)Online publication date: 14-Jan-2020
https://doi.org/10.1007/978-3-030-39197-3_7
Ramsay CStewart RVazou NMorris J(2024)Cloaca: A Concurrent Hardware Garbage Collector for Non-strict Functional LanguagesProceedings of the 17th ACM SIGPLAN International Haskell Symposium10.1145/3677999.3678277(41-54)Online publication date: 29-Aug-2024
https://dl.acm.org/doi/10.1145/3677999.3678277
Sivaramakrishnan KDolan SWhite LJaffer SKelly TSahoo AParimala SDhiman AMadhavapeddy A(2020)Retrofitting parallelism onto OCamlProceedings of the ACM on Programming Languages10.1145/34089954:ICFP(1-30)Online publication date: 3-Aug-2020
https://dl.acm.org/doi/10.1145/3408995

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