Selective specialization for object-oriented languages

ABSTRACT

Dynamic dispatching is a major source of run-time overhead in object-oriented languages, due both to the direct cost of method lookup and to the indirect effect of preventing other optimizations. To reduce this overhead, optimizing compilers for object-oriented languages analyze the classes of objects stored in program variables, with the goal of bounding the possible classes of message receivers enough so that the compiler can uniquely determine the target of a message send at compile time and replace the message send with a direct procedure call. Specialization is one important technique for improving the precision of this static class information: by compiling multiple versions of a method, each applicable to a subset of the possible argument classes of the method, more precise static information about the classes of the method's arguments is obtained. Previous specialization strategies have not been selective about where this technique is applied, and therefore tended to significantly increase compile time and code space usage, particularly for large applications. In this paper, we present a more general framework for specialization in object-oriented languages and describe a goal directed specialization algorithm that makes selective decisions to apply specialization to those cases where it provides the highest benefit. Our results show that our algorithm improves the performance of a group of sizeable programs by 65% to 275% while increasing compiled code space requirements by only 4% to 10%. Moreover, when compared to the previous state-of-the-art specialization scheme, our algorithm improves performance by 11% to 67% while simultaneously reducing code space requirements by 65% to 73%.

REFERENCES

• Amiel et al. 94: Eric Amiel , Olivier Gruber , Eric Simon, Optimizing multi-method dispatch using compressed dispatch tables, Proceedings of the ninth annual conference on Object-oriented programming systems, language, and applications, p.244-258, October 23-28, 1994, Portland, Oregon, United States
• Chambers & Ungar 89: C. Chambers , D. Ungar, Customization: optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language, ACM SIGPLAN Notices, v.24 n.7, p.146-160, July 1989
• Chambers & Ungar 91: Craig Chambers , David Ungar, Making pure object-oriented languages practical, ACM SIGPLAN Notices, v.26 n.11, p.1-15, Nov. 1991
• Chambers 92: Craig David Chambers, The design and implementation of the self compiler, an optimizing compiler for object-oriented programming languages, Stanford University, Stanford, CA, 1992
• Chambers 93: Craig Chambers. The Cecil Language: Specification and Rationale. Technical Report TR-93-03-05, Department of Computer Science and Engineering. University of Washington, March 1993.
• Chambers et al. 89: C. Chambers , D. Ungar , E. Lee, An efficient implementation of SELF a dynamically-typed object-oriented language based on prototypes, ACM SIGPLAN Notices, v.24 n.10, p.49-70, Oct. 1989
• Chambers et al. 95: Craig Chambers , Jeffrey Dean , David Grove, A framework for selective recompilation in the presence of complex intermodule dependencies, Proceedings of the 17th international conference on Software engineering, p.221-230, April 24-28, 1995, Seattle, Washington, United States [doi>10.1145/225014.225035]
• Chen et al. 94: Weimin Chen , Volker Turau , Wolfgang Klas, Efficient Dynamic Look-Up Strategy for Multi-Methods, Proceedings of the 8th European Conference on Object-Oriented Programming, p.408-431, July 04-08, 1994
• Cooper et al. 92: Keith D. Cooper, Mary W. Hall, and Ken Kennedy. Procedure Cloning. In Proceedings of 1992 IEEE International Conference on Computer Languages, pages 96- 105, Oakland, CA, April 1992.
• Dean & Chambers 94: Jeffrey Dean , Craig Chambers, Towards better inlining decisions using inlining trials, Proceedings of the 1994 ACM conference on LISP and functional programming, p.273-282, June 27-29, 1994, Orlando, Florida, United States
• Dean et al. 95: 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
• Garrett et al. 94: Charlie Garrett, Jeffrey Dean, David Grove, and Craig Chambers. Measurement and Application of Dynamic Receiver Class Distributions. Technical Report UW-CS 94-03- 05, University of Washington, March 1994.
• Grove & Torczon 93: Dan Grove , Linda Torczon, Interprocedural constant propagation: a study of jump function implementation, ACM SIGPLAN Notices, v.28 n.6, p.90-99, June 1993
• Holzle & Ungar 94: Urs Hölzle , David Ungar, Optimizing dynamically-dispatched calls with run-time type feedback, ACM SIGPLAN Notices, v.29 n.6, p.326-336, June 1994
• Holzle et al. 91: 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
• Ingalls 86: Daniel H. H. Ingalls, A simple technique for handling multiple polymorphism, ACM SIGPLAN Notices, v.21 n.11, p.347-349, Nov. 1986
• Jones et al. 93: Neil D. Jones , Carsten K. Gomard , Peter Sestoft, Partial evaluation and automatic program generation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• Katz & Weise 92: M. Katz and D. Weise. Towards a New Perspective on Partial Evaluation. In Proceedings of the Workshop on Partial Evaluation and Semantics-Based Program Manipulation '92, pages 29-36. Yale University, 1992.
• Kiczales & Rodriguez 89: Gregor Kiczales and Luis Rodriguez. Efficient Method Dispatch in PCL. Technical Report SSL 89-95, Xerox PARC Systems Sciences Laboratory, 1989.
• Kilian 88: Michael F. Kilian. Why Trellis/Owl Runs Fast. Unpublished manuscript, March 1988.
• Lea 90: Doug Lea. Customization in C++. In Proceedings of the 1990 Usenix C++ Conference, San Francisco, CA, Aprfi 1990.
• Lim & Stolcke 91: Chu-Cheow Lim and Andreas Stolcke. Sather Language Design and Performance Evaluation. Technical Report TR 91-034, International Computer Science Institute, May 1991.
• Palsberg & Schwartzbach 91: Jens Palsberg , Michael I. Schwartzbach, Object-oriented type inference, ACM SIGPLAN Notices, v.26 n.11, p.146-161, Nov. 1991
• Pande & Ryder 94: Hemant D. Pande and Barbara G. Ryder. Static Type Determination for C++. in Proceedings of Sixth USENIX C+ + Technical Conference, 1994.
• Plevyak & Chien 94: 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
• Ruf & Weise 91: Erik Ruf , Daniel Weise, Using types to avoid redundant specialization, Proceedings of the 1991 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.321-333, June 17-19, 1991, New Haven, Connecticut, United States

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Compilers

General Terms:
Algorithms, Languages, Performance