Modeling, analysis and throughput optimization of a generational garbage collector

ABSTRACT

One of the garbage collectors in Sun's HotSpot "Java" Virtual Machine is known as the generational throughput collector, which was designed to have a large throughput (fraction of time spent on application's work rather than on garbage collection). This paper derives an analytical expression for the throughput of this collector in terms of the following key parameters: the sizes of the Young and Old memory spaces and the value of the tenuring threshold. Based on the derived throughput model, a practical algorithm ThruMax is proposed for tuning the collector's parameters so as to formally maximize its throughput. This algorithm was implemented in a custom Java Virtual Machine (JVM) based on the HotSpot sources currently shipped in JDK" 6, and its performance was evaluated on multiple benchmark workloads. A consistent improvement in throughput was demonstrated when the ThruMax algorithm was enabled in this JVM. More importantly, the ThruMax algorithm was shown to actually converge the collector's parameters to the optimal values that resulted in the highest benchmark throughput.

REFERENCES

• 1: "Tuning Garbage Collection with the 5.0 Java Virtual Machine," http://java.sun.com/docs/hotspot/gc5.0/gc_tuning_5.html.
• 2: David A. Barrett , Benjamin G. Zorn, Using lifetime predictors to improve memory allocation performance, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.187-196, June 21-25, 1993, Albuquerque, New Mexico, United States
• 3: David A. Barrett , Benjamin G. Zorn, Garbage collection using a dynamic threatening boundary, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.301-314, June 18-21, 1995, La Jolla, California, United States
• 4: 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
• 5: Stephen M. Blackburn , Matthew Hertz , Kathryn S. Mckinley , J. Eliot B. Moss , Ting Yang, Profile-based pretenuring, ACM Transactions on Programming Languages and Systems (TOPLAS), v.29 n.1, p.2-es, January 2007 [doi>10.1145/1180475.1180477]
• 6: Alan Demers , Mark Weiser , Barry Hayes , Hans Boehm , Daniel Bobrow , Scott Shenker, Combining generational and conservative garbage collection: framework and implementations, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.261-269, December 1989, San Francisco, California, United States [doi>10.1145/96709.96735]
• 7: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 8: Timothy L. Harris, Dynamic adaptive pre-tenuring, Proceedings of the 2nd international symposium on Memory management, p.127-136, October 15-16, 2000, Minneapolis, Minnesota, United States
• 9: Jeremy Singer , Gavin Brown , Mikel Luján , Ian Watson, Towards intelligent analysis techniques for object pretenuring, Proceedings of the 5th international symposium on Principles and practice of programming in Java, September 05-07, 2007, Lisboa, Portugal [doi>10.1145/1294325.1294353]
• 10: David Ungar , Frank Jackson, An adaptive tenuring policy for generation scavengers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.14 n.1, p.1-27, Jan. 1992 [doi>10.1145/111186.116734]
• 11: Ting Yang , Emery D. Berger , Scott F. Kaplan , J. Eliot B. Moss, CRAMM: virtual memory support for garbage-collected applications, Proceedings of the 7th symposium on Operating systems design and implementation, November 06-08, 2006, Seattle, Washington

INDEX TERMS

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

General Terms:
Algorithms, Performance, Theory

Keywords:
garbage collection, parameter optimization, tenuring threshold, throughput model