research-article

Public Access

Hierarchical memory management for mutable state

Authors:

Ram Raghunathan,

Matthew FluetAuthors Info & Claims

ACM SIGPLAN Notices, Volume 53, Issue 1

Pages 81 - 93

https://doi.org/10.1145/3200691.3178494

Published: 10 February 2018 Publication History

Abstract

It is well known that modern functional programming languages are naturally amenable to parallel programming. Achieving efficient parallelism using functional languages, however, remains difficult. Perhaps the most important reason for this is their lack of support for efficient in-place updates, i.e., mutation, which is important for the implementation of both parallel algorithms and the run-time system services (e.g., schedulers and synchronization primitives) used to execute them.

In this paper, we propose techniques for efficient mutation in parallel functional languages. To this end, we couple the memory manager with the thread scheduler to make reading and updating data allocated by nested threads efficient. We describe the key algorithms behind our technique, implement them in the MLton Standard ML compiler, and present an empirical evaluation. Our experiments show that the approach performs well, significantly improving efficiency over existing functional language implementations.

References

[1]

{n. d.}. Stanford Large Network Dataset Collection. http://snap.stanford.edu/. ({n. d.}).

[2]

Umut A. Acar, Guy Blelloch, Matthew Fluet, and Stefan K. Mullerand Ram Raghunathan. 2015. Coupling Memory and Computation for Locality Management. In Summit on Advances in Programming Languages (SNAPL).

[3]

Umut A. Acar, Guy E. Blelloch, and Robert D. Blumofe. 2002. The Data Locality of Work Stealing. Theory of Computing Systems 35, 3 (2002), 321--347.

[4]

Todd A. Anderson. 2010. Optimizations in a Private Nursery-Based Garbage Collector. In 9th International Symposium on Memory Management, Jan Vitek and Doug Lea (Eds.). ACM Press, Toronto, Canada, 21--30.

Digital Library

[5]

Andrew W. Appel. 1989. Simple Generational Garbage Collection and Fast Allocation. Software: Practice and Experience 19, 2 (1989), 171--183.

Digital Library

[6]

Andrew W. Appel and Zhong Shao. 1996. Empirical and analytic study of stack versus heap cost for languages with closures. Journal of Functional Programming 6, 1 (Jan. 1996), 47--74.

[7]

Sven Auhagen, Lars Bergstrom, Matthew Fluet, and John H. Reppy. 2011. Garbage collection for multicore NUMA machines. In Proceedings of the 2011 ACM SIGPLAN workshop on Memory Systems Performance and Correctness (MSPC). 51--57.

Digital Library

[8]

Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, and Harsha Vardhan Simhadri. 2011. Scheduling irregular parallel computations on hierarchical caches. In Proc. ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 355--366.

Digital Library

[9]

Guy E. Blelloch, Jonathan C. Hardwick, Jay Sipelstein, Marco Zagha, and Siddhartha Chatterjee. 1994. Implementation of a Portable Nested Data-Parallel Language. J. Parallel Distrib. Comput. 21, 1 (1994), 4--14.

Digital Library

[10]

Robert D. Blumofe and Charles E. Leiserson. 1998. Space-Efficient Scheduling of Multithreaded Computations. SIAM J. Comput. 27, 1 (1998), 202--229.

Digital Library

[11]

Robert D. Blumofe and Charles E. Leiserson. 1999. Scheduling multithreaded computations by work stealing. J. ACM 46 (Sept. 1999), 720--748. Issue 5.

Digital Library

[12]

