Dynamic prediction of collection yield for managed runtimes

ABSTRACT

The growth in complexity of modern systems makes it increasingly difficult to extract high-performance. The software stacks for such systems typically consist of multiple layers and include managed runtime environments (MREs). In this paper, we investigate techniques to improve cooperation between these layers and the hardware to increase the efficacy of automatic memory management in MREs.

General-purpose MREs commonly implement parallel and/or concurrent garbage collection and employ compaction to eliminate heap fragmentation. Moreover, most systems trigger collection based on the amount of heap a program uses. Our analysis shows that in many cases this strategy leads to ineffective collections that are unable to reclaim sufficient space to justify the incurred cost. To avoid such collections, we exploit the observation that dead objects tend to cluster together and form large, never-referenced, regions in the address space that correlate well with virtual pages that have not recently been referenced by the application. We leverage this correlation to design a new, simple and light-weight, yield predictor that estimates the amount of reclaimable space in the heap using hardware page reference bits. Our predictor allows MREs to avoid low-yield collections and thereby improve resource management.

We integrate this predictor into three state-of-the-art parallel compactors, implemented in the HotSpot JVM, that represent distinct canonical heap layouts. Our empirical evaluation, based on standard Java benchmarks and open-source applications, indicates that inexpensive and accurate yield prediction can improve performance significantly.

REFERENCES

• 1: Andrew W. Appel , Kai Li, Virtual memory primitives for user programs, ACM SIGPLAN Notices, v.26 n.4, p.96-107, Apr. 1991
• 2: 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
• 3: Víctor Braberman , Federico Fernández , Diego Garbervetsky , Sergio Yovine, Parametric prediction of heap memory requirements, Proceedings of the 7th international symposium on Memory management, June 07-08, 2008, Tucson, AZ, USA [doi>10.1145/1375634.1375655]
• 4: 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
• 5: Cliff Click , Gil Tene , Michael Wolf, The pauseless GC algorithm, Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments, June 11-12, 2005, Chicago, IL, USA [doi>10.1145/1064979.1064988]
• 6: Jacques Cohen , Alexandru Nicolau, Comparison of Compacting Algorithms for Garbage Collection, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.4, p.532-553, Oct. 1983 [doi>10.1145/69575.357226]
• 7: D. Cohn and S. Singh. Predicting lifetimes in dynamically allocated memory. ANIPS'97.
• 8: The DaCapo Benchmark Suite. http://dacapobench.org.
• 9: David Detlefs , Christine Flood , Steve Heller , Tony Printezis, Garbage-first garbage collection, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029879]
• 10: Christine H. Flood , David Detlefs , Nir Shavit , Xiaolan Zhang, Parallel garbage collection for shared memory multiprocessors, Proceedings of the 2001 Symposium on Java^TM Virtual Machine Research and Technology Symposium, p.21-21, April 23-24, 2001, Monterey, California
• 11: Open Source Software in Java. http://java-source.net.
• 12: Chris Grzegorczyk , Sunil Soman , Chandra Krintz , Rich Wolski, Isla Vista Heap Sizing: Using Feedback to Avoid Paging, Proceedings of the International Symposium on Code Generation and Optimization, p.325-340, March 11-14, 2007 [doi>10.1109/CGO.2007.20]
• 13: M. Hertz, Y. Feng, and E. Berger. Page-level cooperative garbage collection. Univ. Massachusetts, Tech. Report, 2004.
• 14: Matthew Hertz , Yi Feng , Emery D. Berger, Garbage collection without paging, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 15: Antony L. Hosking , J. Eliot B. Moss, Protection traps and alternatives for memory management of an object-oriented language, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.106-119, December 05-08, 1993, Asheville, North Carolina, United States
• 16: HotSpot Virtual Machine Garbage Collection. http://java.sun.com/javase/technologies/hotspot/gc.
• 17: H. Inoue, D. Stefanovic, and S. Forrest. Object lifetime prediction in Java. Univ. New Mexico, Tech. Report, 2003.
• 18: R. Jones. Dynamic memory management: Challenges for today and tomorrow. ILC'07.
• 19: R. Jones and C. Ryder. Garbage collection should be lifetime aware. ICOOOLPS'06.
• 20: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 21: Haim Kermany , Erez Petrank, The Compressor: concurrent, incremental, and parallel compaction, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 22: Open Source J2SE. http://openjdk.java.net.
• 23: Yoav Ossia , Ori Ben-Yitzhak , Marc Segal, Mostly concurrent compaction for mark-sweep GC, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029877]
• 24: C. Ruggieri , T. P. Murtagh, Lifetime analysis of dynamically allocated objects, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.285-293, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73585]
• 25: Narendran Sachindran , J. Eliot B. Moss , B. Moss, Mark-copy: fast copying GC with less space overhead, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 26: M.L. Seidl and B. Zorn. Low cost methods for predicting heap object behavior. WFDO'99.
• 27: The SPEC Benchmarks. http://www.spec.org.
• 28: David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, ACM SIGPLAN Notices, v.19 n.5, p.157-167, May 1984
• 29: The VolanoMark Benchmark. http://www.volano.com.
• 30: Michal Wegiel , Chandra Krintz, The mapping collector: virtual memory support for generational, parallel, and concurrent compaction, Proceedings of the 13th international conference on Architectural support for programming languages and operating systems, March 01-05, 2008, Seattle, WA, USA
• 31: P.R. Wilson. Uniprocessor garbage collection techniques. Univ. Texas, Tech. Report, 1994.
• 32: Paul R. Wilson , Mark S. Johnstone , Michael Neely , David Boles, Dynamic Storage Allocation: A Survey and Critical Review, Proceedings of the International Workshop on Memory Management, p.1-116, September 27-29, 1995
• 33: Feng Xian , Witawas Srisa-an , Hong Jiang, Microphase: an approach to proactively invoking garbage collection for improved performance, Proceedings of the 22nd annual ACM SIGPLAN conference on Object-oriented programming systems and applications, October 21-25, 2007, Montreal, Quebec, Canada
• 34: Ting Yang , Matthew Hertz , Emery D. Berger , Scott F. Kaplan , J. Eliot B. Moss, Automatic heap sizing: taking real memory into account, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029881]
• 35: Ting Yang , Emery D. Berger , Scott F. Kaplan , J. Eliot B. Moss , B. Moss, CRAMM: virtual memory support for garbage-collected applications, Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation, p.8-8, November 06-08, 2006, Seattle, WA
• 36: Chengliang Zhang , Kirk Kelsey , Xipeng Shen , Chen Ding , Matthew Hertz , Mitsunori Ogihara, Program-level adaptive memory management, Proceedings of the 5th international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada [doi>10.1145/1133956.1133979]
• 37: 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

INDEX TERMS

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

General Terms:
Languages, Management, Performance

Keywords:
clustering, concurrent, garbage collection, operating system, parallel, reference bits, yield prediction