Reconciling responsiveness with performance in pure object-oriented languages

ABSTRACT

Dynamically dispatched calls often limit the performance of object-oriented programs, since opject-oriented programming encourages factoring code into small, reusable units, thereby increasing the frequency of these expensive operations. Frequent calls not only slow down execution with the dispatch overhead per se, but more importantly they hinder optimization by limiting the range and effectiveness of standard global optimizations. In particular, dynamically dispatched calles prevent standard interprocedual optimizations that depend on the availability of a static call graph. The SELF implementation described here offers tow novel approaches to optimization. Type feedback speculatively inlines dynamically dispatched calls based on profile information that predicts likely receiver classes. Adaptive optimization reconciles optimizing compilation with interactive performance by incrementally optimizing only the frequently executed parts of a program. When combined, these two techniques result in a system that can execute programs significantly faster than previous systems while retaining much of the interactiveness of an interpreted system.

REFERENCES

• 1: Ole Agesen , Urs Hölzle, Type feedback vs. concrete type inference: a comparison of optimization techniques for object-oriented languages, Proceedings of the tenth annual conference on Object-oriented programming systems, languages, and applications, p.91-107, October 15-19, 1995, Austin, Texas, United States
• 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 Holzle, Eliminating Virtual Function Calls in C++ Programs, University of California at Santa Barbara, Santa Barbara, CA, 1996
• 4: APPLE. 1988. Object Pascal User's Manual. Apple Computer, Inc., Cupertino, Calif.
• 5: Craig David Chambers, The design and implementation of the self compiler, an optimizing compiler for object-oriented programming languages, Stanford University, Stanford, CA, 1992
• 6: CHAMBERS, C. 1993. The Cecil language--Specification and rationale. Tech. Rep. UW CS TR 93-03-05, Dept. of Computer Science, Univ. of Washington, Seattle, Wash.
• 7: Craig Chambers , David Ungar, Making pure object-oriented languages practical, Conference proceedings on Object-oriented programming systems, languages, and applications, p.1-15, October 06-11, 1991, Phoenix, Arizona, United States
• 8: C. Chambers , D. Ungar , E. Lee, An efficient implementation of SELF a dynamically-typed object-oriented language based on prototypes, Conference proceedings on Object-oriented programming systems, languages and applications, p.49-70, October 02-06, 1989, New Orleans, Louisiana, United States
• 9: Bay-Wei Chang , David Ungar, Animation: from cartoons to the user interface, Proceedings of the 6th annual ACM symposium on User interface software and technology, p.45-55, December 1993, Atlanta, Georgia, United States [doi>10.1145/168642.168647]
• 10: Pohua P. Chang , Scott A. Mahlke , William Y. Chen , Wen-mei W. Hwu, Profile-guided automatic inline expansion for C programs, Software—Practice & Experience, v.22 n.5, p.349-369, May 1992 [doi>10.1002/spe.4380220502]
• 11: Robert F. Cmelik , David Keppel, Shade: A Fast Instruction Set Simulator for Execution Profiling, Sun Microsystems, Inc., Mountain View, CA, 1993
• 12: Keith D. Cooper , Mary W. Hall , Linda Torczon, An experiment with inline substitution, Software—Practice & Experience, v.21 n.6, p.581-601, June 1991 [doi>10.1002/spe.4380210604]
• 13: Jack W. Davidson , Anne M. Holler, A study of a C function inliner, Software—Practice & Experience, v.18 n.8, p.775-790, August 1988 [doi>10.1002/spe.4380180805]
• 14: 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
• 15: 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
• 16: DEUTSCH, L. P. 1983. The Dorado Smalltalk-80 implementation: Hardware architecture's impact on software architecture. In Smalltalk-80: Bits of History and Words of Advice, G. Krasner, Ed. Addison-Wesley, Reading, Mass.
• 17: L. Peter Deutsch , Allan M. Schiffman, Efficient implementation of the smalltalk-80 system, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.297-302, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800542]
• 18: Amer Diwan , David Tarditi , Eliot Moss, Memory system performance of programs with intensive heap allocation, ACM Transactions on Computer Systems (TOCS), v.13 n.3, p.244-273, Aug. 1995 [doi>10.1145/210126.210129]
• 19: Mary F. Fernández, Simple and effective link-time optimization of Modula-3 programs, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.103-115, June 18-21, 1995, La Jolla, California, United States
• 20: GRAHAM, S. L., KESSLER, P. B., AND McKuSICK, M. K. 1983. An execution profiler for modular programs. Softw. Pract. Exper. 13, 671-685.
• 21: 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
• 22: Leo J. Guibas , Douglas K. Wyatt, Compilation and delayed evaluation in APL, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.1-8, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512761]
• 23: Mary Wolcott Hall, Managing interprocedural optimization, Rice University, Houston, TX, 1992
• 24: Gilbert Joseph Hansen, Adaptive systems for the dynamic run-time optimization of programs., 1974
• 25: Mark D Hill, Aspects of Cache Memory and Instruction, University of California at Berkeley, Berkeley, CA, 1987
• 26: Urs Hölzle, Adaptive optimization for self: reconciling high performance with exploratory programming, Stanford University, Stanford, CA, 1995
• 27: Urs Hölzle , Ole Agesen, Dynamic versus static optimization techniques for object-oriented languages, Theory and Practice of Object Systems, v.1 n.3, p.167-188, Fall 1995
• 28: 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
• 29: 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
• 30: Urs Hölzle , Craig Chambers , David Ungar, Debugging optimized code with dynamic deoptimization, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.32-43, June 15-19, 1992, San Francisco, California, United States
• 31: P. P. Chang , W.-W. Hwu, Inline function expansion for compiling C programs, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.246-257, June 19-23, 1989, Portland, Oregon, United States
• 32: IRLAM, G. 1991. SPA--SPARC analyzer tool set. Available via ftp from cs.adelaide.edu.au.
• 33: ISE. 1993. ISE Eiffel 3.0. Software. ISE, Inc., Santa Barbara, Calif.
• 34: Ronald L. Johnston, The Dynamic Incremental Compiler of APL\3000, Proceedings of the international conference on APL: part 1, p.82-87, May 30-June 01, 1979, New York, New York, United States
• 35: Philip J. Koopman, Jr. , Peter Lee , Daniel P. Siewiorek, Cache behavior of combinator graph reduction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.14 n.2, p.265-297, April 1992 [doi>10.1145/128861.128867]
• 36: James George Mitchell, The design and construction of flexible and efficient interactive programming systems, 1970
• 37: PANDE, H. AND RYDER, B. 1994. Static type determination for C++. Tech. Rep. LCSR-TR- 197a, Rutgers Univ., Piscataway, N.J.
• 38: PARCPLACE. 1992. VisualWorks 1.0 Smalltalk System. Software. ParcPlace Systems, Sunnyvale, Calif.
• 39: 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
• 40: Mark Baldwin Reinhold, Cache performance of garbage-collected programming languages, Massachusetts Institute of Technology, Cambridge, MA, 1993
• 41: SILICON GRAPHICS. 1993. SGI Delta C++ programming environment. Silicon Graphics, Inc., Mountain View, Calif. Software.
• 42: Michael Sannella , John Maloney , Bjorn Freeman-Benson , Alan Borning, Multi-way versus one-way constraints in user interfaces: experience with the DeltaBlue algorithm, Software—Practice & Experience, v.23 n.5, p.529-566, May 1993 [doi>10.1002/spe.4380230507]
• 43: SRIVASTAVA, A. AND WALL, D. 1992. A practical system for intermodule code optimization at link-time. DEC WRL Res. Rep. 92/6, Digital Equipment Corp., Palo Alto, Calif.
• 44: David Ungar , Randall B. Smith, Self: The power of simplicity, Conference proceedings on Object-oriented programming systems, languages and applications, p.227-242, October 04-08, 1987, Orlando, Florida, United States
• 45: VAN DYKE, E. 1977. A dynamic incremental compiler for an interpretative language. HP J. 28, 3 (July), 17-24.
• 46: P. R. Wilson , T. G. Moher, Design of the opportunistic garbage collector, Conference proceedings on Object-oriented programming systems, languages and applications, p.23-35, October 02-06, 1989, New Orleans, Louisiana, United States
• 47: David W. Wall, Predicting program behavior using real or estimated profiles, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.59-70, June 24-28, 1991, Toronto, Ontario, Canada

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.6 Programming Environments
          Subjects: Interactive environments
      D.2.m Miscellaneous
          Subjects: Rapid prototyping**
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Run-time environments; Interpreters; Compilers
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Interactive systems

General Terms:
Languages

Keywords:
adaptive optimization, pause clustering, profile-based optimization, run-time compilation, type feedback