Optimizing multi-method dispatch using compressed dispatch tables

ABSTRACT

Optimizing method dispatch is a central issue in object-oriented language implementation. The dispatch table scheme, used for example by C++, is the only implementation of method dispatch that offers constant time performance. This property is the main asset of dispatch tables and a major requirement for some languages. However, the major drawback of dispatch tables is the space they require. Reducing the size of dispatch tables has been studied in the case of mono-methods with techniques such as coloring. In the case of multi-methods, dispatch tables are practically unusable as they grow as a power of the number of arguments. In this paper, we propose an algorithm to compress the dispatch tables of multi-methods by analyzing their signatures.

REFERENCES

• ADL91: Rakesh Agrawal , Linda G. Demichiel , Bruce G. Lindsay, Static type checking of multi-methods, Conference proceedings on Object-oriented programming systems, languages, and applications, p.113-128, October 06-11, 1991, Phoenix, Arizona, United States
• AR92: Pascal André , Jean-Claude Royer, Optimizing method search with lookup caches and incremental coloring, conference proceedings on Object-oriented programming systems, languages, and applications, p.110-126, October 18-22, 1992, Vancouver, British Columbia, Canada
• BDG+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]
• BKK+86: Daniel G. Bobrow , Kenneth Kahn , Gregor Kiczales , Larry Masinter , Mark Stefik , Frank Zdybel, CommonLoops: merging Lisp and object-oriented programming, Conference proceedings on Object-oriented programming systems, languages and applications, p.17-29, September 29-October 02, 1986, Portland, Oregon, United States
• Cha92: 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
• CU90: Craig Chambers and David Ungar. Iterative type analysis and extended message splitting. In Proc. SIGPLAN 90, volume 23, pages 27-34, 1990.
• CU91: 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
• 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
• Deu83: L. Peter Deutsch. Smalltalk-80: Bits of History and Works of Advice, chapter The Dorado Smalltalk-80 Implementation: Hardware Architecture. Addison Wesley, 1983.
• DMPM89: R. Dixon , T. McKee , M. Vaughan , P. Schweizer, A fast method dispatcher for compiled languages with multiple inheritance, Conference proceedings on Object-oriented programming systems, languages and applications, p.211-214, October 02-06, 1989, New Orleans, Louisiana, 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]
• CR83: 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
• Ing86: Daniel H. H. Ingalls, A simple technique for handling multiple polymorphism, Conference proceedings on Object-oriented programming systems, languages and applications, p.347-349, September 29-October 02, 1986, Portland, Oregon, United States
• KR90: Gregor Kiczales and Luis Rodrigrez. Efficient method dispatch in PCL. In Proc. ACM POPL, 1990.
• Mey92: Bertrand Meyer, Eiffel: the language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• MHH91: 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
• REJZ88: 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
• 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
• SO91: Heinz W. Schmidt and Stephen Omohundro. Clos. Eiffel, and Sather: A comparison. Technical Report TR-91-047, International Computer Science Institute, Berkeley, CA, 1991.
• Str86: Bjarne Stroustrup, The C++ programming language, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• Ung86: David Michael Ungar, The design and evaluation of a high performance Smalltalk system, MIT Press, Cambridge, MA, 1987
• UP83: David Ungar and David Patterson. Smalltalk-80: Bits of History and Words of Advice, chapter Berkeley Smalltalk: Who Knows Where the Time Goes? Addison Wesley, 1983.
• UP87: David Ungar , David Patterson, What price Smalltalk?, Computer, v.20 n.1, p.67-74, Jan. 1987 [doi>10.1109/MC.1987.1663359]
• USCH92: David Ungar , Randall B. Smith , Craig Chambers , Urs Hölzle, Object, Message, and Performance: How they Coexist in Self, Computer, v.25 n.10, p.53-64, October 1992 [doi>10.1109/2.161280]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Algorithms, Theory