Niels Hallenberg
Martin Elsman
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 Scholar
Digital 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
Combining region inference and garbage collection
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 ...
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, ...
Age-based garbage collection
OOPSLA '99: Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applicationsModern 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