Concurrent and parallel garbage collection for lightweight threads on multicore processors
Pages 29 - 42
Abstract
This paper develops a concurrent and parallel garbage collection (GC) method that works with a lightweight thread library realizing the standard M:N threading model. The GC algorithm is organized as a set of procedures that are called from a user-level thread at various occasions and executed in the context of the OS-level threads owning the user-level thread. The procedures realize an on-the-fly collection that does not stop any thread. All OS-level threads cooperatively perform the collection in parallel. This construction achieves the same degree of parallelism as underlying lightweight thread scheduling. We have implemented the algorithm in a Standard ML compiler and have evaluated the performance with sequential and parallel benchmark programs. Our implementation shows good parallel scalability comparable to C programs directly using the lightweight threads library.
References
[1]
Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt, and Nir Shavit. 1993. Atomic Snapshots of Shared Memory. J. ACM, 40, 4 (1993), Sept., 873–890. issn:0004-5411 https://doi.org/10.1145/153724.153741
[2]
Sven Auhagen, Lars Bergstrom, Matthew Fluet, and John Reppy. 2011. Garbage Collection for Multicore NUMA Machines. In Proceedings of the 2011 ACM SIGPLAN Workshop on Memory Systems Performance and Correctness (MSPC ’11). ACM, New York, NY, USA. 51–57. isbn:978-1-4503-0794-9 https://doi.org/10.1145/1988915.1988929
[3]
The Go Authors. 2022. Source file src/runtime/mgc.go. https://go.dev/src/runtime/mgc.go
[4]
Hezi Azatchi, Yossi Levanoni, Harel Paz, and Erez Petrank. 2003. 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 (OOPSLA ’03). ACM, New York, NY, USA. 269–281. isbn:1-58113-712-5 https://doi.org/10.1145/949305.949329
[5]
Katherine Barabash, Ori Ben-Yitzhak, Irit Goft, Elliot K. Kolodner, Victor Leikehman, Yoav Ossia, Avi Owshanko, and Erez Petrank. 2005. A Parallel, Incremental, Mostly Concurrent Garbage Collector for Servers. ACM Trans. Program. Lang. Syst., 27, 6 (2005), Nov., 1097–1146. issn:0164-0925 https://doi.org/10.1145/1108970.1108972
[6]
Guy E. Blelloch, Jonathan C. Hardwick, Siddhartha Chatterjee, Jay Sipelstein, and Marco Zagha. 1993. Implementation of a Portable Nested Data-parallel Language. In Proceedings of the Fourth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP ’93). ACM, New York, NY, USA. 102–111. isbn:0-89791-589-5 https://doi.org/10.1145/155332.155343
[7]
Robert D. Blumofe, Christopher F. Joerg, Bradley C. Kuszmaul, Charles E. Leiserson, Keith H. Randall, and Yuli Zhou. 1995. Cilk: An Efficient Multithreaded Runtime System. In Proceedings of the Fifth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP ’95). ACM, New York, NY, USA. 207–216. isbn:0-89791-700-6 https://doi.org/10.1145/209936.209958
[8]
Hans-J. Boehm, Alan J. Demers, and Scott Shenker. 1991. Mostly parallel garbage collection. In Proceedings of the ACM SIGPLAN 1991 conference on Programming Language Design and Implementation (PLDI ’91). ACM, New York, NY, USA. 157–164. isbn:0-89791-428-7 https://doi.org/10.1145/113445.113459
[9]
Manuel M. T. Chakravarty, Gabriele Keller, Roman Lechtchinsky, and W. Pfannenstiel. 2001. Nepal - Nested Data Parallelism in Haskell. In Proceedings of the 7th International Euro-Par Conference Manchester on Parallel Processing (Euro-Par ’01). Springer-Verlag, London, UK, UK. 524–534. isbn:3-540-42495-4 https://doi.org/10.1007/3-540-44681-8_76
[10]
P. Cheng and G.E. Blelloch. 2001. A Parallel, Realtime Garbage Collector. In Proceedings of the ACM SIGPLAN Conference on Programming language design and implementation (PLDI ’01). https://doi.org/10.1145/381694.378823
[11]
David Detlefs, Christine Flood, Steve Heller, and Tony Printezis. 2004. Garbage-first garbage collection. In Proceedings of the 4th International Symposium on Memory Management (ISMM ’04). ACM, New York, NY, USA. 37–48. isbn:1-58113-945-4 https://doi.org/10.1145/1029873.1029879
[12]
Edsger W. Dijkstra, Leslie Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens. 1978. On-the-fly Garbage Collection: An Exercise in Cooperation. Commun. ACM, 21, 11 (1978), Nov., 966–975. issn:0001-0782 https://doi.org/10.1145/359642.359655
[13]
Damien Doligez and Georges Gonthier. 1994. Portable, unobtrusive garbage collection for multiprocessor systems. In Proceedings of the 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’94). ACM, New York, NY, USA. 70–83. isbn:0-89791-636-0 https://doi.org/10.1145/174675.174673
[14]
Damien Doligez and Xavier Leroy. 1993. 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 (POPL ’93). ACM, New York, NY, USA. 113–123. isbn:0-89791-560-7 https://doi.org/10.1145/158511.158611
[15]
Tamar Domani, Elliot K. Kolodner, Ethan Lewis, Eliot E. Salant, Katherine Barabash, Itai Lahan, Yossi Levanoni, Erez Petrank, and Igor Yanorer. 2000. Implementing an On-the-fly Garbage Collector for Java. In Proceedings of the 2nd International Symposium on Memory Management (ISMM ’00). ACM, New York, NY, USA. 155–166. isbn:1-58113-263-8 https://doi.org/10.1145/362422.362484
[16]
Toshio Endo, Kenjiro Taura, and Akinori Yonezawa. 1997. A Scalable Mark-Sweep Garbage Collector on Large-Scale Shared-Memory Machines. In Proceedings of the 1997 ACM/IEEE Conference on Supercomputing (SC ’97). Association for Computing Machinery, New York, NY, USA. 1–14. isbn:0897919858 https://doi.org/10.1145/509593.509641
[17]
Matthew Fluet, Mike Rainey, John Reppy, and Adam Shaw. 2010. Implicitly Threaded Parallelism in Manticore. J. Funct. Program., 20, 5-6 (2010), Nov., 537–576. issn:0956-7968 https://doi.org/10.1017/S0956796810000201
[18]
Adrien Guatto, Sam Westrick, Ram Raghunathan, Umut Acar, and Matthew Fluet. 2018. Hierarchical Memory Management for Mutable State. In Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP ’18). ACM, New York, NY, USA. 81–93. isbn:978-1-4503-4982-6 https://doi.org/10.1145/3178487.3178494
[19]
Richard L. Hudson and J. Eliot B. Moss. 2001. Sapphire: Copying GC Without Stopping the World. In Proceedings of the 2001 Joint ACM-ISCOPE Conference on Java Grande (JGI ’01). ACM, New York, NY, USA. 48–57. isbn:1-58113-359-6 https://doi.org/10.1145/376656.376810
[20]
Doug Lea. 2000. A Java Fork/Join Framework. In Proceedings of the ACM 2000 Conference on Java Grande (JAVA ’00). ACM, New York, NY, USA. 36–43. isbn:1-58113-288-3 https://doi.org/10.1145/337449.337465
[21]
Yossi Levanoni and Erez Petrank. 2006. An on-the-fly reference-counting garbage collector for Java. ACM Trans. Program. Lang. Syst., 28, 1 (2006), Jan., 1–69. issn:0164-0925 https://doi.org/10.1145/1111596.1111597
[22]
Simon Marlow, Tim Harris, Roshan P. James, and Simon Peyton Jones. 2008. Parallel generational-copying garbage collection with a block-structured heap. In Proceedings of the 7th international symposium on Memory management (ISMM ’08). ACM, New York, NY, USA. 11–20. isbn:978-1-60558-134-7 https://doi.org/10.1145/1375634.1375637
[23]
Simon Marlow and Simon Peyton Jones. 2011. Multicore garbage collection with local heaps. In Proceedings of the international symposium on Memory management (ISMM ’11). ACM, New York, NY, USA. 21–32. isbn:978-1-4503-0263-0 https://doi.org/10.1145/1993478.1993482
[24]
Simon Marlow, Simon Peyton Jones, and Satnam Singh. 2009. Runtime Support for Multicore Haskell. In Proceedings of the 14th ACM SIGPLAN International Conference on Functional Programming (ICFP ’09). ACM, New York, NY, USA. 65–78. isbn:978-1-60558-332-7 https://doi.org/10.1145/1596550.1596563
[25]
Jun Nakashima and Kenjiro Taura. 2014. MassiveThreads: A Thread Library for High Productivity Languages. In Concurrent Objects and Beyond (Lecture Notes in Computer Science, Vol. 8665). 222–238. https://doi.org/10.1007/978-3-662-44471-9_10
[26]
Simon Peyton Jones, Andrew Gordon, and Sigbjorn Finne. 1996. Concurrent Haskell. In Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’96). ACM, New York, NY, USA. 295–308. isbn:0-89791-769-3 https://doi.org/10.1145/237721.237794
[27]
Chuck Pheatt. 2008. Intel® Threading Building Blocks. J. Comput. Sci. Coll., 23, 4 (2008), April, 298–298. issn:1937-4771 http://dl.acm.org/citation.cfm?id=1352079.1352134
[28]
Ram Raghunathan, Stefan K. Muller, Umut A. Acar, and Guy Blelloch. 2016. Hierarchical Memory Management for Parallel Programs. In Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming (ICFP 2016). Association for Computing Machinery, New York, NY, USA. 392–406. isbn:9781450342193 https://doi.org/10.1145/2951913.2951935
[29]
John Reppy, Claudio V. Russo, and Yingqi Xiao. 2009. Parallel Concurrent ML. In Proceedings of the 14th ACM SIGPLAN International Conference on Functional Programming (ICFP ’09). ACM, New York, NY, USA. 257–268. isbn:978-1-60558-332-7 https://doi.org/10.1145/1596550.1596588
[30]
John H. Reppy. 1991. CML: A Higher Concurrent Language. In Proceedings of the ACM SIGPLAN 1991 Conference on Programming Language Design and Implementation (PLDI ’91). ACM, New York, NY, USA. 293–305. isbn:0-89791-428-7 https://doi.org/10.1145/113445.113470
[31]
Konstantinos Sagonas and Jesper Wilhelmsson. 2004. Message analysis-guided allocation and low-pause incremental garbage collection in a concurrent language. In Proceedings of the 4th International Symposium on Memory Management (ISMM ’04). ACM, New York, NY, USA. 1–12. isbn:1-58113-945-4 https://doi.org/10.1145/1029873.1029875
[32]
Sangmin Seo, Abdelhalim Amer, Pavan Balaji, Cyril Bordage, George Bosilca, Alex Brooks, Philip H. Carns, Adrián Castelló, Damien Genet, Thomas Hérault, Shintaro Iwasaki, Prateek Jindal, Laxmikant V. Kalé, Sriram Krishnamoorthy, Jonathan Lifflander, Huiwei Lu, Esteban Meneses, Marc Snir, Yanhua Sun, Kenjiro Taura, and Peter H. Beckman. 2018. Argobots: A Lightweight Low-Level Threading and Tasking Framework. IEEE Trans. Parallel Distrib. Syst., 29, 3 (2018), 512–526. https://doi.org/10.1109/TPDS.2017.2766062
[33]
KC Sivaramakrishnan, Stephen Dolan, Leo White, Sadiq Jaffer, Tom Kelly, Anmol Sahoo, Sudha Parimala, Atul Dhiman, and Anil Madhavapeddy. 2020. Retrofitting Parallelism onto OCaml. Proc. ACM Program. Lang., 4, ICFP (2020), Article 113, Aug., 30 pages. https://doi.org/10.1145/3408995
[34]
K. C. Sivaramakrishnan, Lukasz Ziarek, and Suresh Jagannathan. 2014. MultiMLton: A multicore-aware runtime for Standard ML. J. Funct. Program., 24, 6 (2014), 613–674. https://doi.org/10.1017/S0956796814000161
[35]
Katsuhiro Ueno and Atsushi Ohori. 2016. A Fully Concurrent Garbage Collector for Functional Programs on Multicore Processors. In Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming (ICFP 2016). ACM, New York, NY, USA. 421–433. isbn:978-1-4503-4219-3 https://doi.org/10.1145/2951913.2951944
[36]
Katsuhiro Ueno, Atsushi Ohori, and Toshiaki Otomo. 2011. An efficient non-moving garbage collector for functional languages. In Proceedings of the 16th ACM SIGPLAN international conference on Functional programming (ICFP ’11). ACM, New York, NY, USA. 196–208. isbn:978-1-4503-0865-6 https://doi.org/10.1145/2034773.2034802
[37]
Tomoharu Ugawa, Carl G. Ritson, and Richard E. Jones. 2018. Transactional Sapphire: Lessons in High-Performance, On-the-fly Garbage Collection. ACM Trans. Program. Lang. Syst., 40, 4 (2018), Article 15, Dec., 56 pages. issn:0164-0925 https://doi.org/10.1145/3226225
[38]
Sam Westrick, Rohan Yadav, Matthew Fluet, and Umut A. Acar. 2019. Disentanglement in Nested-Parallel Programs. Proc. ACM Program. Lang., 4, POPL (2019), Article 47, Dec., 32 pages. https://doi.org/10.1145/3371115
[39]
K.B. Wheeler, R.C. Murphy, and D. Thain. 2008. Qthreads: An API for Programming with Millions of Lightweight Threads. In IPDPS. 1–8.
[40]
Taiichi Yuasa. 1990. Real-time garbage collection on general-purpose machines. Journal of Systems and Software, 11, 3 (1990), 181 – 198. issn:0164-1212 https://doi.org/10.1016/0164-1212(90)90084-Y
[41]
Siyao Zheng, Xiang Long, and Jingwei Yang. 2013. Using Many-core Coprocessor to Boost Up Erlang VM. In Proceedings of the Twelfth ACM SIGPLAN Workshop on Erlang (Erlang ’13). ACM, New York, NY, USA. 3–14. isbn:978-1-4503-2385-7 https://doi.org/10.1145/2505305.2505307
Index Terms
- Concurrent and parallel garbage collection for lightweight threads on multicore processors
Recommendations
A fully concurrent garbage collector for functional programs on multicore processors
ICFP 2016: Proceedings of the 21st ACM SIGPLAN International Conference on Functional ProgrammingThis 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 ...
Concurrent, parallel, real-time garbage-collection
ISMM '10With 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 managementWith 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
June 2022
56 pages
Copyright © 2022 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
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 14 June 2022
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
ISMM '22
Sponsor:
ISMM '22: 2022 ACM SIGPLAN International Symposium on Memory Management
June 14, 2022
CA, San Diego, USA
Acceptance Rates
Overall Acceptance Rate 72 of 156 submissions, 46%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 173Total Downloads
- Downloads (Last 12 months)57
- Downloads (Last 6 weeks)6
Reflects downloads up to 18 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in