Run-time evaluation of opportunities for object inlining in Java

ABSTRACT

Object-oriented languages, such as Java, encourage the use of many small objects linked together by field references, instead of a few monolithic structures. While this practice is beneficial from a program design perspective, it can slow down program execution by incurring many pointer indirections. One solution to this problem is object inlining: when the compiler can safely do so, it fuses small objects together, thus removing the reads/writes to the removed field, saving the memory needed to store the field and object header, and reducing the number of object allocations.The objective of this paper is to measure the potential for object inlining by studying the run-time behaviour of a comprehensive set of Java programs. We study the traces of program executions in order to determine which fields behave like inlinable fields. Since we are using dynamic information instead of a static analysis, our results give an upper bound on what could be achieved via a static compiler-based approach. Our experimental results measure the potential improvements attainable with object inlining, including reductions in the numbers of field reads and writes, and reduced memory usage.Our study shows that some Java programs can benefit significantly from object inlining, with close to a 10% speedup. Somewhat to our surprise, our study found one case, the <tt>db</tt> benchmark, where the most important inlinable field was the result of unusual program design, and fixing this small flaw led to both better performance and clearer program design. However, the opportunities for object inlining are highly dependent on the individual program being considered, and are in many cases very limited. Furthermore, fields that are inlinable also have properties that make them potential candidates for other optimizations such as removing redundant memory accesses. The memory savings possible through object inlining are moderate.

REFERENCES

• 1: Ashes suite collection http://www.sable.mcgill.ca/software/.
• 2: SPEC JVM98 benchmarks http://www.spec.org/osg/jvm98/.
• 3: 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
• 4: 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
• 5: Julian Dolby , Andrew A. Chien, An evaluation of automatic object inline allocation techniques, Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.1-20, October 18-22, 1998, Vancouver, British Columbia, Canada
• 6: Sanjay Ghemawat , Keith H. Randall , Daniel J. Scales, Field analysis: getting useful and low-cost interprocedural information, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.334-344, June 18-21, 2000, Vancouver, British Columbia, Canada
• 7: P. Laud. Analysis for object inlining in Java. In JOSES workshop, a satellite event of ETAPS 2001. http://i44w3.info.uni-karlsruhe.de/~josesworkshop/01-laud.ps.
• 8: O. Lhoták. Run-time evaluation of object inlining opportunities in Java. Technical Report 2002-3, McGill University, School of Computer Science, http://www.cs.mcgill.ca/resrchpages/reports/02/SOCS-02.3.ps.gz, 2002.
• 9: 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
• 10: R. Vallée-Rai. Soot - a Java optimization framework. Master's thesis, McGill University, School of Computer Science, http://www.sable.mcgill.ca/publications, July 2000.
• 11: Raja Vallée-Rai , Etienne Gagnon , Laurie J. Hendren , Patrick Lam , Patrice Pominville , Vijay Sundaresan, Optimizing Java Bytecode Using the Soot Framework: Is It Feasible?, Proceedings of the 9th International Conference on Compiler Construction, p.18-34, March 25-April 02, 2000
• 12: R. Vallée-Rai, L. Hendren, V. Sundaresan, P. Lam, E. Gagnon, and P. Co. Soot - a Java optimization framework. In Proceedings of CASCON 1999, pages 125--135, 1999.

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: Memory management (garbage collection); Optimization; Compilers

General Terms:
Languages, Measurement, Performance

Keywords:
Java, compilers, object inlining, optimization