Type feedback vs. concrete type inference: a comparison of optimization techniques for object-oriented languages

ABSTRACT

Two promising optimization techniques for object-oriented languages are type feedback (profile-based receiver class prediction) and concrete type inference (static analysis). We directly compare the two techniques, evaluating their effectiveness on a suite of 23 SELF programs while keeping other factors constant.Our results show that both systems inline over 95% of all sends and deliver similar overall performance with one exception: SELF's automatic coercion of machine integers to arbitrary-precision integers upon overflow confounds type inference and slows down arithmetic-intensive benchmarks.We discuss several other issues which, given the comparable run-time performance, may influence the choice between type feedback and type inference.

REFERENCES

• Age94: Ole Agesen. Constraint-Based Type Inference and Parametric Polymorphism. in SAS '94, First International Static Analysis Symposium, p. 78-100, Namur, Belgium, Sept. 1994. Springer-Verlag (LNCS 864).
• AU94: Ole Agesen , David Ungar, Sifting out the gold: delivering compact applications from an exploratory object-oriented programming environment, Proceedings of the ninth annual conference on Object-oriented programming systems, language, and applications, p.355-370, October 23-28, 1994, Portland, Oregon, United States
• Age95: Ole Agesen, The Cartesian Product Algorithm: Simple and Precise Type Inference Of Parametric Polymorphism, Proceedings of the 9th European Conference on Object-Oriented Programming, p.2-26, August 07-11, 1995
• AH95: Ole Agesen , Urs Holzle, Type Feedback vs. Concrete Type Inference: A Comparison of Optimization Techniques for Object-Oriented Languages, University of California at Santa Barbara, Santa Barbara, CA, 1995
• APS93: 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
• CGZ94: Brad Calder, Dirk Grunwald, and Benjamin Zorn. Quantifying Behavioral Differences Between C and C++ Programs. Journal of Programming Languages 4(2), Dec. 1994.
• CUL89: 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
• CU90: Craig Chambers , David Ungar, Interactive type analysis and extended message splitting; optimizing dynamically-typed object-oriented programs, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.150-164, June 1990, White Plains, New York, United States
• DGC95: 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
• DS84: 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]
• Dyk77: Eric J. Van Dyke. A dynamic incremental compiler for an interpretative language. HP Journal, p. 17-24, July 1977.
• Gro95: 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
• GW78: 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]
• HCU91: 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
• Höl94: Urs H61zle. Adaptive Optimization in SELF: Reconciling High Performance with Exploratory Programming. Ph.D. Thesis, Department of Computer Science, Stanford University, Aug. 1994. (Available from http://www.cs.ucsb.edu/--urs.)
• HU94a: 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
• HU94b: Urs Hölzle , David Ungar, A third-generation SELF implementation: reconciling responsiveness with performance, Proceedings of the ninth annual conference on Object-oriented programming systems, language, and applications, p.229-243, October 23-28, 1994, Portland, Oregon, United States
• JGZ88: Ralph E. Johnson , Justin O. Graver , Laurance W. Zurawski, TS: an optimizing compiler for smalltalk, Conference proceedings on Object-oriented programming systems, languages and applications, p.18-26, September 25-30, 1988, San Diego, California, United States
• Joh79: 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
• Kra83: Glenn Krasner, Smalltalk-80: bits of history, words of advice, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• Mit70: James George Mitchell, The design and construction of flexible and efficient interactive programming systems, 1970
• OPS92: Nicholas Oxhøj , Jens Palsberg , Michael I. Schwartzbach, Making Type Inference Practical, Proceedings of the European Conference on Object-Oriented Programming, p.329-349, June 29-July 03, 1992
• PS91: Jens Palsberg , Michael I. Schwartzbach, Object-oriented type inference, Conference proceedings on Object-oriented programming systems, languages, and applications, p.146-161, October 06-11, 1991, Phoenix, Arizona, United States
• PR94: Hemant D. Pande and Barbara G. Ryder. Static Type Determination and Aliasing for C++. Technical Report LCSR- TR-236, Rutgers University, Dec. 1994.
• PC94a: 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
• PC94b: John B. Plevyak and Andrew A. Chien. Precise Concrete Type Inference and its Use in Program Optimization. Unpublished report, Oct. 1994.
• PC94c: john B. Plevyak and Andrew A. Chien. Efficient cloning to eliminate dynamic dispatch in object-oriented languages. Unpublished report, Dec. 1994.
• PZC95: John Plevyak , Xingbin Zhang , Andrew A. Chien, Obtaining sequential efficiency for concurrent object-oriented languages, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.311-321, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199524]
• Suz81: Norihisa Suzuki, Inferring types in Smalltalk, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.187-199, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567553]
• US87: 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
• VHU92: Jan Vitek , R. Nigel Horspool , James S. Uhl, Compile-Time Analysis of Object-Oriented Programs, Proceedings of the 4th International Conference on Compiler Construction, p.236-250, October 05-07, 1992

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.2 Installation Management
          Subjects: Benchmarks

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Object-oriented languages
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Design, Languages, Measurement, Performance, Theory