Understanding the connectivity of heap objects

ABSTRACT

Modern garbage collectors partition the set of heap objects to achieve the best performance. For example, generational garbage collectors partition objects by age and focus their efforts on the youngest objects. Partitioning by age works well for many programs because younger objects usually have short lifetimes and thus garbage collection of young objects is often able to free up many objects. However, generational garbage collectors are typically much less efficient for longer-lived objects, and thus prior work has proposed many enhancements to generational collection.Our work explores whether the connectivity of objects can yield useful partitions or improve existing partitioning schemes. We look at both direct (e.g., object A points to object B) and transitive (e.g., object A is reachable from object B) connectivity. Our results indicate that connectivity correlates strongly with object lifetimes and deathtimes and is therefore likely to be useful for partitioning objects.

REFERENCES

• 1: 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
• 2: 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
• 3: 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]
• 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: H. Boehm, A. Demers, and M. Weiser. A garbage collector for C and C++. http://www.hpl.hp.com/personal/Hans_Boehm/gc/
• 6: Michael G. Burke , Jong-Deok Choi , Stephen Fink , David Grove , Michael Hind , Vivek Sarkar , Mauricio J. Serrano , V. C. Sreedhar , Harini Srinivasan , John Whaley, The Jalapeño dynamic optimizing compiler for Java, Proceedings of the ACM 1999 conference on Java Grande, p.129-141, June 12-14, 1999, San Francisco, California, United States [doi>10.1145/304065.304113]
• 7: B. Cahoon. Java-Olden benchmarks. http://www-ali.cs.umass.edu/~cahoon/olden
• 8: Dante J. Cannarozzi , Michael P. Plezbert , Ron K. Cytron, Contaminated garbage collection, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.264-273, June 18-21, 2000, Vancouver, British Columbia, Canada
• 9: 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]
• 10: 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
• 11: Trishul M. Chilimbi , James R. Larus, Using generational garbage collection to implement cache-conscious data placement, Proceedings of the 1st international symposium on Memory management, p.37-48, October 17-19, 1998, Vancouver, British Columbia, Canada
• 12: Jong-Deok Choi , Manish Gupta , Mauricio Serrano , Vugranam C. Sreedhar , Sam Midkiff, Escape analysis for Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.1-19, November 01-05, 1999, Denver, Colorado, United States
• 13: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 14: 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
• 15: Julian Dolby , Andrew Chien, An automatic object inlining optimization and its evaluation, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.345-357, June 18-21, 2000, Vancouver, British Columbia, Canada
• 16: 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
• 17: David Gay , Alex Aiken, Memory management with explicit regions, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.313-323, June 17-19, 1998, Montreal, Quebec, Canada
• 18: David Gay , Bjarne Steensgaard, Fast Escape Analysis and Stack Allocation for Object-Based Programs, Proceedings of the 9th International Conference on Compiler Construction, p.82-93, March 25-April 02, 2000
• 19: Timothy Harris, Early storage reclamation in a tracing garbage collector, ACM SIGPLAN Notices, v.34 n.4, p.46-53, April 1999 [doi>10.1145/312009.312035]
• 20: 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
• 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: 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
• 23: Martin Hirzel , Amer Diwan , Antony L. Hosking, On the Usefulness of Liveness for Garbage Collection and Leak Detection, Proceedings of the 15th European Conference on Object-Oriented Programming, p.181-206, June 18-22, 2001
• 24: Richard L. Hudson , J. Eliot B. Moss, Incremental Collection of Mature Objects, Proceedings of the International Workshop on Memory Management, p.388-403, September 17-19, 1992
• 25: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 26: 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]
• 27: David A. Moon, Garbage collection in a large LISP system, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.235-246, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802040]
• 28: Erik Ruf, Effective synchronization removal for Java, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.208-218, June 18-21, 2000, Vancouver, British Columbia, Canada
• 29: Matthew L. Seidl , Benjamin G. Zorn, Segregating heap objects by reference behavior and lifetime, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.12-23, October 02-07, 1998, San Jose, California, United States
• 30: Yefim Shuf , Manish Gupta , Rajesh Bordawekar , Jaswinder Pal Singh, Exploiting prolific types for memory management and optimizations, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.295-306, January 16-18, 2002, Portland, Oregon
• 31: 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
• 32: Standard Performance Evaluation Corporation (SPEC). SPECjvm98 benchmarks. http://www.specbench.org/osg/jvm98
• 33: 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
• 34: 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
• 35: Darko Stefanovic , J. Eliot B. Moss, Characterization of object behaviour in Standard ML of New Jersey, Proceedings of the 1994 ACM conference on LISP and functional programming, p.43-54, June 27-29, 1994, Orlando, Florida, United States
• 36: Alexandru Salcianu , Martin Rinard, Pointer and escape analysis for multithreaded programs, Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming, p.12-23, June 2001, Snowbird, Utah, United States
• 37: 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]
• 38: Mads Tofte, A brief introduction to regions, Proceedings of the 1st international symposium on Memory management, p.186-195, October 17-19, 1998, Vancouver, British Columbia, Canada
• 39: 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
• 40: 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]
• 41: Frédéric Vivien , Martin Rinard, Incrementalized pointer and escape analysis, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.35-46, June 2001, Snowbird, Utah, United States
• 42: P. Wilson. Uniprocessor garbage collection techniques. Accepted for publication in ACM Computing Surveys
• 43: Paul R. Wilson , Michael S. Lam , Thomas G. Moher, Effective “static-graph” reorganization to improve locality in garbage-collected systems, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.177-191, June 24-28, 1991, Toronto, Ontario, Canada

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors

General Terms:
Experimentation, Languages, Measurement, Performance

Keywords:
connectivity based garbage collection, object lifetimes