Efficient multiple and predicated dispatching

ABSTRACT

The speed of message dispatching is an important issue in the overall performance of object-oriented programs. We have developed an algorithm for constructing efficient dispatch functions that combines novel algorithms for efficient single dispatching, multiple dispatching, and predicate dispatching. Our algorithm first reduces methods written in the general predicate dispatching model (which generalizes single dispatching, multiple dispatching, predicate classes and classifiers, and pattern-matching) into ones written using a simpler multimethod dispatching model. Our algorithm then computes a strategy for implementing multiple dispatching in terms of sequences of single dispatches, representing the strategy as a lookup DAG. Finally, our algorithm computes an implementation strategy separately for each of the single dispatches, producing for each dispatch a dispatch tree, which is a binary decision tree blending class identity tests, class range tests, and table lookups. Our algorithm exploits any available static information (from type declarations or class analysis) to prune unreachable paths from the lookup DAG, and uses any available dynamic profile information to minimize the expected time to search the dispatch trees. We measure the effectiveness of our dispatching algorithms on a collection of large Cecil programs, compiled by the Vortex optimizing compiler, showing improvements of up to 30% over already heavily optimized baseline versions.

REFERENCES

• Agesen 95: 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
• 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
• Bobrow et. al. 88: Daniel G. Bobrow , Linda G. DeMichiel , Richard P. Gabriel , Sonya E. Keene , Gregor Kiczales , David A. Moon, Common Lisp Object System specification, ACM SIGPLAN Notices, v.23 n.SI, p.1-142, September 1988 [doi>10.1145/885631.885632]
• Chambers & Ungar 90: 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
• Chambers 92: Craig Chambers, Object-Oriented Multi-Methods in Cecil, Proceedings of the European Conference on Object-Oriented Programming, p.33-56, June 29-July 03, 1992
• Chambers 93a: Craig Chambers. The Cecil Language: Specification and Rationale. Technical Report UW-CSE-93-03-05, Department of Computer Science and Engineering. University of Washington, March 1993. Revised, March 1997.
• Chambers 93b: Craig Chambers, Predicate Classes, Proceedings of the 7th European Conference on Object-Oriented Programming, p.268-296, July 26-30, 1993
• Chambers et al. 96: Craig Chambers, Jeffrey Dean, and David Grove. Whole-Program Optimization of Object-Oriented Languages. Teelmieal Report UW-CSE-96-06-02, Department of Computer Science and Engineering. University of Washington, June 1996.
• 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
• 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
• Dean et al. 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
• DeFouw et al. 98: Greg DeFouw , David Grove , Craig Chambers, Fast interprocedural class analysis, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.222-236, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268965]
• Driesen & Hölzle 95: Karel Driesen , Urs Hölzle, Minimizing row displacement dispatch tables, Proceedings of the tenth annual conference on Object-oriented programming systems, languages, and applications, p.141-155, October 15-19, 1995, Austin, Texas, United States
• Driesen 93: Karel Driesen, Selector table indexing & sparse arrays, Proceedings of the eighth annual conference on Object-oriented programming systems, languages, and applications, p.259-270, September 26-October 01, 1993, Washington, D.C., United States
• Driesen et al. 95: 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
• Dujardin 96: Eric Dujardin. Efficient Dispatch of Multimehtods in Constant Time with Dispatch Trees. Technical Report 2892, INRIA, Rocquencourt, France, 1996.
• Dujardin et al. 98: Eric Dujardin , Eric Amiel , Eric Simon, Fast algorithms for compressed multimethod dispatch table generation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.1, p.116-165, Jan. 1998 [doi>10.1145/271510.271521]
• Dussud 89: P. H. Dussud, TICLOS: an implementation of CLOS for the explorer family, Conference proceedings on Object-oriented programming systems, languages and applications, p.215-219, October 02-06, 1989, New Orleans, Louisiana, United States
• Ernst et al. 98: Michael Ernst , Craig Kaplan , Craig Chambers, Predicate Dispatching: A Unified Theory of Dispatch, Proceedings of the 12th European Conference on Object-Oriented Programming, p.186-211, July 20-24, 1998
• Fernandez 95: 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
• Goldberg & Robson 83: Adele Goldberg , David Robson, Smalltalk-80: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• Gosling et al. 96: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• Grove et al. 95: 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
• Grove et al. 97: David Grove , Greg DeFouw , Jeffrey Dean , Craig Chambers, Call graph construction in object-oriented languages, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.108-124, October 05-09, 1997, Atlanta, Georgia, United States
• Hamer et al. 90: J. Hamer, J.G. Hosking, and W.B. Mugridge. A Method for Integrating Classification Within an Object-Oriented Environment. Technical Report Auckland Computer Science Report No. 48, Department of Computer Science, University of Auckland, October 1990.
• Hölzle 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
• Hu & Tucker 71: T.C. Hu and A. C. Tucker. "Optimal Computer Search Trees and Variable-Length Alphabetical Codes. SIAM Journal on Applied Mathematics, 21 (4):514-532, 1971.
• Hudak et al. 92: Paul Hudak , Simon Peyton Jones , Philip Wadler , Brian Boutel , Jon Fairbairn , Joseph Fasel , María M. Guzmán , Kevin Hammond , John Hughes , Thomas Johnsson , Dick Kieburtz , Rishiyur Nikhil , Will Partain , John Peterson, Report on the programming language Haskell: a non-strict, purely functional language version 1.2, ACM SIGPLAN Notices, v.27 n.5, p.1-164, May 1992 [doi>10.1145/130697.130699]
• Hyafil & Rivest 76: Laurem Hyafil and RonaldL. Rivest. Constructing optimal binary decision trees is NP-complete. Information Processing Letters, 5( 1): 15-17, May 1976.
• Johnson 86: Ralph E. Johnson, Type-checking Smalltalk, Conference proceedings on Object-oriented programming systems, languages and applications, p.315-321, September 29-October 02, 1986, Portland, Oregon, United States
• Johnson et al. 88: 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
• Kaehler & Krasner 83: Ted Kaehler and Glenn Krasner. LOOM Large Object-Oriented Memory for Smalltalk-80 Systems. In G. Krasner, editor, Smalltalk-80 m Bits of History, Words of Advice, chapter 14, pages 251-270. Addison-Wesley, 1983.
• Kiczales & Rodriguez 90: Gregor Kiczales , Luis Rodriguez, Efficient method dispatch in PCL, Proceedings of the 1990 ACM conference on LISP and functional programming, p.99-105, June 27-29, 1990, Nice, France [doi>10.1145/91556.91600]
• Meyer 92: Bertrand Meyer, Eiffel: the language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• Milner et al. 97: Robin Milner , Mads Tofte , David Macqueen, The Definition of Standard ML, MIT Press, Cambridge, MA, 1997
• Morel & Renvoise 79: E. Morel , C. Renvoise, Global optimization by suppression of partial redundancies, Communications of the ACM, v.22 n.2, p.96-103, Feb. 1979 [doi>10.1145/359060.359069]
• Mugridge et al. 91: Warwick B. Mugridge , John Hamer , John G. Hosking, Multi-Methods in a Statically-Typed Programming Language, Proceedings of the European Conference on Object-Oriented Programming, p.307-324, July 15-19, 1991
• Nakamura et al. 96: Hiroaki Nakamura, Tamiya Onodera, and Mildo Takeuehi. Message dispatch using binary decision trees. Technical Report RT0137, IBM Research, Tokyo Research Laboratory, Kanagawa, Japan, March 1, 1996.
• Nelson 91: Greg Nelson, Systems programming with Modula-3, Prentice-Hall, Inc., Upper Saddle River, NJ, 1991
• Pang et al. 99: Candy Pang , Wade Holst , Yuri Leontiev , Duane Szafron, Multi-method Dispatch Using Multiple Row Displacement, Proceedings of the 13th European Conference on Object-Oriented Programming, p.304-328, June 14-18, 1999
• Peyton Jones 87: Simon L. Peyton Jones, The Implementation of Functional Programming Languages (Prentice-Hall International Series in Computer Science), Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 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
• Rose 88: 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
• Shalit 96: Andrew Shalit, editor. The Dylan Reference Manual. Addison-Wesley, Reading, MA, 1996.
• Steele Jr. 90: Guy L. Steele, Jr., Common LISP: the language (2nd ed.), Digital Press, Newton, MA, 1990
• Stroustrup 91: Bjarne Stroustrup, The C++ programming language (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• Taivalsaari 93: Antero Taivalsaari. Object-oriented programming with modes. Journal of Object-Oriented Programming, pages 25--32, June 1993.
• Vitek et al. 97: Jan Vitek , R. Nigel Horspool , Andreas Krall, Efficient type inclusion tests, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.142-157, October 05-09, 1997, Atlanta, Georgia, United States
• Zendra et al. 97: Olivier Zendra , Dominique Colnet , Suzanne Collin, Efficient dynamic dispatch without virtual function tables: the SmallEiffel compiler, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.125-141, October 05-09, 1997, Atlanta, Georgia, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory