[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On the Effects of Integrating Region-Based Memory Management and Generational Garbage Collection in ML

  • Conference paper
  • First Online:
Practical Aspects of Declarative Languages (PADL 2020)

Part of the book series: Lecture Notes in Computer Science ((LNPSE,volume 12007))

Included in the following conference series:

  • 564 Accesses

Abstract

We present a region-based memory management scheme with support for generational garbage collection. The scheme is implemented in the MLKit Standard ML compiler, which features a compile-time region inference algorithm. The compiler generates native x64 machine code and deploys region types at runtime to avoid write barrier problems and to support partly tag-free garbage collection. We measure the characteristics of the scheme, for a number of benchmarks, and compare it to the Mlton state-of-the-art Standard ML compiler and configurations of the MLKit with and without region inference and generational garbage collection enabled. Although region inference often serves the purpose of generations, we demonstrate that, in some cases, generational garbage collection combined with region inference is beneficial.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    In the implementation, the color pointer associated with a region page is located in the header of the page. If colorPtr points past the page, the entire page is black.

References

  1. Aiken, A., Fähndrich, M., Levien, R.: Better static memory management: improving region-based analysis of higher-order languages. In: ACM Conference on Programming Languages and Implementation, PLDI, June 1995

    Google Scholar 

  2. Aldrich, J., Kostadinov, V., Chambers, C.: Alias annotations for program understanding. In: ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA (2002)

    Google Scholar 

  3. Anderson, T.A.: Optimizations in a private nursery-based garbage collector. In: ACM International Symposium on Memory Management, ISMM (2010)

    Google Scholar 

  4. Birkedal, L., Tofte, M., Vejlstrup, M.: From region inference to von Neumann machines via region representation inference. In: ACM Symposium on Principles of Programming Languages, POPL, January 1996

    Google Scholar 

  5. Blanchet, B.: Escape analysis: correctness proof, implementation and experimental results. In: ACM Symposium on Principles of Programming Languages (POPL 1998), pp. 25–37. ACM Press, January 1998

    Google Scholar 

  6. Boyapati, C., Salcianu, A., Beebee Jr., W., Rinard, M.: Ownership types for safe region-based memory management in real-time Java. In: ACM Conference on Programming Language Design and Implementation, PLDI (2003)

    Google Scholar 

  7. Doligez, D., Leroy, X.: A concurrent, generational garbage collector for a multithreaded implementation of ML. In: ACM Symposium on Principles of Programming Languages, POPL (1993)

    Google Scholar 

  8. Elsman, M.: Garbage collection safety for region-based memory management. In: ACM Workshop on Types in Language Design and Implementation. TLDI, January 2003

    Google Scholar 

  9. Elsman, M., Hallenberg, N.: An optimizing backend for the ML Kit using a stack of regions. Student Project 95-7-8, University of Copenhagen (DIKU), 5 July 1995

    Google Scholar 

  10. Elsman, M., Hallenberg, N.: SMLserver–a functional approach to web publishing, 154 p. The IT University of Copenhagen (2002). http://www.smlserver.org

  11. Elsman, M., Hallenberg, N.: Web programming with SMLserver. In: Dahl, V., Wadler, P. (eds.) PADL 2003. LNCS, vol. 2562, pp. 74–91. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36388-2_7

    Chapter  Google Scholar 

  12. Elsman, M., Hallenberg, N.: Combining region inference and generational garbage collection. Technical report 2019/01, Department of Computer Science, University of Copenhagen (DIKU), ISSN 0107–8283, November 2019

    Google Scholar 

  13. Elsman, M., Larsen, K.F.: Typing XHTML web applications in ML. In: Jayaraman, B. (ed.) PADL 2004. LNCS, vol. 3057, pp. 224–238. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24836-1_16

    Chapter  Google Scholar 

  14. Elsman, M., Munksgaard, P., Larsen, K.F.: Experience report: type-safe multi-tier programming with Standard ML modules. In: Proceedings of the ML Family Workshop, ML, September 2018

    Google Scholar 

  15. Gay, D., Aiken, A.: Language support for regions. In: ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2001). ACM Press, Snowbird, June 2001

    Google Scholar 

  16. Hallenberg, N.: A region profiler for a standard ML compiler based on region inference. Student Project 96-5-7, Department of Computer Science, University of Copenhagen (DIKU), June 1996

    Google Scholar 

  17. Hallenberg, N., Elsman, M., Tofte, M.: Combining region inference and garbage collection. In: ACM Conference on Programming Language Design and Implementation (PLDI 2002). ACM Press, Berlin, June 2002

    Google Scholar 

  18. Huelsbergen, L., Winterbottom, P.: Very concurrent mark-&-sweep garbage collection without fine-grain synchronization. In: ACM International Symposium on Memory Management, ISMM (1998)

    Google Scholar 

  19. Jones, R., Hosking, A., Moss, E.: The Garbage Collection Handbook: The Art of Automatic Memory Management. Chapman & Hall/CRC, London (2011)

    Book  Google Scholar 

  20. Jost, S., Hammond, K., Loidl, H.W., Hofmann, M.: Static determination of quantitative resource usage for higher-order programs. In: ACM Symposium on Principles of Programming Languages, POPL (2010)

    Google Scholar 

  21. Marlow, S., Peyton Jones, S.: Multicore garbage collection with local heaps. In: ACM International Symposium on Memory Management, ISMM (2011)

    Google Scholar 

  22. Marlow, S., Peyton Jones, S., Singh, S.: Runtime support for multicore Haskell. In: ACM International Conference on Functional Programming, ICFP (2009)

    Google Scholar 

  23. Reppy, J.H.: A high-performance garbage collector for Standard ML. Technical report, AT&T Bell Laboratories, January 1994

    Google Scholar 

  24. Salagnac, G., Yovine, S., Garbervetsky, D.: Fast escape analysis for region-based memory management. Electron. Notes Theor. Comput. Sci. 131, 99–110 (2005)

    Article  Google Scholar 

  25. Salagnac, G., Nakhli, C., Rippert, C., Yovine, S.: Efficient region-based memory management for resource-limited real-time embedded systems. In: Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems, July 2006

    Google Scholar 

  26. Swamy, N., Hicks, M., Morrisett, G., Grossman, D., Jim, T.: Safe manual memory management in cyclone. Sci. Comput. Program. 62(2), 122–144 (2006)

    Article  MathSciNet  Google Scholar 

  27. Tofte, M., Birkedal, L., Elsman, M., Hallenberg, N.: A retrospective on region-based memory management. Higher-Order Symb. Comput. 17(3), 245–265 (2004)

    Article  Google Scholar 

  28. Tofte, M., Birkedal, L., Elsman, M., Hallenberg, N., Olesen, T.H., Sestoft, P.: Programming with regions in the MLKit (revised for version 4.3.0). Technical report, IT University of Copenhagen, Denmark, January 2006

    Google Scholar 

  29. Ueno, K., Ohori, A.: A fully concurrent garbage collector for functional programs on multicore processors. In: ACM International Conference on Functional Programming, ICFP (2016)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Copenhagen, Copenhagen, Denmark

    Martin Elsman

  2. SimCorp A/S, Copenhagen, Denmark

    Niels Hallenberg

Authors
  1. Martin Elsman
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Niels Hallenberg
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Martin Elsman .

Editor information

Editors and Affiliations

  1. Heriot-Watt University, Edinburgh, UK

    Ekaterina Komendantskaya

  2. Stony Brook University, New York, USA

    Yanhong Annie Liu

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Elsman, M., Hallenberg, N. (2020). On the Effects of Integrating Region-Based Memory Management and Generational Garbage Collection in ML. In: Komendantskaya, E., Liu, Y. (eds) Practical Aspects of Declarative Languages. PADL 2020. Lecture Notes in Computer Science(), vol 12007. Springer, Cham. https://doi.org/10.1007/978-3-030-39197-3_7

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-39197-3_7

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-39196-6

  • Online ISBN: 978-3-030-39197-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation