Free-Me: a static analysis for automatic individual object reclamation

ABSTRACT

Garbage collection has proven benefits, including fewer memory related errors and reduced programmer effort. Garbage collection, however, trades space for time. It reclaims memory only when it is invoked: invoking it more frequently reclaims memory quickly, but incurs a significant cost; invoking it less frequently fills memory with dead objects. In contrast, explicit memory management provides prompt low cost reclamation, but at the expense of programmer effort.This work comes closer to the best of both worlds by adding novel compiler and runtime support for compiler inserted frees to a garbage-collected system. The compiler's free-me analysis identifies when objects become unreachable and inserts calls to free. It combines a lightweight pointer analysis with liveness information that detects when short-lived objects die. Our approach differs from stack and region allocation in two crucial ways. First, it frees objects incrementally exactly when they become unreachable, instead of based on program scope. Second, our system does not require allocation-site lifetime homogeneity, and thus frees objects on some paths and not on others. It also handles common patterns: it can free objects in loops and objects created by factory methods.We evaluate free() variations for free-list and bump-pointer allocators. Explicit freeing improves performance by promptly reclaiming objects and reducing collection load. Compared to marksweep alone, free-me cuts total time by 22% on average, collector time by 50% to 70%, and allows programs to run in 17% less memory. This combination retains the software engineering benefits of garbage collection while increasing space efficiency and improving performance, and thus is especially appealing for real-time and space constrained systems.

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: 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: L. O. Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, DIKU, University of Copenhagen, May 1994.
• 4: David F. Bacon , Perry Cheng , David Grove , Martin T. Vechev, Syncopation: generational real-time garbage collection in the metronome, Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 15-17, 2005, Chicago, Illinois, USA
• 5: Jeffrey M. Barth, Shifting garbage collection overhead to compile time, Communications of the ACM, v.20 n.7, p.513-518, July 1977 [doi>10.1145/359636.359713]
• 6: Emery D. Berger , Benjamin G. Zorn , Kathryn S. McKinley, Reconsidering custom memory allocation, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 7: 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
• 8: 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
• 9: S. M. Blackburn, R. Garner, C. Hoffmann, A. M. Khan, K. S. McKinley, R. Bentzur, A. Diwan, D. Feinberg, S. Z. Guyer, A. Hosking, M. Jump, J. E. B. Moss, D. Stefanović, T. VanDrunen, D. von Dincklage, and B. Wiedermann. The DaCapo Benchmarks: Java benchmarking development and analysis. Technical Report TRCS-06-01, Deptartment of Computer Science, Austrailian National University, Mar. 2006. http://ali-www.cs.umass.edu/DaCapo/-Benchmarks.
• 10: Bruno Blanchet, Escape analysis for Java^TM: Theory and practice, ACM Transactions on Programming Languages and Systems (TOPLAS), v.25 n.6, p.713-775, November 2003 [doi>10.1145/945885.945886]
• 11: Sigmund Cherem , Radu Rugina, Region analysis and transformation for Java programs, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029884]
• 12: Wei-Ngan Chin , Florin Craciun , Shengchao Qin , Martin Rinard, Region inference for an object-oriented language, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 13: Jong-Deok Choi , Manish Gupta , Mauricio J. Serrano , Vugranam C. Sreedhar , Samuel P. Midkiff, Stack allocation and synchronization optimizations for Java using escape analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.25 n.6, p.876-910, November 2003 [doi>10.1145/945885.945892]
• 14: C. Click. Stack allocation, Jan. 2005. Personal Communication.
• 15: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 16: Lieven Eeckhout , Andy Georges , Koen De Bosschere, How java programs interact with virtual machines at the microarchitectural level, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 17: Yi Feng , Emery D. Berger, A locality-improving dynamic memory allocator, Proceedings of the 2005 workshop on Memory system performance, June 12-12, 2005, Chicago, Illinois [doi>10.1145/1111583.1111594]
• 18: Robert Fitzgerald , Todd B. Knoblock , Erik Ruf , Bjarne Steensgaard , David Tarditi, Marmot: an optimizing compiler for Java, Software—Practice & Experience, v.30 n.3, p.199-232, Mar.1.2000 [doi>10.1002/(SICI)1097-024X(200003)30:3<199::AID-SPE296>3.0.CO;2-2]
• 19: David Gay , Alex Aiken, Language support for regions, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.70-80, June 2001, Snowbird, Utah, United States
• 20: 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
• 21: Ovidiu Gheorghioiu , Alexandru Salcianu , Martin Rinard, Interprocedural compatibility analysis for static object preallocation, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.273-284, January 15-17, 2003, New Orleans, Louisiana, USA
• 22: Niels Hallenberg , Martin Elsman , Mads Tofte, Combining region inference and garbage collection, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 23: Matthew Hertz , Emery D. Berger, Quantifying the performance of garbage collection vs. explicit memory management, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 24: Michael Hicks , Greg Morrisett , Dan Grossman , Trevor Jim, Experience with safe manual memory-management in cyclone, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029883]
• 25: Martin Hirzel , Amer Diwan , Johannes Henkel, On the usefulness of type and liveness accuracy for garbage collection and leak detection, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.6, p.593-624, November 2002 [doi>10.1145/586088.586089]
• 26: H. Inoue, D. Stefanović, and S. Forrest. Object lifetime prediction in Java. Technical Report TR-CS-2003-28, University of New Mexico, May 2003.
• 27: Jikes RVM. IBM, 2005. http://jikesrvm.sourceforge.net.
• 28: Simon B. Jones , Daniel Le Métayer, Compile-time garbage collection by sharing analysis, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.54-74, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99375]
• 29: D. Lea. A memory allocator. http://gee.cs.oswego.edu/dl/html/malloc.html, 1997.
• 30: Oukseh Lee , Kwangkeun Yi, Experiments on the effectiveness of an automatic insertion of memory reuses into ML-like programs, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029885]
• 31: Darko Marinov , Robert O'Callahan, Object equality profiling, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 32: 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
• 33: Ran Shaham , Elliot K. Kolodner , Mooly Sagiv, Heap profiling for space-efficient Java, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.104-113, June 2001, Snowbird, Utah, United States
• 34: R. Shaham, E. Yahav, E. K. Kolodner, and M. Sagiv. Establishing local temporal heap safety properties with application to compiletime memory management. In Static Analysis Symposium, pages 483--503, San Diego, CA, June 2003.
• 35: Standard Performance Evaluation Corporation. SPECjvm98 Documentation, release 1.03 edition, March 1999.
• 36: Standard Performance Evaluation Corporation. SPECjbb2000 (Java Business Benchmark) Documentation, release 1.01 edition, 2001.
• 37: 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]
• 38: 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
• 39: John Whaley , Martin Rinard, Compositional pointer and escape analysis for Java programs, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.187-206, November 01-05, 1999, Denver, Colorado, United States

INDEX TERMS

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

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

General Terms:
Algorithms, Experimentation, Languages, Performance

Keywords:
adaptive, compiler-assisted, copying, generational, liveness, locality, mark-sweep, pointer analysis