Efficient dynamic dispatch without virtual function tables: the SmallEiffel compiler

ABSTRACT

SmallEiffel is an Eiffel compiler which uses a fast simple type inference mechanism to remove most late binding calls, replacing them by static bindings. Starting from the system's entry point, it compiles only statically living code, which saves compiling and then removing dead code. As the whole system is analyzed at compile time, multiple inheritance and genericity do not cause any overhead.SmallEiffel features a coding scheme which eliminates the need for virtual function tables. Dynamic dispatch is implemented without any array access but uses a simple static binary branch code. We show that this implementation makes it possible to use modern hardware very efficiently. It also allows us to inline more calls even when dynamic dispatch is required. Some more dispatch sites are removed after the type inference algorithm has been performed, if the different branches of a dispatch site lead to the same code.The advantage of this approach is that it greatly speeds up execution time and considerably decreases the amount of generated code.

REFERENCES

• 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
• Age96: Ole Agesen, Concrete type inference: delivering object-oriented applications, Stanford University, Stanford, CA, 1996
• AH95: 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
• AH96: 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
• 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
• AU77: Alfred V. Ah0 and Jeffrey D. Ullman. Principles o/Compiler Design. Addison-Wesley, eading~ Massachusetts, 1977. ~ '
• BS96: David F. Bacon , Peter F. Sweeney, Fast static analysis of C++ virtual function calls, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.324-341, October 06-10, 1996, San Jose, California, United States
• CCZ97: Suzanne Collin , Dominique Colnet , Olivier Zendra, Type Inference for Late Binding: The SmallEiffel Compiler, Proceedings of the Joint Modular Languages Conference on Modular Programming Languages, p.67-81, March 19-21, 1997
• CF91: Robert Cartwright , Mike Fagan, Soft typing, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.278-292, June 24-28, 1991, Toronto, Ontario, Canada
• CG94a: Brad Calder , Dirk Grunwald, Reducing indirect function call overhead in C++ programs, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.397-408, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177973]
• CG94b: Diane Corney , John Gough, Type test elimination using typeflow analysis, Proceedings of the international conference on Programming languages and system architectures, p.137-150, April 1994, Zurich, Switzerland
• CU89: 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
• DDG+96: Jeffrey Dean , Greg DeFouw , David Grove , Vassily Litvinov , Craig Chambers, Vortex: an optimizing compiler for object-oriented languages, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.83-100, October 06-10, 1996, San Jose, California, 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
• DH96: Karel Driesen , Urs Hölzle, The direct cost of virtual function calls in C++, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.306-323, October 06-10, 1996, San Jose, California, United States
• Dha91: D. M. Dhamdhere, Practical adaption of the global optimization algorithm of Morel and Renvoise, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.291-294, April 1991 [doi>10.1145/103135.214520]
• DHV95: Karel Driesen , Urs Hölzle , Jan Vitek, Message Dispatch on Pipelined Processors, Proceedings of the 9th European Conference on Object-Oriented Programming, p.253-282, August 07-11, 1995
• DMM96: Amer Diwan , J. Eliot B. Moss , Kathryn S. McKinley, Simple and effective analysis of statically-typed object-oriented programs, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.292-305, October 06-10, 1996, San Jose, California, United States
• 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]
• EST95: Jonathan Eifrig , Scott Smith , Valery Trifonov, Sound polymorphic type inference for objects, Proceedings of the tenth annual conference on Object-oriented programming systems, languages, and applications, p.169-184, October 15-19, 1995, Austin, Texas, United States
• GJ90: Justin O. Graver , Ralph E. Johnson, A type system for Smalltalk, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.136-150, December 1989, San Francisco, California, United States [doi>10.1145/96709.96722]
• GR83: Adele Goldberg , David Robson, Smalltalk-80: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 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
• HU95: Urs Hölzle , David Ungar, Do Object-Oriented Languages Need Special Hardware Support?, Proceedings of the 9th European Conference on Object-Oriented Programming, p.283-302, August 07-11, 1995
• JGS96: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• KRS94: Jens Knoop , Oliver Rüthing , Bernhard Steffen, Partial dead code elimination, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.147-158, June 20-24, 1994, Orlando, Florida, United States
• Mey88: Bertrand Meyer, Object-oriented software construction (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1997
• Mey94: Bertrand Meyer, Eiffel: the language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• Mil78: R. Milner. A Theory of Type Polymorphism in Programming. In Journal of Computer and System Sciences, pages 348-375, 1978.
• MNC+91: G. Masini, A. Napoli, D. Colnet, D. L6onard, and K. Tombre. Object Oriented Languages. Academic Press Limited, London, 1991.
• PC94: 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
• 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
• PS92: Jens Palsberg , Michael I. Schwartzbach, Safety analysis versus type inference for partial types, Information Processing Letters, v.43 n.4, p.175-180, Sept. 28, 1992 [doi>10.1016/0020-0190(92)90196-3]
• Ros88: John R. Rose, Fast dispatch mechanisms for stock hardware, Conference proceedings on Object-oriented programming systems, languages and applications, p.27-35, September 25-30, 1988, San Diego, California, United States
• ST84: Norihisa Suzuki , Minoru Terada, Creating efficient systems for object-oriented languages, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.290-296, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800541]
• Str86: Bjarne Stroustrup, The C++ programming language, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 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]
• UP87: David Ungar , David Patterson, What price Smalltalk?, Computer, v.20 n.1, p.67-74, Jan. 1987 [doi>10.1109/MC.1987.1663359]
• 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:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Eiffel

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