Connectivity-based garbage collection

ABSTRACT

We introduce a new family of connectivity-based garbage collectors (Cbgc) that are based on potential object-connectivity properties. The key feature of these collectors is that the placement of objects into partitions is determined by performing one of several forms of connectivity analyses on the program. This enables partial garbage collections, as in generational collectors, but without the need for any write barrier.The contributions of this paper are 1) a novel family of garbage collection algorithms based on object connectivity; 2) a detailed description of an instance of this family; and 3) an empirical evaluation of Cbgc using simulations. Simulations help explore a broad range of possibilities for Cbgc, ranging from simplistic ones that determine connectivity based on type information to oracular ones that use run-time information to determine connectivity. Our experiments with the oracular Cbgc configurations give an indication of the potential for Cbgc and also identify weaknesses in the realistic configurations. We found that even the simplistic implementations beat state-of-the-art generational collectors with respect to some metrics (pause times and memory footprint).

REFERENCES

• 1: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 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: Lars Ole Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, University of Copenhagen, 1994. DIKU report 94/19.
• 4: 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]
• 5: 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
• 6: Henry G. Baker, Jr., List processing in real time on a serial computer, Communications of the ACM, v.21 n.4, p.280-294, April 1978 [doi>10.1145/359460.359470]
• 7: 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
• 8: 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
• 9: Richard Brooksby and Nicholas Barnes. The memory pool system. Unpublished paper, 2002.
• 10: Brendon Cahoon. Java-Olden benchmarks. http://www-ali.cs.umass.edu/~cahoon/olden.
• 11: 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
• 12: 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]
• 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: 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
• 15: 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]
• 16: Amer Diwan , Kathryn S. McKinley , J. Eliot B. Moss, Using types to analyze and optimize object-oriented programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.1, p.30-72, Jan. 2001 [doi>10.1145/383721.383732]
• 17: 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
• 18: 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
• 19: Rakesh Ghiya , Laurie J. Hendren, Connection analysis: a practical interprocedural heap analysis for C, International Journal of Parallel Programming, v.24 n.6, p.547-578, Dec. 1996
• 20: 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]
• 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, Harold N. Gabow, and Amer Diwan. Choosing a set of partitions to collect in a connectivity-based garbage collector. Technical Report CU-CS-958-03, University of Colorado at Boulder, 2003.
• 24: Martin Hirzel , Johannes Henkel , Amer Diwan , Michael Hind, Understanding the connectivity of heap objects, Proceedings of the 3rd international symposium on Memory management, June 20-21, 2002, Berlin, Germany
• 25: 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
• 26: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 27: Chris Lattner , Vikram Adve, Automatic pool allocation for disjoint data structures, Proceedings of the 2002 workshop on Memory system performance, p.13-24, June 16-16, 2002, Berlin, Germany
• 28: Ondřej Lhoták and Laurie Hendren. Scaling Java points-to analysis using SPARK. In Compiler Construction (CC), 2003.
• 29: J. Eliot B. Moss. Regions determined by kind and generation. Unpublished note, 1999.
• 30: Young Gil Park , Benjamin Goldberg, Escape analysis on lists, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.116-127, June 15-19, 1992, San Francisco, California, United States
• 31: Feng Qian , Laurie Hendren, An adaptive, region-based allocator for java, Proceedings of the 3rd international symposium on Memory management, June 20-21, 2002, Berlin, Germany
• 32: Atanas Rountev , Ana Milanova , Barbara G. Ryder, Points-to analysis for Java using annotated constraints, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.43-55, October 14-18, 2001, Tampa Bay, FL, USA
• 33: 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
• 34: 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
• 35: Yefim Shuf , Manish Gupta , Hubertus Franke , Andrew Appel , Jaswinder Pal Singh, Creating and preserving locality of java applications at allocation and garbage collection times, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 36: Standard Performance Evaluation Corporation (SPEC). SPECjvm98 benchmarks. http://www.specbench.org/osg/jvm98.
• 37: Bjarne Steensgaard, Points-to analysis in almost linear time, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.32-41, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237727]
• 38: 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
• 39: 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
• 40: 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
• 41: Darko Stefanović , Kathryn S. McKinley , J. Eliot B. Moss, On models for object lifetime distributions, Proceedings of the 2nd international symposium on Memory management, p.137-142, October 15-16, 2000, Minneapolis, Minnesota, United States
• 42: 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]
• 43: Mads Tofte , Jean-Pierre Talpin, Region-based memory management, Information and Computation, v.132 n.2, p.109-176, Feb. 1, 1997 [doi>10.1006/inco.1996.2613]
• 44: 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
• 45: John Whaley , Monica S. Lam, An Efficient Inclusion-Based Points-To Analysis for Strictly-Typed Languages, Proceedings of the 9th International Symposium on Static Analysis, p.180-195, September 17-20, 2002
• 46: Paul R. Wilson. Uniprocessor garbage collection techniques. Accepted for publication in ACM Computing Surveys.
• 47: 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
• 48: 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)

General Terms:
Experimentation, Languages, Measurement, Performance

Keywords:
connectivity based garbage collection