Automatic heap sizing: taking real memory into account

ABSTRACT

Heap size has a huge impact on the performance of garbage collected applications. A heap that barely meets the application's needs causes excessive GC overhead, while a heap that exceeds physical memory induces paging. Choosing the best heap size <i>a priori</i> is impossible in multiprogrammed environments, where physical memory allocations to processes change constantly. We present an automatic heap-sizing algorithm applicable to different garbage collectors with only modest changes. It relies on an analytical model and on detailed information from the virtual memory manager. The model characterizes the relation between collection algorithm, heap size, and footprint. The virtual memory manager tracks recent reference behavior, reporting the current footprint and allocation to the collector. The collector uses those values as inputs to its model to compute a heap size that maximizes throughput while minimizing paging. We show that our adaptive heap sizing algorithm can substantially reduce running time over fixed-sized heaps.

REFERENCES

• 1: Raphael Alonso , Andrew W. Appel, An advisor for flexible working sets, Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.153-162, April 1990, Univ. of Colorado, Boulder, 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: 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
• 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: O. Babaoglu and D. Ferrari. Two-level replacement decisions in paging stores. IEEE Transactions on Computers, C-32(12):1151--1159, Dec. 1983.
• 6: Jeffrey A. Barnett, Garbage collection versus swapping, ACM SIGOPS Operating Systems Review, v.13 n.3, p.12-17, July 1979 [doi>10.1145/850662.850665]
• 7: BEA WebLogic. Technical white paper---JRockit: Java for the enterprise. http://www.bea.com/content/news_events/white_papers/BEA_JRockit_wp.pdf.
• 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: Hans-Juergen Boehm , Mark Weiser, Garbage collection in an uncooperative environment, Software—Practice & Experience, v.18 n.9, p.807-820, September 1988 [doi>10.1002/spe.4380180902]
• 10: Tim Brecht , Eshrat Arjomandi , Chang Li , Hang Pham, Controlling garbage collection and heap growth to reduce the execution time of Java applications, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.353-366, October 14-18, 2001, Tampa Bay, FL, USA
• 11: Eric Cooper , Scott Nettles , Indira Subramanian, Improving the performance of SML garbage collection using application-specific virtual memory management, Proceedings of the 1992 ACM conference on LISP and functional programming, p.43-52, June 22-24, 1992, San Francisco, California, United States
• 12: M. Hertz, Y. Feng, and E. D. Berger. Page-level cooperative garbage collection. Technical Report TR-04-16, University of Massachusetts, 2004.
• 13: X. Huang, J. E. B. Moss, K. S. Mckinley, S. Blackburn, and D. Burger. Dynamic SimpleScala: Simulating Java Virtual Machines. Technical Report TR-03-03, University of Texas at Austin, Feb. 2003.
• 14: JavaSoft. J2SE 1.5.0 Documentation---Garbage Collector Ergonomics. Available at http://java.sun.com/j2se/1.5.0/docs/guide/vm/gc-ergonomics.html.
• 15: Scott F. Kaplan , Yannis Smaragdakis , Paul R. Wilson, Trace reduction for virtual memory simulations, Proceedings of the 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.47-58, May 01-04, 1999, Atlanta, Georgia, United States
• 16: Scott F. Kaplan , Yannis Smaragdakis , Paul R. Wilson, Flexible reference trace reduction for VM simulations, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.13 n.1, p.1-38, January 2003 [doi>10.1145/778553.778554]
• 17: Jin-Soo Kim , Yarsun Hsu, Memory system behavior of Java programs: methodology and analysis, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.264-274, June 18-21, 2000, Santa Clara, California, United States
• 18: 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]
• 19: Novell. Documentation: NetWare 6---Optimizing Garbage Collection. Available at http://www.novell.com/documentation/index.html.
• 20: Yannis Smaragdakis , Scott Kaplan , Paul Wilson, The EELRU adaptive replacement algorithm, Performance Evaluation, v.53 n.2, p.93-123, July 2003 [doi>10.1016/S0166-5316(02)00226-2]
• 21: P. R. Wilson, S. F. Kaplan, and Y. Smaragdakis. The case for compressed caching in virtual memory systems. In Proceedings of The 1999 USENIX Annual Technical Conference, pages 101--116, Monterey, California, June 1999. USENIX Association.
• 22: T. Yang, E. D. Berger, M. Hertz, S. F. Kaplan, and J. E. B. Moss. Autonomic heap sizing: Taking real memory into account. Technical Report TR-04-14, University of Massachusetts, July 2004.

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance

Keywords:
garbage collection, paging, virtual memory