Automatic program specialization for Java

ABSTRACT

The object-oriented style of programming facilitates program adaptation and enhances program genericness, but at the expense of efficiency. We demonstrate experimentally that state-of-the-art Java compilers fail to compensate for the use of object-oriented abstractions in the implementation of generic programs, and that program specialization can eliminate a significant portion of these overheads. We present an automatic program specializer for Java, illustrate its use through detailed case studies, and demonstrate experimentally that it can significantly reduce program execution time. Although automatic program specialization could be seen as being subsumed by existing optimizing compiler technology, we show that specialization and compiler optimization are in fact complementary.

REFERENCES

• 1: Reynald Affeldt , Hidehiko Masuhara , Eijiro Sumii , Akinori Yonezawa, Supporting objects in run-time bytecode specialization, Proceedings of the ASIAN symposium on Partial evaluation and semantics-based program manipulation, p.50-60, September 12-14, 2002, Aizu, Japan [doi>10.1145/568173.568179]
• 2: 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
• 3: Gerald Aigner , Urs Hölzle, Eliminating Virtual Function Calls in C++ Programs, Proceedings of the 10th European Conference on Object-Oriented Programming, p.142-166, July 08-12, 1996
• 4: 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
• 5: Andersen, L. 1994. Program analysis and specialization for the C programming language. Ph.D. thesis, Computer Science Department, University of Copenhagen. DIKU Technical Report 94/19.
• 6: Baier, R., Glück, R., and Zöchling, R. 1994. Partial evaluation of numerical programs in Fortran. In ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation (PEPM'94). Technical Report 94/9, University of Melbourne, Australia, Orlando, FL, USA, 119--132.
• 7: Blount, B. and Chatterjee, S. 1999. An evaluation of Java for numerical computing. Scientific Programming 7(2), 97--110. Special Issue: High Performance Java Compilation and Runtime Issues.
• 8: Bondorf, A. 1990. Self-applicable partial evaluation. Ph.D. thesis, DIKU, University of Copenhagen, Denmark. Revised version: DIKU Report 90/17.
• 9: Mathias Braux , Jacques Noyé, Towards partially evaluating reflection in Java, Proceedings of the 2000 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation, p.2-11, January 22-23, 2000, Boston, Massachusetts, United States
• 10: Budimlić, Z. and Kennedy, K. 1999. Prospects for scientific computing in polymorphic, object-oriented style. In Proceedings of the Ninth SIAM Conference of Parallel Processing in Scientific Computing. SIAM, San Antonio.
• 11: Zoran Budimlic , Ken Kennedy, JaMake: A Java Compiler Environment, Proceedings of the Third International Conference on Large-Scale Scientific Computing-Revised Papers, p.201-209, June 06-10, 2001
• 12: Budimlić, Z., Kennedy, K., and Piper, J. 1999. The cost of being object-oriented: A preliminary study. Scientific Computing 7, 2, 87--95.
• 13: C. Chambers , D. Ungar, Customization: optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.146-160, June 19-23, 1989, Portland, Oregon, United States
• 14: Charles Consel, A tour of Schism: a partial evaluation system for higher-order applicative languages, Proceedings of the 1993 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.145-154, June 14-16, 1993, Copenhagen, Denmark [doi>10.1145/154630.154645]
• 15: Charles Consel , Luke Hornof , François Noël , Jacques Noyé , Nicolae Volansche, A Uniform Approach for Compile-Time and Run-Time Specialization, Selected Papers from the Internaltional Seminar on Partial Evaluation, p.54-72, February 12-16, 1996
• 16: Cooper, K., Hall, M., and Kennedy, K. 1992. Procedure cloning. In Proceedings of the 1992 International Conference on Computer Languages. IEEE Computer Society Press, Oakland, CA, USA, 96--105.
• 17: 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
• 18: 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
• 19: 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
• 20: 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
• 21: 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
• 22: Nobuhisa Fujinami, Determination of Dynamic Method Dispatches Using Run-Time Code Generation, Proceedings of the Second International Workshop on Types in Compilation, p.253-271, March 25-27, 1998
• 23: Erich Gamma , Richard Helm , Ralph Johnson , John Vlissides, Design patterns: elements of reusable object-oriented software, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 24: David Grove , Jeffrey Dean , Charles Garrett , Craig Chambers, Profile-guided receiver class prediction, Proceedings of the tenth annual conference on Object-oriented programming systems, languages, and applications, p.108-123, October 15-19, 1995, Austin, Texas, United States
• 25: 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
• 26: Luke Hornof , Jacques Noyé, Accurate binding-time analysis for imperative languages: flow, context, and return sensitivity, Theoretical Computer Science, v.248 n.1-2, p.3-27, October 2000 [doi>10.1016/S0304-3975(00)00048-7]
• 27: Luke Hornof , Charles Consel , Jacques Noyé, Effective Specialization of Realistic Programs via Use Sensitivity, Proceedings of the 4th International Symposium on Static Analysis, p.293-314, September 08-10, 1997
• 28: IBM. 2001. IBM JDK 1.3.1. http://www.ibm.com/java/jdk.
• 29: IBM. 2002. Jikes RVM 2.1.0. http://www.ibm.com/developerworks/oss/jikesrvm/.
• 30: John Irwin , Jean-Marc Loingtier , John R. Gilbert , Gregor Kiczales , John Lamping , Anurag Mendhekar , Tatiana Shpeisman, Aspect-Oriented Programming of Sparse Matrix Code, Proceedings of the Scientific Computing in Object-Oriented Parallel Environments, p.249-256, December 08-11, 1997
• 31: Kazuaki Ishizaki , Motohiro Kawahito , Toshiaki Yasue , Hideaki Komatsu , Toshio Nakatani, A study of devirtualization techniques for a Java Just-In-Time compiler, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.294-310, October 2000, Minneapolis, Minnesota, United States
• 32: Java Grande Forum. 1999. The Java Grande Forum benchmark suite. http://www. javagrande.org.
• 33: Neil D. Jones , Carsten K. Gomard , Peter Sestoft, Partial evaluation and automatic program generation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 34: Gregor Kiczales , Erik Hilsdale , Jim Hugunin , Mik Kersten , Jeffrey Palm , William G. Griswold, An Overview of AspectJ, Proceedings of the 15th European Conference on Object-Oriented Programming, p.327-353, June 18-22, 2001
• 35: Kiczales, G., Lamping, J., Mendhekar, A., Maeda, C., Lopes, C., Loingtier, J., and Irwin, J. 1997. Aspect-oriented programming. In Proceedings of the European Conference on Object-oriented Programming (ECOOP'97), M. Aksit and S. Matsuoka, Eds. Lecture Notes in Computer Science, vol. 1241. Springer, Jyväskylä, Finland, 220--242.
• 36: Julia L. Lawall , Gilles Muller, Efficient Incremental Checkpointing of Java Programs, Proceedings of the 2000 International Conference on Dependable Systems and Networks (formerly FTCS-30 and DCCA-8), p.61-70, June 25-28, 2000
• 37: J. W. Lloyd , J. C. Shepherdson, Partial evaluation in logic programming, Journal of Logic Programming, v.11 n.3-4, p.217-242, Oct./Nov. 1991 [doi>10.1016/0743-1066(91)90027-M]
• 38: Luján, M. 1999. Object oriented linear algebra. M.S. thesis, University of Manchester.
• 39: Mikel Luján , T. L. Freeman , John R. Gurd, OoLALA: an object oriented analysis and design of numerical linear algebra, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.229-252, October 2000, Minneapolis, Minnesota, United States
• 40: Luján, M., Gurd, J., and Freeman, T. 2001. OoLaLa: Transformations for implementations of matrix operations at high abstraction levels. In Proceedings 4th Workshop on Parallel Object-Oriented Scientific Computing---POOSC'01. ACM Press, Tampa Bay, Florida, USA.
• 41: Marquard, M. and Steensgaard, B. 1992. Partial evaluation of an object-oriented imperative language. M.S. thesis, University of Copenhagen.
• 42: Hidehiko Masuhara , Akinori Yonezawa, A portable-approach to dynamic optimization in run-time specialization, New Generation Computing, v.20 n.1, p.101-124, January 2002 [doi>10.1007/BF03037261]
• 43: Gilles Muller , Ulrik Pagh Schultz, Harissa: A Hybrid Approach to Java Execution, IEEE Software, v.16 n.2, p.44-51, March 1999 [doi>10.1109/52.754052]
• 44: Hirotaka Ogawa , Kouya Shimura , Satoshi Matsuoka , Fuyuhiko Maruyama , Yukihiko Sohda , Yasunori Kimura, OpenJIT: An Open-Ended, Reflective JIT Compiler Framework for Java, Proceedings of the 14th European Conference on Object-Oriented Programming, p.362-387, June 12-16, 2000
• 45: 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
• 46: Rajendra K. Raj , Ewan Tempero , Henry M. Levy , Andrew P. Black , Norman C. Hutchinson , Eric Jul, Emerald: a general-purpose programming language, Software—Practice & Experience, v.21 n.1, p.91-118, Jan. 1991 [doi>10.1002/spe.4380210107]
• 47: Schultz, U. 2000. Object-oriented software engineering using partial evaluation. Ph.D. thesis, University of Rennes I, Rennes, France.
• 48: Ulrik Pagh Schultz, Partial Evaluation for Class-Based Object-Oriented Languages, Proceedings of the Second Symposium on Programs as Data Objects, p.173-197, May 21-23, 2001
• 49: Ulrik Pagh Schultz , Julia L. Lawall , Charles Consel , Gilles Muller, Towards Automatic Specialization of Java Programs, Proceedings of the 13th European Conference on Object-Oriented Programming, p.367-390, June 14-18, 1999
• 50: Ulrik P. Schultz , Julia L. Lawall , Charles Consel, Specialization Patterns, Proceedings of the 15th IEEE international conference on Automated software engineering, p.197, September 11-15, 2000
• 51: SPEC. 1998. SPEC JVM 98 benchmarks. Standard Performance Evaluation Corporation. http://www.specbench.org/osg/jvm98/.
• 52: 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
• 53: Gregory T. Sullivan, Dynamic Partial Evaluation, Proceedings of the Second Symposium on Programs as Data Objects, p.238-256, May 21-23, 2001
• 54: Sun Microsystems, Inc. 1999. Sun JDK 1.2.2. http://java.sun.com/products/j2se.
• 55: Sun Microsystems, Inc. 2002. Sun JDK 1.4.0. http://java.sun.com/products/j2se.
• 56: Vijay Sundaresan , Laurie Hendren , Chrislain Razafimahefa , Raja Vallée-Rai , Patrick Lam , Etienne Gagnon , Charles Godin, Practical virtual method call resolution for Java, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.264-280, October 2000, Minneapolis, Minnesota, United States
• 57: Frank Tip , Chris Laffra , Peter F. Sweeney , David Streeter, Practical experience with an application extractor for Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.292-305, November 01-05, 1999, Denver, Colorado, United States
• 58: Veldhuizen, T. 1999. C++ templates as partial evaluation. In ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation (PEPM'98). ACM Press, San Antonio, TX, USA, 13--18.
• 59: Todd L. Veldhuizen, Just When You Thought Your Little Language Was Safe: ``Expression Templates'' in Java, Proceedings of the Second International Symposium on Generative and Component-Based Software Engineering-Revised Papers, p.188-202, October 09-12, 2000
• 60: Eugen N. Volanschi , Charles Counsel , Gilles Muller , Crispin Cowan, Declarative specialization of object-oriented programs, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.286-300, October 05-09, 1997, Atlanta, Georgia, United States
• 61: Tiejun Wang , Scott F. Smith, Precise Constraint-Based Type Inference for Java, Proceedings of the 15th European Conference on Object-Oriented Programming, p.99-117, June 18-22, 2001
• 62: XEROX 2000. AspectJ home page. http://aspectj.org. Xerox Corp.
• 63: Ayal Zaks , Vitaly Feldman , Nava Aizikowitz, Sealed calls in Java packages, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.83-92, October 2000, Minneapolis, Minnesota, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program transformation

General Terms:
Design, Experimentation

Keywords:
Automatic program specialization, Java, object-oriented languages, optimization, partial evaluation