Stephen M. Blackburn
Perry Cheng
ABSTRACT
This paper explores and quantifies garbage collection behavior for three whole heap collectors and generational counterparts: copying semi-space, mark-sweep, and reference counting, the canonical algorithms from which essentially all other collection algorithms are derived. Efficient implementations in MMTk, a Java memory management toolkit, in IBM's Jikes RVM share all common mechanisms to provide a clean experimental platform. Instrumentation separates collector and program behavior, and performance counters measure timing and memory behavior on three architectures.Our experimental design reveals key algorithmic features and how they match program characteristics to explain the direct and indirect costs of garbage collection as a function of heap size on the SPEC JVM benchmarks. For example, we find that the contiguous allocation of copying collectors attains significant locality benefits over free-list allocators. The reduced collection costs of the generational algorithms together with the locality benefit of contiguous allocation motivates a copying nursery for newly allocated objects. These benefits dominate the overheads of generational collectors compared with non-generational and no collection, disputing the myth that "no garbage collection is good garbage collection." Performance is less sensitive to the mature space collection algorithm in our benchmarks. However the locality and pointer mutation characteristics for a given program occasionally prefer copying or mark-sweep. This study is unique in its breadth of garbage collection algorithms and its depth of analysis.
- B. Alpern et al. Implementing Jalapeño in Java. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 314--324, Denver, CO, Nov. 1999.]] Google Scholar
Digital Library
- B. Alpern et al. The Jalape#241;o virtual machine. IBM Systems Journal, 39(1):211--238, February 2000.]] Google ScholarDigital Library
- A. W. Appel. Simple generational garbage collection and fast allocation. Software Practice and Experience, 19(2):171--183, 1989.]] Google ScholarDigital Library
- M. Arnold, S. J. Fink, D. Grove, M. Hind, and P. Sweeney. Adaptive optimization in the Jalapeño JVM. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 47--65, Minneapolis, MN, October 2000.]] Google ScholarDigital Library
- C. R. Attanasio, D. F. Bacon, A. Cocchi, and S. Smith. A comparative evaluation of parallel garbage collectors. In Languages and Compilers for Parallel Computing, Lecture Notes in Computer Science. Springer-Verlag, 2001.]] Google ScholarDigital Library
- D. Bacon, S. Fink, and D. Grove. Space- and time-efficient implementations of the Java object model. In Proceedings of the European Conference on Object-Oriented Programming (ECOOP), pages 111--132. ACM Press, June 2002.]] Google ScholarDigital Library
- D. F. Bacon and V. T. Rajan. Concurrent cycle collection in reference counted systems. In J. L. Knudsen, editor, Proc. of the 15th ECOOP, volume 2072 of Lecture Notes in Computer Science, pages 207--235. Springer-Verlag, 2001.]] Google ScholarDigital Library
- H. G. Baker. The Treadmill: Real-time garbage collection without motion sickness. ACM SIGPLAN Notices, 27(3):66--70, 1992.]] Google ScholarDigital Library
- E. D. Berger, K. S. McKinley, R. D. Blumofe, and P. R. Wilson. Hoard: A scalable memory allocator for multithreaded applications. In ACM Conference on Architectural Support for Programming Languages and Operating Systems, Cambridge, MA, Nov. 2000.]] Google ScholarDigital Library
- E. D. Berger, B. G. Zorn, and K. S. McKinley. Composing high-performance memory allocators. In ACM SIGPLAN Conference on Programming Languages Design and Implementation, pages 114--124, Salt Lake City, UT, June 2001.]] Google ScholarDigital Library
- E. D. Berger, B. G. Zorn, and K. S. McKinley. Reconsidering custom memory allocation. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 1--12, Seattle, WA, Nov. 2002.]] Google ScholarDigital Library
- S. M. Blackburn, P. Cheng, and K. S. McKinley. Myths and realities: The performance impact of garbage collection. Technical Report TR-CS-04-04, Dept. of Computer Science, Australian National University, 2004.]]Google ScholarDigital Library
- S. M. Blackburn, P. Cheng, and K. S. McKinley. Oil and water? High performance garbage collection in Java with JMTk. In ICSE, Scotland, UK, May 2004.]] Google ScholarDigital Library
- S. M. Blackburn, R. E. Jones, K. S. McKinley, and J. E. B. Moss. Beltway: Getting around garbage collection gridlock. In Proc. of SIGPLAN 2002 Conference on PLDI, pages 153--164, Berlin, Germany, June 2002.]] Google ScholarDigital Library
- S. M. Blackburn and K. S. McKinley. In or out? Putting write barriers in their place. In ACM International Symposium on Memory Management, pages 175--183, Berlin, Germany, June 2002.]] Google ScholarDigital Library
- S. M. Blackburn and K. S. McKinley. Ulterior reference counting: Fast garbage collection without a long wait. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 244--358, Anaheim, CA, Oct. 2003.]] Google ScholarDigital Library
- H.-J. Boehm. Space efficient conservative garbage collection. In ACM SIGPLAN Conference on Programming Languages Design and Implementation, pages 197--206, 1993.]] Google ScholarDigital Library
- T. Brecht, E. Arjomandi, C. Li, and H. Pham. Controlling garbage collection and heap growth to reduce the execution time of Java applications. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 353--366, Tampa, FL, 2001.]] Google ScholarDigital Library
- C. J. Cheney. A non-recursive list compacting algorithm. Communications of the ACM, 13(11):677--8, Nov. 1970.]] Google ScholarDigital Library
- J. Cohen and A. Nicolau. Comparison of compacting algorithms for garbage collection. ACM Transactions on Programming Languages and Systems, 5(4):532--553, Oct. 1983.]] Google ScholarDigital Library
- D. L. Detlefs, A. Dosser, and B. Zorn. Memory allocation costs in large C and C++ programs. Software Practice & Experience, 24(6):527--542, June 1994.]] Google ScholarDigital Library
- L. P. Deutsch and D. G. Bobrow. An efficient incremental automatic garbage collector. Communications of the ACM, 19(9):522--526, September 1976.]] Google ScholarDigital Library
- S. Dieckmann and U. Hölzle. A study of the allocation behavior of the SPECjvm98 Java benchmarks. In Proceedings of the European Conference on Object-Oriented Programming, pages 92--115, June 1999.]] Google ScholarDigital Library
- E. Dijkstra, L. Lamport, A. Martin, C. Scholten, and E. Steffens. On-the-fly garbage collection: An exercise in cooperation. Communications of the ACM, 21(11):966--975, September 1978.]] Google ScholarDigital Library
- A. Diwan, D. Tarditi, and J. E. B. Moss. Memory subsystem performance of programs using copying garbage collection. In Conference Record of the Twenty-First ACM Symposium on Principles of Programming Languages, pages 1--14, Portland, OR, Jan. 1994.]] Google ScholarDigital Library
- L. Eeckhout, A. Georges, and K. D. Bosschere. How Java programs interact with virtual machines at the microarchitectural level. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 244--358, Anaheim, CA, Oct. 2003.]] Google ScholarDigital Library
- R. Fitzgerald and D. Tarditi. The case for profile-directed selection of garbage collectors. In ACM International Symposium on Memory Management, pages 111--120, Minneapolis, MN, Oct. 2000.]] Google ScholarDigital Library
- M. W. Hicks, J. T. Moore, and S. Nettles. The measured cost of copying garbage collection mechanisms. In ACM International Conference on Functional Programming, pages 292--305, 1997.]] Google ScholarDigital Library
- A. L. Hosking and R. L. Hudson. Remembered sets can also play cards, Oct. 1993. Position paper for OOPSLA '93 Workshop on Memory Management and Garbage Collection.]]Google Scholar
- R. E. Jones and R. D. Lins. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. Wiley, July 1996.]] Google ScholarDigital Library
- N. P. Jouppi. Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers. In Proceedings of the 17th International Symposium on Computer Architecture, pages 364--373, Seattle, WA, June 1990.]] Google ScholarDigital Library
- J. Kim and Y. Hsu. Memory system behavior of Java programs: Methodology and analysis. In ACM SIGMETRICS Conference on Measurement & Modeling Computer Systems, pages 264--274, Santa Clara, CA, June 2000.]] Google ScholarDigital Library
- D. Lea. A memory allocator. http://gee.cs.oswego.edu/dl/html/malloc.html, 1997.]]Google Scholar
- Y. Levanoni and E. Petrank. An on-the-fly reference counting garbage collector for Java. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 367--380, Tampa, FL, Oct. 2001.]] Google ScholarDigital Library
- H. Lieberman and C. E. Hewitt. A real time garbage collector based on the lifetimes of objects. Communications of the ACM, 26(6):419--429, 1983.]] Google ScholarDigital Library
- M. Pettersson. Linux Intel/x86 performance counters, 2003. http://user.it.uu.se/ mikpe/linux/perfctr/.]]Google Scholar
- Y. Shuf, M. J. Serran, M. Gupta, and J. P. Singh. Characterizing the memory behavior of Java workloads: A structured view and opportunities for optimizations. In ACM SIGMETRICS Conference on Measurement & Modeling Computer Systems, pages 194--205, Cambridge, MA, June 2001.]] Google ScholarDigital Library
- Standard Performance Evaluation Corporation. SPECjvm98 Documentation, release 1.03 edition, March 1999.]]Google Scholar
- Standard Performance Evaluation Corporation. SPECjbb2000 (Java Business Benchmark) Documentation, release 1.01 edition, 2001.]]Google Scholar
- D. Stefanović, M. Hertz, S. M. Blackburn, K. McKinley, and J. Moss. Older-first garbage collection in practice: Evaluation in a Java virtual machine. In Memory System Performance, pages 175--184, June 2002.]] Google ScholarDigital Library
- D. Tarditi and A. Diwan. Measuring the cost of storage management. Lisp and Symbolic Computation, 9(4), Dec. 1996.]] Google ScholarDigital Library
- D. M. Ungar. Generation scavenging: A non-disruptive high performance storage reclamation algorithm. In ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, pages 157--167, April 1984.]] Google ScholarDigital Library
- B. G. Zorn. The measured cost of conservative garbage collection. Software Practice & Experience, 23(7):733--756, 1993.]] Google ScholarDigital Library
Index Terms
- Myths and realities: the performance impact of garbage collection
Recommendations
Myths and realities: the performance impact of garbage collection
This paper explores and quantifies garbage collection behavior for three whole heap collectors and generational counterparts: copying semi-space, mark-sweep, and reference counting, the canonical algorithms from which essentially all other collection ...
Immix: a mark-region garbage collector with space efficiency, fast collection, and mutator performance
PLDI '08: Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and ImplementationProgrammers are increasingly choosing managed languages for modern applications, which tend to allocate many short-to-medium lived small objects. The garbage collector therefore directly determines program performance by making a classic space-time ...
Immix: a mark-region garbage collector with space efficiency, fast collection, and mutator performance
PLDI '08Programmers are increasingly choosing managed languages for modern applications, which tend to allocate many short-to-medium lived small objects. The garbage collector therefore directly determines program performance by making a classic space-time ...
Reviews
Peter C. Patton
This is a fascinating paper on garbage collection, a subject in which strong opinions are common, but experiential wisdom is rare. The software engineering advantages of garbage collection over programmer directed memory management are generally accepted, but the performance trade-off in languages that have garbage collection is unexplored. This paper reports on extensive experiments that showed a clear mutator performance advantage for contiguous allocation over free-list allocation. Manual allocation using the malloc() and free() methods employs free-list allocation. Hardware architectural trends toward the increasing use of hierarchical cache memory will continue to lean in favor of contiguous allocation, due to the principles of data and task locality. Neither standard manual nor explicit memory management is able to exploit the locality advantages of continuous allocation, so garbage collection will very likely show an even higher performance advantage over manual allocation as computer architecture evolves. Results are given in the paper for several collection algorithms, and thus the paper also provides insights for memory management designers on collection algorithms that could tune themselves to improve performance in long running applications. This is an excellent paper, which is well written and well documented. It represents the state-of-the-art on garbage collection technology. It is a must read for the performance specialist, the software architect, and the hardware architect. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments