Darko Stefanovic
J. Eliot B. Moss
Skip Abstract Section
Abstract
We describe a method of measuring lifetime characteristics of heap objects, and discuss ways in which such quantitative object behaviour measurements can help improve language implementations, especially garbage collection performance. For Standard ML of New Jersey, we find that certain primary aspects of object behaviour are qualitatively the same across benchmark programs, in particular the rapid object decay. We show that the heap-only allocation implementation model is the cause of this similarity. We confirm the weak generational hypothesis for SML/NJ and discuss garbage collector configuration tuning. Our approach is to obtain object statistics directly from program execution, rather than simulation, for reasons of simplicity and speed. Towards this end, we exploit the flexibility of the garbage collector toolkit as a measurement tool. Careful numerical analysis of the acquired data is necessary to arrive at relevant object lifetime measures. This study fills a gap in quantitative knowledge of the workings of heap-based compilers and their run-time systems, and should be useful to functional language implementors.
- 1 Andrew W. Appel. Simple generational garbage collection and fast allocation. Software--Practice and Experience, 19(2):171-83, i989. Google Scholar
Digital Library
- 2 Andrew W. Appel. Compiling with Continuations. Cambridge University Press, first edition, 1992. Google ScholarDigital Library
- 3 Andrew W. Appel, James S. Mattson, and David Tarditi. A lexical analyzer generator for Standard ML. Distributed with Standard ML of New Jersey, 1989.Google Scholar
- 4 Andrew W. Appel and Zhong Shao. An empirical and analytic study of stack vs. heap cost for languages with closures. Technical Report CS-TR-450-94, Dept. of Computer Science, Princeton University, Princeton, NJ, 1994.Google Scholar
- 5 Henry Baker. The thermodynamics of garbage collection- a tutorial. In OOPSLA '93 Workshop on Memory Management and Garbage Collection, September 1993.Google Scholar
- 6 Henry G. Baker. 'Infant Mortality' and generational garbage collection. SIGPLAN Notices, 28(4):55-57, 1993. Google ScholarDigital Library
- 7 Yves Bekkers and Jacques Cohen, editors. International Workshop on Memory Management, number 637 in Lecture Notes in Computer Science, St. Malo, France, September 1992. Springer-Verlag. Google ScholarDigital Library
- 8 Rance Cleaveland, Joachim Parrow, and Bernhard Steffen. The Concurrency Workbench: A semantics-based tool for the verification of concurrent systems. Transactions on Programming Languages and Systems, 15(1):36-72, January 1993. Google ScholarDigital Library
- 9 Eric Cooper, Scott Nettles, and Indira Subramanian. Improving the performance of SML garbage collection using application-specific virtual memory management. In 1992 A CM Conference on Lisp and Functional Programming, pages 43-52, San Francisco, California, June 1992. Google ScholarDigital Library
- 10 W. P. Crowley, C. P. Hendrickson, and T. E. Rudy. The SIM- PLE code. Technical Report UCID 17715, Lawrence Livermore Laboratory, Livermore, CA, February 1978.Google Scholar
- 11 Amer Diwan, David Tarditi, and J. Eliot B. Moss. Memory subsystem performance of programs with intensive heap allocation. Submitted for Publication, October 1993.Google ScholarCross Ref
- 12 Amer Diwan, David Tarditi, and J. Eliot B. Moss. Memory subsystem performance of programs using copying garbage collection. In Conference Record of the Twenty-First A CM Symposium on Principles of Programming Languages, Portland, Oregon, January 1994. Google ScholarDigital Library
- 13 K. Ekanadham and Arvind. SIMPLE: An exercise in future scientific programming. Technical Report Computation Structures Group Memo 273, MIT, Cambridge, MA, July 1987. Simultaneously published as IBM/T. J. Watson Research Center Research Report 12686, Yorktown Heights, NY.Google Scholar
- 14 Barry Hayes. Using key object opportunism to collect old objects. In Proceedings of the Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 33--46, Phoenix, Arizona, October 199 i. A CM SIGPLAN Not. 26, 11 (November 1991). Google ScholarDigital Library
- 15 Antony L. Hosking, J. Eliot B. Moss, and Darko Stefanovi& A comparative performance evaluation of write barrier implementations. In Proceedings of the Conference on Object- Oriented Programming Systems, Languages, and Applications, pages 92-I 09, Vancouver, Canada, October 1992. A CM SIGPLAN Not. 27, 10 (October 1992). Google ScholarDigital Library
- 16 Richard L. Hudson, J. Eliot B. Moss, Amer Diwan, and Christopher F. Weight. A language-independent garbage collector toolkit. COINS Technical Report 91-47, University of Massachusetts, Amherst, September 1991. Google ScholarDigital Library
- 17 Peter Lancaster and Kcstutis galkauskas. Curve and Surface Fitting. Academic Press, 1986.Google Scholar
- 18 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
- 19 Frederick Mosteller and John W. Tukey. Data Analysis and Regression. Addison-Wesley, 1977.Google Scholar
- 20 Scott M. Nettles, James W. O'Toole, David Pierce, and Nicholas Haines. Replication-based incremental copying collection. In Bekkers and Cohen {7}, pages 357-364. Google Scholar
- 21 G.A.F. Seber and C.J. Wild. Nonlinear Regression. Wiley, 1989.Google ScholarCross Ref
- 22 Darko Stefanovi& The garbage collection toolkit as an experimentation tool, October 1993. Position paper for OOPSLA '93 Workshop on Memory Management and Garbage Collection.Google Scholar
- 23 Darko Stefanovid. Implementing a small imperative language with safe dynamic allocation. Memo, April 1993.Google Scholar
- 24 David Tarditi and Andrew W. Appel. ML-Yacc, version 2.0. Distributed with Standard ML of New Jersey, April 1990.Google Scholar
- 25 David Tarditi and Amer Diwan. The full cost of a generational copying garbage collection implementation, October 1993. Position paper for OOPSLA '93 Workshop on Memory Management and Garbage Collection.Google Scholar
- 26 David Ungar. Generation scavenging: A non-disruptive high performance storage reclamation algorithm. In Proceedings of the A CM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, pages i57-167, Pittsburgh, Pennsylvania, April 1984. ACM SIG- PLAN Not. 19, 5 (May 1984). Google ScholarDigital Library
- 27 David Michael Ungar. The Design and Evaluation of a High Performance SmaUtalk System. ACM Distinguished Dissertations. The MIT Press, Cambridge, MA, 1987. Ph.D. Dissertation, University of California at Berkeley, February 1986. Google ScholarDigital Library
- 28 Kevin G. Waugh, Patrick McAndrew, and Greg Michaelson. Parallel implementations from function prototypes: a case study. Technical Report Computer Science 90/4, Heriot-Watt University, Edinburgh, August 1990.Google Scholar
- 29 Paul R. Wilson. Uniprocessor garbage collection techniques. In Bekkers and Cohen {7}. Google ScholarDigital Library
- 30 Paul R. Wilson and Thomas G. Moher. Design of the Opportunistic Garbage Collector. In Proceedings of the Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 23-35, New Orleans, Louisiana, October 1989. ACM SIGPLAN Not. 24, 10 (October 1989). Google ScholarDigital Library
- 31 Benjamin Zorn. Comparative Performance Evaluation of Garbage Collection Algorithms. PhD thesis, University of California at Berkeley, December 1989. Available as Technical Report UCB/CSD 89/544. Google ScholarDigital Library
Index Terms
- Characterization of object behaviour in Standard ML of New Jersey
Recommendations
Characterization of object behaviour in Standard ML of New Jersey
LFP '94: Proceedings of the 1994 ACM conference on LISP and functional programmingWe describe a method of measuring lifetime characteristics of heap objects, and discuss ways in which such quantitative object behaviour measurements can help improve language implementations, especially garbage collection performance. For Standard ML ...
A New Backend for Standard ML of New Jersey
IFL '20: Proceedings of the 32nd Symposium on Implementation and Application of Functional LanguagesThis paper describes the design and implementation of a new backend for the Standard ML of New Jersey (SML/NJ) system that is based on the LLVM compiler infrastructure. We first describe the history and design of the current backend, which is based on ...
Comments