Myths and realities: the performance impact of garbage collection

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.

REFERENCES

• 1: Bowen Alpern , C. R. Attanasio , Anthony Cocchi , Derek Lieber , Stephen Smith , Ton Ngo , John J. Barton , Susan Flynn Hummel , Janice C. Sheperd , Mark Mergen, Implementing jalapeño in Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.314-324, November 01-05, 1999, Denver, Colorado, United States
• 2: B. Alpern , C. R. Attanasio , J. J. Barton , M. G. Burke , P. Cheng , J.-D. Choi , A. Cocchi , S. J. Fink , D. Grove , M. Hind , S. F. Hummel , D. Lieber , V. Litvinov , M. F. Mergen , T. Ngo , J. R. Russell , V. Sarkar , M. J. Serrano , J. C. Shepherd , S. E. Smith , V. C. Sreedhar , H. Srinivasan , J. Whaley, The Jalapeño virtual machine, IBM Systems Journal, v.39 n.1, p.211-238, January 2000
• 3: A. W. Appel, Simple generational garbage collection and fast allocation, Software—Practice & Experience, v.19 n.2, p.171-183, February 1989 [doi>10.1002/spe.4380190206]
• 4: Matthew Arnold , Stephen Fink , David Grove , Michael Hind , Peter F. Sweeney, Adaptive optimization in the Jalapeño JVM, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.47-65, October 2000, Minneapolis, Minnesota, United States
• 5: 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.
• 6: David F. Bacon , Stephen J. Fink , David Grove, Space- and Time-Efficient Implementation of the Java Object Model, Proceedings of the 16th European Conference on Object-Oriented Programming, p.111-132, June 10-14, 2002
• 7: David F. Bacon , V. T. Rajan, Concurrent Cycle Collection in Reference Counted Systems, Proceedings of the 15th European Conference on Object-Oriented Programming, p.207-235, June 18-22, 2001
• 8: Henry G. Baker, The treadmill: real-time garbage collection without motion sickness, ACM SIGPLAN Notices, v.27 n.3, p.66-70, March 1992 [doi>10.1145/130854.130862]
• 9: Emery D. Berger , Kathryn S. McKinley , Robert D. Blumofe , Paul R. Wilson, Hoard: a scalable memory allocator for multithreaded applications, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.117-128, November 2000, Cambridge, Massachusetts, United States
• 10: Emery D. Berger , Benjamin G. Zorn , Kathryn S. McKinley, Composing high-performance memory allocators, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.114-124, June 2001, Snowbird, Utah, United States
• 11: Emery D. Berger , Benjamin G. Zorn , Kathryn S. McKinley, Reconsidering custom memory allocation, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 12: 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.
• 13: 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.
• 14: Stephen M Blackburn , Richard Jones , Kathryn S. McKinley , J Eliot B Moss, Beltway: getting around garbage collection gridlock, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 15: Stephen M Blackburn , Kathryn S. McKinley, In or out?: putting write barriers in their place, Proceedings of the 3rd international symposium on Memory management, June 20-21, 2002, Berlin, Germany
• 16: Stephen M. Blackburn , Kathryn S. McKinley, Ulterior reference counting: fast garbage collection without a long wait, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 17: Hans-Juergen Boehm, Space efficient conservative garbage collection, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.197-206, June 21-25, 1993, Albuquerque, New Mexico, United States
• 18: Tim Brecht , Eshrat Arjomandi , Chang Li , Hang Pham, Controlling garbage collection and heap growth to reduce the execution time of Java applications, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.353-366, October 14-18, 2001, Tampa Bay, FL, USA
• 19: C. J. Cheney, A nonrecursive list compacting algorithm, Communications of the ACM, v.13 n.11, p.677-678, Nov 1970 [doi>10.1145/362790.362798]
• 20: Jacques Cohen , Alexandru Nicolau, Comparison of Compacting Algorithms for Garbage Collection, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.4, p.532-553, Oct. 1983 [doi>10.1145/69575.357226]
• 21: David Detlefs , Al Dosser , Benjamin Zorn, Memory allocation costs in large C and C++ programs, Software—Practice & Experience, v.24 n.6, p.527-542, June 1994 [doi>10.1002/spe.4380240602]
• 22: L. Peter Deutsch , Daniel G. Bobrow, An efficient, incremental, automatic garbage collector, Communications of the ACM, v.19 n.9, p.522-526, Sept. 1976 [doi>10.1145/360336.360345]
• 23: Sylvia Dieckmann , Urs Hölzle, A Study of the Allocation Behavior of the SPECjvm98 Java Benchmark, Proceedings of the 13th European Conference on Object-Oriented Programming, p.92-115, June 14-18, 1999
• 24: Edsger W. Dijkstra , Leslie Lamport , A. J. Martin , C. S. Scholten , E. F. M. Steffens, On-the-fly garbage collection: an exercise in cooperation, Communications of the ACM, v.21 n.11, p.966-975, Nov. 1978 [doi>10.1145/359642.359655]
• 25: Amer Diwan , David Tarditi , Eliot Moss, Memory subsystem performance of programs using copying garbage collection, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-14, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.174710]
• 26: Lieven Eeckhout , Andy Georges , Koen De Bosschere, How java programs interact with virtual machines at the microarchitectural level, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 27: Robert Fitzgerald , David Tarditi, The case for profile-directed selection of garbage collectors, Proceedings of the 2nd international symposium on Memory management, p.111-120, October 15-16, 2000, Minneapolis, Minnesota, United States
• 28: Michael W. Hicks , Jonathan T. Moore , Scott M. Nettles, The measured cost of copying garbage collection mechanisms, Proceedings of the second ACM SIGPLAN international conference on Functional programming, p.292-305, June 09-11, 1997, Amsterdam, The Netherlands
• 29: 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.
• 30: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 31: Norman P. Jouppi, Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers, Proceedings of the 17th annual international symposium on Computer Architecture, p.364-373, May 28-31, 1990, Seattle, Washington, United States
• 32: Jin-Soo Kim , Yarsun Hsu, Memory system behavior of Java programs: methodology and analysis, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.264-274, June 18-21, 2000, Santa Clara, California, United States
• 33: D. Lea. A memory allocator. http://gee.cs.oswego.edu/dl/html/malloc.html, 1997.
• 34: Yossi Levanoni , Erez Petrank, An on-the-fly reference counting garbage collector for Java, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.367-380, October 14-18, 2001, Tampa Bay, FL, USA
• 35: Henry Lieberman , Carl Hewitt, A real-time garbage collector based on the lifetimes of objects, Communications of the ACM, v.26 n.6, p.419-429, June 1983 [doi>10.1145/358141.358147]
• 36: M. Pettersson. Linux Intel/x86 performance counters, 2003. http://user.it.uu.se/ mikpe/linux/perfctr/.
• 37: Yefim Shuf , Mauricio J. Serrano , Manish Gupta , Jaswinder Pal Singh, Characterizing the memory behavior of Java workloads: a structured view and opportunities for optimizations, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.194-205, June 2001, Cambridge, Massachusetts, United States
• 38: Standard Performance Evaluation Corporation. SPECjvm98 Documentation, release 1.03 edition, March 1999.
• 39: Standard Performance Evaluation Corporation. SPECjbb2000 (Java Business Benchmark) Documentation, release 1.01 edition, 2001.
• 40: Darko Stefanović , Matthew Hertz , Stephen M. Blackburn , Kathryn S. McKinley , J. Eliot B. Moss, Older-first garbage collection in practice: evaluation in a Java Virtual Machine, Proceedings of the 2002 workshop on Memory system performance, p.25-36, June 16-16, 2002, Berlin, Germany
• 41: David Tarditi , Amer Diwan, Measuring the cost of storage management, Lisp and Symbolic Computation, v.9 n.4, p.323-342, Dec. 1996 [doi>10.1007/BF01806316]
• 42: David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.157-167, April 1984
• 43: Benjamin Zorn, The measured cost of conservative garbage collection, Software—Practice & Experience, v.23 n.7, p.733-756, July 1993 [doi>10.1002/spe.4380230704]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Memory management (garbage collection)

General Terms:
Algorithms, Design, Performance

Keywords:
generational, java, mark-sweep, reference counting, semi-space