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. 1.O. Agesen, J. Palsberg, and M. Schwartzbach. Type inference of SELF: Analysis of objects with dynamic and multiple inheritance. In Proceedings of ECOOP '93, 1993.
2. 2.P. America. Inheritance and subtyping in a parallel object-oriented language, in Proceedings of ECOOP, pages 234-42. Springer-Verlag, June 1987.
3. 3.A. Black, N. Hutchinson, E. Jul, and H. Levy. Object structure in the emerald system. In Proceedings of OOPSLA '86, pages 78-86. ACM, September 1986.
4. 4.Zoran Budimlic and Ken Kennedy. Optimizing java: Theory and practice. Concurrency: Practice and Experience, 9(6), June 1997.
5. 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. 6.C. Chambers and D. Ungar. Iterative type analysis and extended message splitting. In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation, pages 150-60, 1990.
7. 7.Andrew Chien, Julian Dolby, Bishwaroop Ganguly, Vijay Karamcheti, and Xingbin Zhang. Supporting high level programming with high performance: The Illinois Concert system. In Proceedings of the Second International Workshop on High-level Parallel Programming Models and Supportive Environments, pages 15-24, April 1997.
8. 8.Jeffrey Dean, Craig Chambers, and David Grove. Selective specialization for object-oriented languages. In Proceedings of the A CM SIGPLAN '95 Conference on Programmin g Language Design and implementation, pages 93-102, La Jolla, CA, June 1995.
9. 9.Julian Dolby. Automatic inline allocation of objects. In Proceedings of the 1997 A CM SIGPLAN Conference on Programming Language Design and Implementation, pages 7-17, Las Vegas, Nevada, June 1997.
10. 10.Margaret A. Ellis and Bjarne Stroustrup. The Annotated C++ Reference Manual. Addison-Wesley, 1990.
11. 11.Maryam Emami, Rakesh Ghiya, and Laurie J. Hendren. Context-sensitive interprocedural points-to analysis in the presence of function pointers. In Proceedings of the 1994 A CM SIGPLAN Conference on Programming Language Design and Implementation, pages 242-256, 1994.
12. 12.Jeanne Ferrante, Karl J. Ottenstein, and Joe D. Warren. The program dependence graph and its use in optimization. A CM Transactions on Programming Languages and Systems, 9(3):319-49, July 1987.
13. 13.Tim Freeman and Frank Pfenning. Refinement types for ML. in Proceedings of the 1991 A CM SIGPLAN Conference on Programming Language Design and Implementation, June 1991.
14. 14.Keith E. Gorlen, Sanford M. Orlow, and Perry S. Plexico. Data Abstraction and Object-Oriented Programming in C++. John Wiley and Sons, 1991.
15. 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. 16.Urs HSlzle, Craig Chambers, and David Ungar. Optimizing dynamically-typed objectoriented languages with polymorphic inline caches. In ECOOP'91 Conference Proceedings. Springer- Verlag, 1991. Lecture Notes in Computer Science 512.
17. 17.Urs HSlzle and David Ungar. Optimizing dynamically-dispatched calls with run-time type feedback. In Proceedings of the 1994 A CM SIC- PLAN Conference on Programming Language Design and Implementation, pages 326-336, June 1994.
18. 18.Norman C. Hutchinson. Emerald: An Object-Based Language for Distributed Programming. PhD thesis, University of Washington, Department of Computer Science, Seattle, Washington, 1987. TR-87- 01-01.
19. 19.Christopher Lapkowski and Laurie Hendren. Extended ssa numbering: Introducing ssa properties to languages with multi-level pointers. In Proceedings of GASCON, 1996.
20. 20.Xavier Leroy. Unboxed objects and polymorphic typing. In Proceedings of the 19th Symposium on the Principles of Programming Languages, pages 177-188, 1992.
21. 21.J. Palsberg and M. Schwartzbach. Object-oriented type inference. In Proceedings of OOPSLA '91, pages 146-61, 1991.
22. 22.James Philbin, Jan Edler, Otto J. Anshus, Craig C. Douglas, and Kai Li. Thread scheduling for cache locality. In Proceedings of the Seventh Symposium on Architectural Support for Programming Languages and Operating Systems (ASPLOS-VII), pages 60-71, 1996.
23. 23.John Plevyak. Optimization of Object-Oriented and Concurrent Programs. PhD thesis, University of Illinois at Urbana-Champaign, Urbana, Illinois, 1996.
24. 24.John Plevyak and Andrew A. Chien. Precise concrete type inference of object-oriented programs. In Proceedings of OOPSLA '94, Object-Oriented Programming Systems, Languages and Architectures, pages 324-340, 1994.
25. 25.John Plevyak and Andrew A. Chien. Type directed cloning for object-oriented programs. In Proceedings of the Workshop for Languages and Compilers for Parallel Computing, pages 566-580, 1995.
26. 26.Zhong Shao, John H. Reppy, and Andrew W. Appel. Unrolling lists. In A CM Conference on Lisp and Functional Programming, June 1994.
27. 27.Olin Shivers. Control flow analysis in scheme, in SIGPLAN Conference on Programming Language Design and Implementation, pages 164-74. ACM, 1988.
28. 28.Olin Shivers. Control-Flow Analysis of Higher- Order Languages. PhD thesis, Carnegie Mellon University Department of Computer Science, Pittsburgh, PA, May 1991. also CMU-CS-91-145.
29. 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. 30.Guy L. Steele Jr. Common LISP: The Language. Digital Press, second edition, 1990.
31. 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. 32.Sun Microsystems Computer Corporation. The Java Language Specification, March 1995. Available at http://java.sun.com/1.0alpha2/doc/javawhitepaper.ps.
33. 33.N. Wirth and J. Gutknecht. Project Oberon: The Design of an Operating System and Compiler. Addison Wesley, 1992.

Index Terms

• Software and its engineering

  • Software notations and tools

    • Compilers

    • General programming languages

      • Language types

        • Object oriented languages