Microphase: an approach to proactively invoking garbage collection for improved performance

ABSTRACT

To date, the most commonly used criterion for invoking garbage collection (GC) is based on heap usage; that is, garbage collection is invoked when the heap or an area inside the heap is full. This approach can suffer from two performance shortcomings: untimely garbage collection invocations and large volumes of surviving objects. In this work, we explore a new GC triggering approach called MicroPhase that exploits two observations: (i) allocation requests occur in phases and (ii) phase boundaries coincide with times when most objects also die. Thus, proactively invoking garbage collection at these phase boundaries can yield high efficiency. We extended the HotSpot virtual machine from Sun Microsystems to support MicroPhase and conducted experiments using 20 benchmarks. The experimental results indicate that our technique can reduce the GC times in 19 applications. The differences in GC overhead range from an increase of 1% to a decrease of 26% when the heap is set to twice the maximum live-size. As a result, MicroPhase can improve the overall performance of 13 benchmarks. The performance differences range from a degradation of 2.5% to an improvement of 14%.

REFERENCES

• 1: David F. Bacon , Perry Cheng , V. T. Rajan, Controlling fragmentation and space consumption in the metronome, a real-time garbage collector for Java, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
• 2: David F. Bacon , Ravi Konuru , Chet Murthy , Mauricio Serrano, Thin locks: featherweight synchronization for Java, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.258-268, June 17-19, 1998, Montreal, Quebec, Canada
• 3: 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
• 4: Stephen M. Blackburn , Sharad Singhai , Matthew Hertz , Kathryn S. McKinely , J. Eliot B. Moss, Pretenuring for Java, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.342-352, October 14-18, 2001, Tampa Bay, FL, USA
• 5: Stephen M. Blackburn , Robin Garner , Chris Hoffmann , Asjad M. Khang , Kathryn S. McKinley , Rotem Bentzur , Amer Diwan , Daniel Feinberg , Daniel Frampton , Samuel Z. Guyer , Martin Hirzel , Antony Hosking , Maria Jump , Han Lee , J. Eliot B. Moss , B. Moss , Aashish Phansalkar , Darko Stefanović , Thomas VanDrunen , Daniel von Dincklage , Ben Wiedermann, The DaCapo benchmarks: java benchmarking development and analysis, Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
• 6: 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
• 7: Dries Buytaert, Kris Venstermans, Lieven Eeckhout, and Koen De Bosschere. Garbage collection hints. In Proceedings of the First International Conference on High Performance Embedded Architectures and Compilers (HiPEAC 2005), pages 233--248, Barcelona, Spain, 11 2005. Springer Verlag.
• 8: Wen-ke Chen , Sanjay Bhansali , Trishul Chilimbi , Xiaofeng Gao , Weihaw Chuang, Profile-guided proactive garbage collection for locality optimization, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 9: Perry Cheng , Guy E. Blelloch, A parallel, real-time garbage collector, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.125-136, June 2001, Snowbird, Utah, United States
• 10: 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
• 11: Chen Ding , Chengliang Zhang , Xipeng Shen , Mitsunori Ogihara, Gated memory control for memory monitoring, leak detection and garbage collection, Proceedings of the 2005 workshop on Memory system performance, June 12-12, 2005, Chicago, Illinois [doi>10.1145/1111583.1111593]
• 12: Tamar Domani , Gal Goldshtein , Elliot K. Kolodner , Ethan Lewis , Erez Petrank , Dafna Sheinwald, Thread-local heaps for Java, ACM SIGPLAN Notices, v.38 n.2 supplement, February 2003
• 13: Samuel Z. Guyer , Kathryn S. McKinley , Daniel Frampton, Free-Me: a static analysis for automatic individual object reclamation, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 14: Matthias Hauswirth , Peter F. Sweeney , Amer Diwan , Michael Hind, Vertical profiling: understanding the behavior of object-priented applications, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 24-28, 2004, Vancouver, BC, Canada
• 15: Matthew Hertz , Stephen M Blackburn , J Eliot B Moss , Kathryn S. McKinley , Darko Stefanović, Error-free garbage collection traces: how to cheat and not get caught, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 16: IBM. Jikes Research Virtual Machine. http://jikesrvm.sourceforge.net.
• 17: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 18: Peter Mikhalenko. Real-time Java: An introduction. On-Line Article, Last visited: July 2007. http://www.onjava.com/pub/a/onjava/2006/05/10/real-time-\\java-introductio%n.html.
• 19: Priya Nagpurkar , Chandra Krintz, Visualization and analysis of phased behavior in Java programs, Proceedings of the 3rd international symposium on Principles and practice of programming in Java, June 16-18, 2004, Las Vegas, Nevada
• 20: Priya Nagpurkar , Chandra Krintz , Michael Hind , Peter F. Sweeney , V. T. Rajan, Online Phase Detection Algorithms, Proceedings of the International Symposium on Code Generation and Optimization, p.111-123, March 26-29, 2006 [doi>10.1109/CGO.2006.26]
• 21: Yang Qian, Wei Huang, Witawas Srisa-an, and J. Morris Chang. Allocation Pattern and GC Triggering. Technical Report TR-UNL-CSE-2003-0017, University of Nebraska-Lincoln, Lincoln, Nebraska, U.S.A., October 2003. http://lakota.unl.edu//facdb/TechReportArchive/TR-UNL-CSE-2003-0017.pdf.
• 22: Yang Qian, W. Srisa-an, T. Skotiniotis, and J. M. Chang. A cycle-accurate per-thread timer for Linux operating system. In Proceedings of IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), pages 38--44, Tucson, Arizona, USA, November 2001.
• 23: Sven Gestegard Robertz , Roger Henriksson, Time-triggered garbage collection: robust and adaptive real-time GC scheduling for embedded systems, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
• 24: Ran Shaham , Elliot K. Kolodner , Mooly Sagiv, On effectiveness of GC in Java, Proceedings of the 2nd international symposium on Memory management, p.12-17, October 15-16, 2000, Minneapolis, Minnesota, United States
• 25: Jon Shemitz. Using RDTSC for benchmarking code on Pentium computers, Last visited: July 2007. http://www.midnightbeach.com/jon/pubs/rdtsc.htm.
• 26: Standard Performance Evaluation Corporation. SPECjbb2000. White Paper, Last visited: July 2007. http://www.spec.org/osg/jbb2000/docs/whitepaper.html.
• 27: Standard Performance Evaluation Corporation. SPECjvm98 benchmarks, Last visited: July 2007. http://www.spec.org/osg/jvm98.
• 28: Bjarne Steensgaard, Thread-specific heaps for multi-threaded programs, Proceedings of the 2nd international symposium on Memory management, p.18-24, October 15-16, 2000, Minneapolis, Minnesota, United States
• 29: 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, ACM SIGPLAN Notices, v.38 n.2 supplement, p.25-36, February 2003
• 30: Darko Stefanović , Kathryn S. McKinley , J. Eliot B. Moss, Age-based garbage collection, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.370-381, November 01-05, 1999, Denver, Colorado, United States
• 31: Sun Microsystems. Java technology is everywhere, surpasses 1.5 billion devices worldwide. Press Release, February 2004. http://www.sun.com/smi/Press/sunflash/2004--02/sunflash.20040219.1.html.
• 32: 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
• 33: P. R. Wilson, Opportunistic garbage collection, ACM SIGPLAN Notices, v.23 n.12, p.98-102, Dec. 1988 [doi>10.1145/57669.57679]
• 34: P. R. Wilson , T. G. Moher, Design of the opportunistic garbage collector, ACM SIGPLAN Notices, v.24 n.10, p.23-35, Oct. 1989
• 35: Feng Xian, Witawas Srisa-an, ChengHuan Jia, and Hong Jiang. AS-GC: An efficient generational garbage collector for Java application servers. In Proceedings of the European Conference on Object-Oriented Programming (ECOOP), pages 126--150, Berlin, Germany, July 2007.
• 36: Feng Xian , Witawas Srisa-an , Hong Jiang, Investigating throughput degradation behavior of Java application servers: a view from inside a virtual machine, Proceedings of the 4th international symposium on Principles and practice of programming in Java, August 30-September 01, 2006, Mannheim, Germany [doi>10.1145/1168054.1168061]
• 37: Karen Zee , Martin Rinard, Write barrier removal by static analysis, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Run-time environments

General Terms:
Experimentation, Languages, Performance

Keywords:
execution phase, garbage collection