Exploiting prolific types for memory management and optimizations

ABSTRACT

In this paper, we introduce the notion of prolific and non-prolific types, based on the number of instantiated objects of those types. We demonstrate that distinguishing between these types enables a new class of techniques for memory management and data locality, and facilitates the deployment of known techniques. Specifically, we first present a new type-based approach to garbage collection that has similar attributes but lower cost than generational collection. Then we describe the short type pointer technique for reducing memory requirements of objects (data) used by the program. We also discuss techniques to facilitate the recycling of prolific objects and to simplify object co-allocation decisions.We evaluate the first two techniques on a standard set of Java benchmarks (SPECjvm98 and SPECjbb2000). An implementation of the type-based collector in the Jalapeño VM shows improved pause times, elimination of unnecessary write barriers, and reduction in garbage collection time (compared to the analogous generational collector) by up to 15%. A study to evaluate the benefits of the short-type pointer technique shows a potential reduction in the heap space requirements of programs by up to 16%.

REFERENCES

• 1: Ole Agesen , Alex Garthwaite, Efficient object sampling via weak references, Proceedings of the 2nd international symposium on Memory management, p.121-126, October 15-16, 2000, Minneapolis, Minnesota, 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: A. Appel. A better analytical model for the strong generational hypothesis, November 1997.
• 4: 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
• 5: David F. Bacon , Peter F. Sweeney, Fast static analysis of C++ virtual function calls, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.324-341, October 06-10, 1996, San Jose, California, United States
• 6: Henry G. Baker, Infant mortality and generational garbage collection, ACM SIGPLAN Notices, v.28 n.4, p.55-57, April 1993 [doi>10.1145/152739.152747]
• 7: David A. Barrett , Benjamin G. Zorn, Using lifetime predictors to improve memory allocation performance, ACM SIGPLAN Notices, v.28 n.6, p.187-196, June 1993
• 8: S. J. Baylor , M. Devarakonda , S. J. Fink , E. Gluzberg , M. Kalantar , P. Muttineni , E. Barsness , R. Arora , R. Dimpsey , S. J. Munroe, Java server benchmarks, IBM Systems Journal, v.39 n.1, p.57-81, January 2000
• 9: Stephen M. Blackburn , John Cavazos , Sharad Singhai , Asjad Khan , Kathryn S. McKinley , J. Eliot B. Moss , Sara Smolensky, Profile-driven pretenuring for Java (poster session), Addendum to the 2000 proceedings of the conference on Object-oriented programming, systems, languages, and applications (Addendum), p.129-130, January 2000, Minneapolis, Minnesota, United States [doi>10.1145/367845.368029]
• 10: J. Bonwick. The slab allocator: An object-caching kernel memory allocator. In USENIX Summer 1994 Technical Conference, pages 87-98, 1994.
• 11: R. Brown and L. Hendren. Automatic recycling of Java objects. Technical Report, McGill University, 2000.
• 12: Patrick J. Caudill , Allen Wirfs-Brock, A third generation Smalltalk-80 implementation, Conference proceedings on Object-oriented programming systems, languages and applications, p.119-130, September 29-October 02, 1986, Portland, Oregon, United States
• 13: Trishul M. Chilimbi , Mark D. Hill , James R. Larus, Cache-conscious structure layout, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.1-12, May 01-04, 1999, Atlanta, Georgia, United States
• 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: Keith D. Cooper , Nathaniel McIntosh, Enhanced code compression for embedded RISC processors, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.139-149, May 01-04, 1999, Atlanta, Georgia, United States
• 16: Jeffrey Dean , David Grove , Craig Chambers, Optimization of Object-Oriented Programs Using Static Class Hierarchy Analysis, Proceedings of the 9th European Conference on Object-Oriented Programming, p.77-101, August 07-11, 1995
• 17: David Detlefs , Ole Agesen, Inlining of Virtual Methods, Proceedings of the 13th European Conference on Object-Oriented Programming, p.258-278, June 14-18, 1999
• 18: L. Peter Deutsch , Daniel G. Bobrow, An efficient, incremental, automatic garbage collector, Communications of the ACM, v.19 n.9, p.522-526, Sept. 1976 [doi>10.1145/360336.360345]
• 19: Julian Dolby, Automatic inline allocation of objects, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.7-17, June 16-18, 1997, Las Vegas, Nevada, United States
• 20: 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
• 21: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 22: 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
• 23: Michael Hicks , Luke Hornof , Jonathan T. Moore , Scott M. Nettles, A study of large object spaces, Proceedings of the 1st international symposium on Memory management, p.138-145, October 17-19, 1998, Vancouver, British Columbia, Canada
• 24: U. Hoelzle. A fast write barrier for generational garbage collectors. In Proc. of OOPSLA'93 Workshop on Garbage Collection, 1993.
• 25: Antony L. Hosking , J. Eliot B. Moss , Darko Stefanovic, A comparative performance evaluation of write barrier implementation, conference proceedings on Object-oriented programming systems, languages, and applications, p.92-109, October 18-22, 1992, Vancouver, British Columbia, Canada
• 26: The Java Hotspot performance engine architecture. http://java.sun.com/products/hotspot/ whitepaper.html.
• 27: Richard L. Hudson , J. E Moss , Amer Diwan , Christopher F. Weight, A Language-Independent Garbage Collector Toolkit, University of Massachusetts, Amherst, MA, 1991
• 28: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 29: 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]
• 30: Amit Rao , Santosh Pande, Storage assignment optimizations to generate compact and efficient code on embedded DSPs, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.128-138, May 01-04, 1999, Atlanta, Georgia, United States
• 31: 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
• 32: Y. Shuf, M. Gupta, R. Bordawekar, and J. P. Singh. Distinguishing between prolific and non-prolific types for efficient memory management. Technical report, IBM T.J. Watson Research Center, Yorktown Heights, NY, 2001.
• 33: Y. Shuf, M. Gupta, R. Bordawekar, and J. P. Singh. A hybrid memory management scheme using prolific types and object ages. Technical report, IBM T.J. Watson Research Center, Yorktown Heights, NY, 2001.
• 34: Y. Shuf, M. Gupta, H. Franke, and J. P. Singh. Creating and preserving locality of Java applications at allocation and garbage collection times. Technical report, IBM T.J. Watson Research Center, Yorktown Heights, NY, 2001.
• 35: 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
• 36: Vugranam C. Sreedhar , Michael Burke , Jong-Deok Choi, A framework for interprocedural optimization in the presence of dynamic class loading, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.196-207, June 18-21, 2000, Vancouver, British Columbia, Canada
• 37: Standard Performance Evaluation Council. SPEC JVM98 Benchmarks, 1998. http://www.spec.org/osg/jvm98/.
• 38: Standard Performance Evaluation Council. SPEC JBB2000 Benchmark, 2000. http://www.spec.org/osg/jbb2000/.
• 39: Darko Stefanovic , J. Eliot Moss, Properties of age-based automatic memory reclamation algorithms, 1999
• 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: D. Tarditi and A. Diwan. The full cost of a generational copying garbage collection implementation. In Proc. of the OOPSLA93 Workshop on Memory Management and Garbage Collection, October 1993.
• 43: Transaction Processing Performance Council. TPC-C Benchmark, 2000. http://www.tpc.org/cspec.html .
• 44: R. Tremaine, P. Franaszek, J. Robinson, C. Schulz, T. Smith, M. Wazlowski, and P. Bland. IBM Memory Expansion Technology (MXT). IBM Journal of Research Development, 45(2), 2001.
• 45: David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, ACM SIGPLAN Notices, v.19 n.5, p.157-167, May 1984
• 46: 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]
• 47: A. R. Wallace. On the tendency of varieties to depart indefinitely from the original type. In Letters to the Royal Society, Feb. 1858.
• 48: P. Wilson. Uniprocessor garbage collection techniques. Technical report, University of Texas at Austin, 1994.
• 49: 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
• 50: Benjamin Goth Zorn, Comparative performance evaluation of garbage collection algorithms, 1989