Philippe Charles, Christian Grothoff, Vijay Saraswat, Christopher Donawa, Allan Kielstra, Kemal Ebcioglu, Christoph von Praun, and Vivek Sarkar. 2005. X10: an object-oriented approach to non-uniform cluster computing. In Proceedings of the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications (OOPSLA '05). ACM, 519--538.

Digital Library

[13]

Damien Doligez and Georges Gonthier. 1994. Portable, Unobtrusive Garbage Collection for Multiprocessor Systems. In 21st Annual ACM Symposium on Principles of Programming Languages. ACM Press, Portland, OR, 70--83.

Digital Library

[14]

Damien Doligez and Xavier Leroy. 1993. A Concurrent Generational Garbage Collector for a Multi-Threaded Implementation of ML. In 20th Annual ACM Symposium on Principles of Programming Languages. ACM Press, Charleston, SC, 113--123.

Digital Library

[15]

Tamar Domani, Elliot K. Kolodner, Ethan Lewis, Erez Petrank, and Dafna Sheinwald. 2002. Thread-Local Heaps for Java. In 3rd International Symposium on Memory Management (ACM SIGPLAN Notices 38(2 supplement)), Hans-J. Boehm and David Detlefs (Eds.). ACM Press, Berlin, Germany, 76--87.

Digital Library

[16]

Matthew Fluet, Mike Rainey, John Reppy, and Adam Shaw. 2011. Implicitly threaded parallelism in Manticore. Journal of Functional Programming 20, 5--6 (2011), 1--40.

Digital Library

[17]

golang {n. d.}. The Go Programming Language. https://golang.org. ({n. d.}). Accessed: 2017.

[18]

Marcelo J. R. Gonçalves. 1995. Cache Performance of Programs with Intensive Heap Allocation and Generational Garbage Collection. Ph.D. Dissertation. Department of Computer Science, Princeton University.

[19]

Marcelo J. R. Gonçalves and Andrew W. Appel. 1995. Cache Performance of Fast-Allocating Programs. In Conference on Functional Programming and Computer Architecture. ACM Press, La Jolla, CA, 293--305.

Digital Library

[20]

Adrien Guatto, Sam Westrick, Ram Raghunathan, Umut Acar, and Matthew Fluet. 2018. Hierarchical Memory Management for Mutable State: Extended Technical Appendix. (2018). arXiv:1801.04618

Digital Library

[21]

Maurice Herlihy and Nir Shavit. 2011. The Art of Multiprocessor Programming. Morgan Kaufmann.

Digital Library

[22]

Shams Mahmood Imam and Vivek Sarkar. 2014. Habanero-Java library: a Java 8 framework for multicore programming. In 2014 International Conference on Principles and Practices of Programming on the Java Platform Virtual Machines, Languages and Tools, PPPJ '14. 75--86.

[23]

Richard Jones, Antony Hosking, and Eliot Moss. 2012. The Garbage Collection Handbook: The Art of Automatic Memory Management. Chapman & Hall.

Digital Library

[24]

Gabriele Keller, Manuel M.T. Chakravarty, Roman Leshchinskiy, Simon Peyton Jones, and Ben Lippmeier. 2010. Regular, shape-polymorphic, parallel arrays in Haskell. In Proceedings of the 15th ACM SIGPLAN international conference on Functional programming (ICFP '10). 261--272.

Digital Library

[25]

Matthew Le and Matthew Fluet. 2015. Partial Aborts for Transactions via First-class Continuations. In Proceedings of the 20th ACM SIGPLAN International Conference on Functional Programming (ICFP 2015). 230--242.

Digital Library

[26]

Doug Lea. 2000. A Java fork/join framework. In Proceedings of the ACM 2000 conference on Java Grande (JAVA '00). 36--43.

Digital Library

[27]

Daan Leijen, Wolfram Schulte, and Sebastian Burckhardt. 2009. The design of a task parallel library. In Proceedings of the 24th ACM SIGPLAN conference on Object Oriented Programming Systems Languages and Applications (OOPSLA '09). 227--242.

Digital Library

[28]

Simon Marlow and Simon L. Peyton Jones. 2011. Multicore Garbage Collection with Local Heaps. In 10th International Symposium on Memory Management, Hans Boehm and David Bacon (Eds.). ACM Press, San Jose, CA, 21--32.

Digital Library

[29]

MLton {n. d.}. MLton web site. http://www.mlton.org. ({n. d.}).

[30]

Ryan Newton. 2017. (2017). Indiana University. Personal Communication.

[31]

Rishiyur S. Nikhil. 1991. Id Language Reference Manual. (1991).

[32]

Ram Raghunathan, Stefan K. Muller, Umut A. Acar, and Guy Blelloch. 2016. Hierarchical Memory Management for Parallel Programs. In ICFP 2016. ACM Press.

Digital Library

[33]

K. C. Sivaramakrishnan, Lukasz Ziarek, and Suresh Jagannathan. 2014. MultiMLton: A multicore-aware runtime for standard ML. Journal of Functional Programming FirstView (6 2014), 1--62.

[34]

Daniel Spoonhower, Guy E. Blelloch, Robert Harper, and Phillip B. Gibbons. 2010. Space profiling for parallel functional programs. Journal of Functional Programming 20 (2010), 417--461. Issue Special Issue 5--6.

Digital Library

[35]

Philip Wadler. 1998. Why No One Uses Functional Languages. SIGPLAN Notices 33, 8 (1998), 23--27.

Digital Library

Cited By

Wilkins MWeil GArnold LHardavellas NDinda P(2023)Evaluating Functional Memory-Managed Parallel Languages for HPC using the NAS Parallel Benchmarks2023 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)10.1109/IPDPSW59300.2023.00072(413-422)Online publication date: May-2023
https://doi.org/10.1109/IPDPSW59300.2023.00072
Moine AWestrick SBalzer S(2024)DisLog: A Separation Logic for DisentanglementProceedings of the ACM on Programming Languages10.1145/36328538:POPL(302-331)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632853
Arora JWestrick SAcar U(2023)Efficient Parallel Functional Programming with EffectsProceedings of the ACM on Programming Languages10.1145/35912847:PLDI(1558-1583)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591284
Show More Cited By

Index Terms

Hierarchical memory management for mutable state
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Functional languages
        Parallel programming languages
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Garbage collection

Recommendations

Hierarchical memory management for mutable state
PPoPP '18: Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

It is well known that modern functional programming languages are naturally amenable to parallel programming. Achieving efficient parallelism using functional languages, however, remains difficult. Perhaps the most important reason for this is their ...
Quantifying the performance of garbage collection vs. explicit memory management
Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming systems languages and applications

Garbage collection yields numerous software engineering benefits, but its quantitative impact on performance remains elusive. One can compare the cost of conservative garbage collection to explicit memory management in C/C++ programs by linking in an ...
Quantifying the performance of garbage collection vs. explicit memory management
OOPSLA '05: Proceedings of the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications

Garbage collection yields numerous software engineering benefits, but its quantitative impact on performance remains elusive. One can compare the cost of conservative garbage collection to explicit memory management in C/C++ programs by linking in an ...

Comments

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 53, Issue 1

PPoPP '18

January 2018

426 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/3200691

Editor:
Matthew Fluet
Rodchester Institude of Technology

Issue’s Table of Contents

PPoPP '18: Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
February 2018
442 pages
ISBN:9781450349826
DOI:10.1145/3178487
General Chair:
Andreas Krall
Vienna University of Technology, Austria
,
Program Chair:
Thomas R. Gross
ETH Zürich, Switzerland

Copyright © 2018 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 the author(s) 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: 10 February 2018

Published in SIGPLAN Volume 53, Issue 1

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

German Research Council (DFG)
National Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
416
Total Downloads

Downloads (Last 12 months)58
Downloads (Last 6 weeks)19

Reflects downloads up to 01 Aug 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wilkins MWeil GArnold LHardavellas NDinda P(2023)Evaluating Functional Memory-Managed Parallel Languages for HPC using the NAS Parallel Benchmarks2023 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)10.1109/IPDPSW59300.2023.00072(413-422)Online publication date: May-2023
https://doi.org/10.1109/IPDPSW59300.2023.00072
Moine AWestrick SBalzer S(2024)DisLog: A Separation Logic for DisentanglementProceedings of the ACM on Programming Languages10.1145/36328538:POPL(302-331)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632853
Arora JWestrick SAcar U(2023)Efficient Parallel Functional Programming with EffectsProceedings of the ACM on Programming Languages10.1145/35912847:PLDI(1558-1583)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591284
Wilkins MWestrick SKandiah VBernat ASuchy BDeiana ECampanoni SAcar UDinda PHardavellas NDubach CBruening DHardekopf B(2023)WARDen: Specializing Cache Coherence for High-Level Parallel LanguagesProceedings of the 21st ACM/IEEE International Symposium on Code Generation and Optimization10.1145/3579990.3580013(122-135)Online publication date: 17-Feb-2023
https://dl.acm.org/doi/10.1145/3579990.3580013
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
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
Rainey MNewton RHale KHardavellas NCampanoni SDinda PAcar UFreund SYahav E(2021)Task parallel assembly language for uncompromising parallelismProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3460969(1064-1079)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3460969
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
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
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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

Media

Figures

Other

Tables

View Issue’s Table of Contents