Abstract
This paper describes a memory discipline that combines region-based memory management and copying garbage collection by extending Cheney's copying garbage collection algorithm to work with regions. The paper presents empirical evidence that region inference very significantly reduces the number of garbage collections; and evidence that the fastest execution is obtained by using regions alone, without garbage collection. The memory discipline is implemented for Standard ML in the ML Kit compiler and measurements show that for a variety of benchmark programs, code generated by the compiler is as efficient, both with respect to execution time and memory usage, as programs compiled with Standard ML of New Jersey, another state-of-the-art Standard ML compiler.
- Alexander Aiken, Manuel Fähndrich, and Raph Levien. Better static memory management: Improving region-based analysis of higher-order languages. In ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'95), pages 174--185, La Jolla, CA, June 1995. ACM Press Google ScholarDigital Library
- Andrew W. Appel. Compiling with Continuations. Cambridge University Press, 1992 Google ScholarDigital Library
- Lars Birkedal, Mads Tofte, and Magnus Vejlstrup. From region inference to von Neumann machines via region representation inference. In Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 171--183. ACM Press, January 1996 Google ScholarDigital Library
- Bruno Blanchet. Escape analysis : Correctness proof, implementation and experimental results. In Procedings of 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'98), pages 25--37. ACM Press, January 1998 Google ScholarDigital Library
- C. J. Cheney. A non-recursive list compacting algorithm. Communications of the ACM, 13(11):677--678, November 1970 Google ScholarDigital Library
- Martin Elsman. Polymorphic equality---no tags required. In Second International Workshop on Types in Compilation, March 1998 Google ScholarDigital Library
- Martin Elsman. Static interpretation of modules. In Procedings of Fourth International Conference on Functional Programming (ICFP'99), pages 208--219. ACM Press, September 1999 Google ScholarDigital Library
- Martin Elsman and Niels Hallenberg. An optimizing backend for the ML Kit using a stack of regions. Student Project 95-7-8, Department of Computer Science, University of Copenhagen (DIKU), July 5 1995Google Scholar
- David Gay and Alexander Aiken. Memory management with explicit regions. In ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'98), Montreal, Canada, June 1998. ACM Press Google ScholarDigital Library
- David Gay and Alexander Aiken. Language support for regions. In ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'01), Snowbird, Utah, June 2001. ACM Press Google ScholarDigital Library
- D. Grossman, G. Morrisett, T. Jim, M. Hicks, Y. Wang, and J. Cheney. Region-based memory management in Cyclone. In ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'02), Berlin, Germany, 2002. ACM Press Google ScholarDigital Library
- Niels Hallenberg. 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 1996Google Scholar
- Niels Hallenberg. Combining garbage collection and region inference in the ML Kit. Master's thesis, Department of Computer Science, University of Copenhagen, 1999Google Scholar
- Richard Jones and Rafael Lins. Garbage Collection. Wiley, 1996Google Scholar
- Henry Lieberman and Carl Hewitt. A real-time garbage collector based on the lifetimes of objects. Communications of the ACM, 26(6):419--429, June 1983 Google ScholarDigital Library
- Robin Milner, Mads Tofte, Robert Harper, and David MacQueen. The Definition of Standard ML (Revised). MIT Press, 1997 Google ScholarDigital Library
- Mads Tofte and Lars Birkedal. A region inference algorithm. Transactions on Programming Languages and Systems (TOPLAS), 20(4):734--767, July 1998 Google ScholarDigital Library
- Mads Tofte, Lars Birkedal, Martin Elsman, Niels Hallenberg, Tommy~Højfeld Olesen, and Peter Sestoft. Programming with regions in the ML Kit (for version 4). Technical report, IT University of Copenhagen, October 2001Google Scholar
- Mads Tofte and Jean-Pierre Talpin. A theory of stack allocation in polymorphically typed languages. Technical Report DIKU-report 93/15, Department of Computer Science, University of Copenhagen, 1993Google Scholar
- Mads Tofte and Jean-Pierre Talpin. Implementing the call-by-value lambda-calculus using a stack of regions. In Proceedings of the 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 188--201. ACM Press, January 1994 Google ScholarDigital Library
- Mads Tofte and Jean-Pierre Talpin. Region-based memory management. Information and Computation, 132(2):109--176, 1997 Google ScholarDigital Library
- Daniel Wang and Andrew Appel. Type-preserving garbage collection. In Conference Record of the 28th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), pages 166--178. ACM Press, January 2001 Google ScholarDigital Library
- Paul R. Wilson. Uniprocessor garbage collection techniques. In Y. Bekkers and J. Cohen, editors, Memory Management, Proceedings, International Workshop IWMM92, pages 1--42. Springer-Verlag, September 1992 Google ScholarDigital Library
Index Terms
- Combining region inference and garbage collection
Recommendations
Garbage collection safety for region-based memory management
In this paper, we prove the safety of integrating region-based memory management and Cheney-style copying garbage collection. The safety property relies on a refinement of the region typing rules that forbids dangling pointers during evaluation.To ...
Combining region inference and garbage collection
PLDI '02: Proceedings of the ACM SIGPLAN 2002 conference on Programming language design and implementationThis paper describes a memory discipline that combines region-based memory management and copying garbage collection by extending Cheney's copying garbage collection algorithm to work with regions. The paper presents empirical evidence that region ...
Age-based garbage collection
Modern generational garbage collectors look for garbage among the young objects, because they have high mortality; however, these objects include the very youngest objects, which clearly are still live. We introduce new garbage collection algorithms, ...
Comments