A study of Java object demographics

ABSTRACT

Researchers have long strived to exploit program behaviour in order to improve garbage collection efficiency. For example, by using a simple heuristic, generational GC manages short-lived objects well, although longer-lived objects will still be promoted to an older generation and may be processed repeatedly thereafter. In this paper, we provide a detailed study of Java object lifetimes which reveals a richer landscape than the generational view offers.

Allocation site has been claimed to be a good predictor for object lifetime, but we show that object lifetime can be categorised more precisely than 'short-lived/long-lived/immortal'. We show that (i) sites allocate objects with lifetimes in only a small number of narrow ranges, and (ii) sites cluster strongly with respect to the lifetime distributions of the objects they allocate. Furthermore, (iii) these clusterings are robust against the size of the input given to the program and (iv) are likely to allocate objects that are live only in particular phases of the program's execution. Finally, we show that, in contrast to previous studies, (v) allocation site alone is not always sufficient as a predictor of object lifetime distribution but one further level of stack context suffices.

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: 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]
• 3: D.A. Barrett and B. Zorn. Garbage collection using a dynamic threatening boundary. Computer Science Technical Report CU-CS-659-93, University of Colorado, July 1993.
• 4: 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
• 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: Stephen M. Blackburn , Perry Cheng , Kathryn S. McKinley, Myths and realities: the performance impact of garbage collection, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 7: Stephen M. Blackburn , Perry Cheng , Kathryn S. McKinley, Oil and Water? High Performance Garbage Collection in Java with MMTk, Proceedings of the 26th International Conference on Software Engineering, p.137-146, May 23-28, 2004
• 8: 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]
• 9: 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
• 10: 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
• 11: Michael D. Bond , Kathryn S. McKinley, Probabilistic calling context, Proceedings of the 22nd annual ACM SIGPLAN conference on Object oriented programming systems and applications, October 21-25, 2007, Montreal, Quebec, Canada
• 12: Chakravarti, Laha, and Roy. Handbook of Methods of Applied Statistics, volume I. John Wiley and Sons, 1967.
• 13: Perry Cheng , Robert Harper , Peter Lee, Generational stack collection and profile-driven pretenuring, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.162-173, June 17-19, 1998, Montreal, Quebec, Canada
• 14: 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]
• 15: 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
• 16: R. Fitzgerald and D. Tarditi. The case for profile-directed selection of garbage collectors. In {22}.
• 17: Joseph (Yossi) Gil , Itay Maman, Micro patterns in Java code, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 18: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 19: Lars T. Hansen , William D. Clinger, An experimental study of renewal-older-first garbage collection, Proceedings of the seventh ACM SIGPLAN international conference on Functional programming, p.247-258, October 04-06, 2002, Pittsburgh, PA, USA
• 20: T. Harris. Dynamic adaptive pre-tenuring. In {22}.
• 21: Barry Hayes, Using key object opportunism to collect old objects, Conference proceedings on Object-oriented programming systems, languages, and applications, p.33-46, October 06-11, 1991, Phoenix, Arizona, United States
• 22: T. Hosking, editor. ISMM 2000 Proceedings of the Second International Symposium on Memory Management, Minneapolis, MN, October 2000. ACM Press.
• 23: L. Hubert and P. Arabie. Comparing clusterings. Journal of Classification, 2:193--218, 1985.
• 24: A. K. Jain , M. N. Murty , P. J. Flynn, Data clustering: a review, ACM Computing Surveys (CSUR), v.31 n.3, p.264-323, Sept. 1999 [doi>10.1145/331499.331504]
• 25: Mark Stuart Johnstone , Paul R. Wilson, Non-compacting memory allocation and real-time garbage collection, The University of Texas at Austin, 1997
• 26: R.E. Jones and C. Ryder. Garbage collection should be lifetime aware. In Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems (ICOOOLPS?2006), Nantes, France, July 2006.
• 27: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 28: Sebastien Marion , Richard Jones , Chris Ryder, Decrypting the Java gene pool, Proceedings of the 6th international symposium on Memory management, October 21-22, 2007, Montreal, Quebec, Canada [doi>10.1145/1296907.1296918]
• 29: 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]
• 30: Marina Meilă, Comparing clusterings---an information based distance, Journal of Multivariate Analysis, v.98 n.5, p.873-895, May, 2007 [doi>10.1016/j.jmva.2006.11.013]
• 31: OOPSLA?99 ACM Conference on Object-Oriented Systems, Languages and Applications, Denver, CO, October 1999. ACM Press.
• 32: Tony Printezis, Hot-swapping between a mark&sweep and a mark&compact garbage collector in a generational environment, Proceedings of the 2001 Symposium on Java^TM Virtual Machine Research and Technology Symposium, p.20-20, April 23-24, 2001, Monterey, California
• 33: Tony Printezis , Richard Jones, GCspy: an adaptable heap visualisation framework, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 34: W.M. Rand. Objective criteria for the evaluation of clustering methods. Journal of the American Statistical Association, 66:846--850, 1971.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques

General Terms:
Languages, Measurement, Performance

Keywords:
garbage collection, java, memory management