An evaluation of automatic object inline allocation techniques

ABSTRACT

Object-oriented languages such as Java and Smalltalk provide a uniform object reference model, allowing objects to be conveniently shared. If implemented directly, these uniform reference models can suffer in efficiency due to additional memory dereferences and memory management operations. Automatic inline allocation of child objects within parent objects can reduce overheads of heap-allocated pointer-referenced objects.We present three compiler analyses to identify inlinable fields by tracking accesses to heap objects. These analyses span a range from local data flow to adaptive whole-program, flow-sensitive inter-procedural analysis. We measure their cost and effectiveness on a suite of moderate-sized C++ programs (up to 30,000 lines including libraries). We show that aggressive interprocedural analysis is required to enable object inlining, and our adaptive inter-procedural analysis [23] computes precise information efficiently. Object inlining eliminates typically 40% of object accesses and allocations (improving performance up to 50%). Furthermore,

REFERENCES

• 1: Ole Agesen , Jens Palsberg , Michael I. Schwartzbach, Type Inference of SELF, Proceedings of the 7th European Conference on Object-Oriented Programming, p.247-267, July 26-30, 1993
• 2: Pierre America, Inheritance and subtyping in a parallel object-oriented language, European conference on object-oriented programming on ECOOP '87, p.234-242, October 1987, Paris, France
• 3: Andrew Black , Norman Hutchinson , Eric Jul , Henry Levy, Object structure in the Emerald system, Conference proceedings on Object-oriented programming systems, languages and applications, p.78-86, September 29-October 02, 1986, Portland, Oregon, United States
• 4: Zoran Budimlic and Ken Kennedy. Optimizing java: Theory and practice. Concurrency: Practice and Experience, 9(6), June 1997.
• 5: Brad Calder, Dirk Grunwald, and Benjamin Zorn. Quantifying differences between C and C++ programs. Technical Report CU-CS-698-94, University of Colorado, Boulder, January 1994.
• 6: Craig Chambers , David Ungar, Interactive type analysis and extended message splitting; optimizing dynamically-typed object-oriented programs, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.150-164, June 1990, White Plains, New York, United States
• 7: Andrew Chien , Julian Dolby , Bishwaroop Ganguly , Vijay Karamcheti , Xingbin Zhang, Supporting High Level Programming with High Performance: The Illinois Concert System, Proceedings of the 1997 Workshop on High-Level Programming Models and Supportive Environments (HIPS '97), p.15, April 01-01, 1997
• 8: Jeffrey Dean , Craig Chambers , David Grove, Selective specialization for object-oriented languages, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.93-102, June 18-21, 1995, La Jolla, California, United States
• 9: 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
• 10: Margaret A. Ellis , Bjarne Stroustrup, The annotated C++ reference manual, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 11: Maryam Emami , Rakesh Ghiya , Laurie J. Hendren, Context-sensitive interprocedural points-to analysis in the presence of function pointers, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.242-256, June 20-24, 1994, Orlando, Florida, United States
• 12: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• 13: Tim Freeman , Frank Pfenning, Refinement types for ML, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.268-277, June 24-28, 1991, Toronto, Ontario, Canada
• 14: Keith E. Gorlen , Sanford M. Orlow , Perry S. Plexico, Data abstraction and object-oriented programming in C++, John Wiley & Sons, Inc., New York, NY, 1990
• 15: Cordelia Hall, Simon L. Peyton-Jones, and Patrick M. Sansom. Functional Programming, Glasgow 1994, chapter Unboxing Using Specialization. Workshops in Computing Science. Springer- Verlag, 1995.
• 16: Urs Hölzle , Craig Chambers , David Ungar, Optimizing Dynamically-Typed Object-Oriented Languages With Polymorphic Inline Caches, Proceedings of the European Conference on Object-Oriented Programming, p.21-38, July 15-19, 1991
• 17: Urs Hölzle , David Ungar, Optimizing dynamically-dispatched calls with run-time type feedback, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.326-336, June 20-24, 1994, Orlando, Florida, United States
• 18: N. C. Hutchinson, EMERALD: An object-based language for distributed programming, University of Washington, Seattle, WA, 1987
• 19: Christopher Lapkowski , Laurie J. Hendren, Extended SSA numbering: introducing SSA properties to languages with multi-level pointers, Proceedings of the 1996 conference of the Centre for Advanced Studies on Collaborative research, p.23, November 12-14, 1996, Toronto, Ontario, Canada
• 20: Xavier Leroy, Unboxed objects and polymorphic typing, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.177-188, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143205]
• 21: Jens Palsberg , Michael I. Schwartzbach, Object-oriented type inference, Conference proceedings on Object-oriented programming systems, languages, and applications, p.146-161, October 06-11, 1991, Phoenix, Arizona, United States
• 22: James Philbin , Jan Edler , Otto J. Anshus , Craig C. Douglas , Kai Li, Thread scheduling for cache locality, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.60-71, October 01-04, 1996, Cambridge, Massachusetts, United States
• 23: John Bradley Plevyak , Andrew Chien, Optimization of object-oriented and concurrent programs, 1996
• 24: John Plevyak , Andrew A. Chien, Precise concrete type inference for object-oriented languages, Proceedings of the ninth annual conference on Object-oriented programming systems, language, and applications, p.324-340, October 23-28, 1994, Portland, Oregon, United States
• 25: John Plevyak , Andrew A. Chien, Type Directed Cloning for Object-Oriented Programs, Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing, p.566-580, August 10-12, 1995
• 26: Zhong Shao , John H. Reppy , Andrew W. Appel, Unrolling lists, Proceedings of the 1994 ACM conference on LISP and functional programming, p.185-195, June 27-29, 1994, Orlando, Florida, United States
• 27: O. Shivers, Control flow analysis in scheme, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.164-174, June 20-24, 1988, Atlanta, Georgia, United States
• 28: Olin Grigsby Shivers, Control-flow analysis of higher-order languages of taming lambda, Carnegie Mellon University, Pittsburgh, PA, 1991
• 29: Olin Shivers. Topics in Advanced Language Implementation, chapter Data-Flow Analysis and Type Recovery in Scheme, pages 47-88. MIT Press, Cambridge, MA, 1991.
• 30: Guy L. Steele, Jr., Common LISP: the language (2nd ed.), Digital Press, Newton, MA, 1990
• 31: David Stoutamire and Stephen Omohundro. Sather 1.1, draft. Available online from hzZp:// www. i cs i. berkeley, edu/~ ather / Sather- i. i. ps, August 1995.
• 32: Sun Microsystems Computer Corporation. The Java Language Specification, March 1995. Available at http://java.sun.com/1.0alpha2/doc/javawhitepaper.ps.
• 33: Niklaus Wirth , Jürg Gutknecht, Project Oberon: the design of an operating system and compiler, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1992

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Object-oriented languages

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

General Terms:
Design, Languages, Measurement, Performance, Theory