research-article

Multicore garbage collection with local heaps

Authors:

Simon Peyton JonesAuthors Info & Claims

ISMM '11: Proceedings of the international symposium on Memory management

Pages 21 - 32

https://doi.org/10.1145/1993478.1993482

Published: 04 June 2011 Publication History

Abstract

In a parallel, shared-memory, language with a garbage collected heap, it is desirable for each processor to perform minor garbage collections independently. Although obvious, it is difficult to make this idea pay off in practice, especially in languages where mutation is common. We present several techniques that substantially improve the state of the art. We describe these techniques in the context of a full-scale implementation of Haskell, and demonstrate that our local-heap collector substantially improves scaling, peak performance, and robustness.

References

[1]

Todd A. Anderson. Optimizations in a private nursery-based garbage collector. In ISMM '10: Proceedings of the 2010 international symposium on Memory management, pages 21--30. ACM, 2010.

Digital Library

[2]

David F. Bacon, Perry Cheng, and V. T. Rajan. A real-time garbage collector with low overhead and consistent utilization. In Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, POPL '03, pages 285--298, 2003.

Digital Library

[3]

Lars Bergstrom, Mike Rainey, John Reppy, Adam Shaw, and Matthew Fluet. Lazy tree splitting. In Proceedings of the 15th ACM SIGPLAN international conference on Functional programming, ICFP '10, pages 93--104, 2010.

Digital Library

[4]

Stephen M. Blackburn and Kathryn S. McKinley. Immix: a mark-region garbage collector with space efficiency, fast collection, and mutator performance. In Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation, PLDI '08, pages 22--32, 2008.

Digital Library

[5]

Stephen M. Blackburn, Perry Cheng, and Kathryn S. McKinley. Myths and realities: the performance impact of garbage collection. In Proceedings of the joint international conference on Measurement and modeling of computer systems, SIGMETRICS '04/Performance '04, pages 25--36. ACM, 2004.

Digital Library

[6]

Damien Doligez and Xavier Leroy. A concurrent, generational garbage collector for a multithreaded implementation of ML. In POPL '93: Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 113--123, 1993.

Digital Library

[7]

Tamar Domani, Gal Goldshtein, Elliot K. Kolodner, Ethan Lewis, Erez Petrank, and Dafna Sheinwald. Thread-local heaps for java. In ISMM '02: Proceedings of the 3rd international symposium on Memory management, pages 76--87. ACM, 2002.

Digital Library

[8]

Matthew Fluet, Mike Rainey, John Reppy, and Adam Shaw. Implicitly-threaded parallelism in manticore. In Proceeding of the 13th ACM SIGPLAN international conference on Functional programming, ICFP '08, pages 119--130, 2008.

Digital Library

[9]

Richard Jones and Andy C. King. A fast analysis for thread-local garbage collection with dynamic class loading. In Proceedings of the Fifth IEEE International Workshop on Source Code Analysis and Manipulation, pages 129--138, Washington, DC, USA, 2005. IEEE Computer Society.

Digital Library

[10]

Simon Marlow, Simon Peyton Jones, and Wolfgang Thaller. Extending the haskell foreign function interface with concurrency. In Proceedings of the 2004 ACM SIGPLAN workshop on Haskell, Haskell '04, pages 22--32, 2004.

Digital Library

[11]

Simon Marlow, Alexey Rodriguez Yakushev, and Simon Peyton Jones. Faster laziness using dynamic pointer tagging. In Proceedings of the 12th ACM SIGPLAN international conference on Functional programming, ICFP '07, pages 277--288, 2007.

Digital Library

[12]

Simon Marlow, Tim Harris, Roshan P. James, and Simon Peyton Jones. Parallel generational-copying garbage collection with a block-structured heap. In Proceedings of the 7th international symposium on Memory management, ISMM '08, pages 11--20. ACM, 2008.

Digital Library

[13]

Simon Marlow, Simon Peyton Jones, and Satnam Singh. Runtime support for multicore haskell. In Proceedings of the 14th ACM SIGPLAN international conference on Functional programming, ICFP '09, pages 65--78, 2009.

Digital Library

[14]

Pekka P. Pirinen. Barrier techniques for incremental tracing. In Proceedings of the 1st international symposium on Memory management, ISMM '98, pages 20--25. ACM, 1998.

Digital Library

[15]

Bjarne Steensgaard. Thread-specific heaps for multi-threaded programs. In ISMM '00: Proceedings of the 2nd international symposium on Memory management, pages 18--24. ACM, 2000.

Digital Library

[16]

Yi Zhao, Jin Shi, Kai Zheng, Haichuan Wang, Haibo Lin, and Ling Shao. Allocation wall: a limiting factor of java applications on emerging multi-core platforms. In Proceeding of the 24th ACM SIGPLAN conference on Object oriented programming systems languages and applications, OOPSLA '09, pages 361--376, 2009.

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
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
Show More Cited By

Index Terms

Multicore garbage collection with local heaps
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Garbage collection

Recommendations

Multicore garbage collection with local heaps
ISMM '11

In a parallel, shared-memory, language with a garbage collected heap, it is desirable for each processor to perform minor garbage collections independently. Although obvious, it is difficult to make this idea pay off in practice, especially in languages ...
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 ...
Concurrent, parallel, real-time garbage-collection
ISMM '10: Proceedings of the 2010 international symposium on Memory management

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

ISMM '11: Proceedings of the international symposium on Memory management

June 2011

148 pages

ISBN:9781450302630

DOI:10.1145/1993478

General Chair:
Hans-J. Boehm
HP Labs
,
Program Chair:
David Bacon
IBM T.J. Watson Research

ACM SIGPLAN Notices Volume 46, Issue 11
ISMM '11
November 2011
135 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2076022
Issue’s Table of Contents

Copyright © 2011 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 June 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISMM '11

Sponsor:

SIGPLAN

ISMM '11: International Symposium on Memory Management

June 4 - 5, 2011

California, San Jose, USA

Acceptance Rates

Overall Acceptance Rate 72 of 156 submissions, 46%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

56
Total Citations
View Citations
494
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)1

Reflects downloads up to 20 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
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
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
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
Ismail MSuh GMars JTang LXue JWu P(2020)Efficient nursery sizing for managed languages on multi-core processors with shared cachesProceedings of the 18th ACM/IEEE International Symposium on Code Generation and Optimization10.1145/3368826.3377908(1-15)Online publication date: 22-Feb-2020
https://dl.acm.org/doi/10.1145/3368826.3377908
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
Guatto AWestrick SRaghunathan RAcar UFluet M(2018)Hierarchical memory management for mutable stateACM SIGPLAN Notices10.1145/3200691.317849453:1(81-93)Online publication date: 10-Feb-2018
https://dl.acm.org/doi/10.1145/3200691.3178494
Guatto AWestrick SRaghunathan RAcar UFluet MKrall AGross T(2018)Hierarchical memory management for mutable stateProceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3178487.3178494(81-93)Online publication date: 10-Feb-2018
https://dl.acm.org/doi/10.1145/3178487.3178494
Franco JClebsch SDrossopoulou SVitek JWrigstad T(2018)Correctness of a Concurrent Object Collector for Actor LanguagesProgramming Languages and Systems10.1007/978-3-319-89884-1_31(885-911)Online publication date: 14-Apr-2018
https://doi.org/10.1007/978-3-319-89884-1_31
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