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
[1]
Rakesh Agrawal, Linda G. DeMichiel. and Bruce G. Lindsay. Static type checking of multi-methods. In Proc. OOPSLA, 1991.
[2]
Pascal Andre and Jean-Claude Royer. Optimizing method search with lookup caches and incremental coloring. In Proc. OOPSLA, pages 110-126, 1992.
[3]
Daniel G. Bobrow. Linda G. DeMichiel, Richard P. Gabriel, Sonya. Keene, Gregor Kiczales, and David A. Moon. Common Lisp Object System specification. SIGPLAN Notices. 23, Sept. 1988.
[4]
Daniel G. Bobrow, Kenneth Kahn, Gregor Kiczales, Larry Masinter, Mark Stefik, and Frank Zdybel CommonLoops: Merging lisp and objectoriented programming. In Proc. OOPSLA, 1986.
[5]
Craig Chambers. Object-oriented multi-methods in Cecil. In Proc. ECOOP, 1992.
[6]
Craig Chambers and David Ungar. Iterative type analysis and extended message splitting. In Proc. SIGPLAN 90, volume 23, pages 27-34, 1990.
[7]
Craig Chambers and David Ungar. Making pure object-oriented languages practical. In Proc. OOPSLA, 1991.
[8]
Craig Chambers, David Ungar, and Elgin Lee. An efficient implementation of SELF, a dynamically typed object-oriented language based on prototypes. In Proc. OOPSLA, pages 49-70, 1989.
[9]
L. Peter Deutsch. Smalltalk-80: Bits of History and Works of Advice, chapter The Dorado Smalltalk-80 Implementation: Hardware Architecture. Addison Wesley, 1983.
[10]
R. Dixon, T. McKee, P.Schweizer, and M. Vaughan. A fast method dispatcher for complied languages with multiple inheritance. In Proc. OOPSLA, pages 211-214, 1989.
[11]
L. Peter Deutsch and Alan Schifman. Efficient implementation of the Smalltalk-80 system. In Proc. ACM POPL, 1984.
[12]
Adele Goldberg and David Robson. Smalltalk-80: The Language and Its Implementation. Addison Wesley, Reading, MA, 1983.
[13]
Urs Holzle, Craig Chambers, and David Ungar. Optimizing dynamically typed object-oriented languages using polymorphic inline caches. In Proc. ECOOP, pages 21-36, 1991.
[14]
Daniel H. H. Ingalls. A simple technique for handling multiple polymorphism. In Proc. OOPSLA, pages 347-349, 1986.
[15]
Gregor Kiczales and Luis Rodrigrez. Efficient method dispatch in PCL. In Proc. ACM POPL, 1990.
[16]
Bertrand Meyer. EIFFEL : The Lnaguage. Prentice Hall Intl., 1992.
[17]
Warwick B. Mugridge, John Hamer, and John G. Hosking Multi-methods in a statically-typed programming language. In Proc. ECOOP, 1991.
[18]
Justin O. Graver Ralp E. Johnson and Lawrence W. Zurawski. Ts: An optimizing compiler for smalltalk. In Proc. OOPSLA, pages 18-26, 1988.
[19]
John R. Rose, Fast dispatch mechanism for stock hardware. In Proc. OOPSLA, pages 27-35, 1988.
[20]
Heinz W. Schmidt and Stephen Omohundro. Clos. Eiffel, and Sather: A comparison. Technical Report TR-91-047, International Computer Science Institute, Berkeley, CA, 1991.
[21]
Bjarne Stroustrup. The C++ Programming Language. Addison-Wesley, Reading, Mass., 1986.
[22]
David Ungar. The Design and Evaluation of a High Performance Smalltalk System. MIT Press, Cambridge, MA, 1986.
[23]
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.
[24]
David Ungar and David Patterson. What price Smalltalk? IEEE Computer, 20(1), 1987.
[25]
David Ungar, Randall B. Smith, Craig Chambers, and Urs Holzle. Object, message and performance: How they coexist in SELF. IEEE Computer, October 1992.
Index Terms
- Optimizing multi-method dispatch using compressed dispatch tables
Recommendations
Optimizing multi-method dispatch using compressed dispatch tables
OOPSLA '94: Proceedings of the ninth annual conference on Object-oriented programming systems, language, and applicationsOptimizing 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 ...
An economic load dispatch and multiple environmental dispatch problem solution with microgrids using interior search algorithm
Microgrid is a novel small-scale system of the centralized electricity for a small-scale community such as villages and commercial area. Microgrid consists of micro-sources like distribution generator, solar and wind units. A microgrid is consummate ...
Solution to economic emission dispatch problem including wind farms using Exchange Market Algorithm Method
AbstractThis paper presents an Exchange Market Algorithm (stocktickerEMA) method for solving the Economic Emission Dispatch (EED) problem including wind farms in the power systems. The stocktickerEMA algorithm is a powerful and useful method ...
Highlights- Exchange Market Algorithm is used for solving the Economic Emission Dispatch.
- ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Oct. 1994
473 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/191081
- Editor:
- Richard L. Wexelblat
October 1994476 pagesISBN:0897916883DOI:10.1145/191080- Chairmen:
- Jeff McKenna,
- J. Eliot B. Moss,
- Editor:
- Richard L. Wexelblat
Copyright © 1994 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 October 1994
Published in SIGPLAN Volume 29, Issue 10
Check for updates
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations48Total Citations
- 741Total Downloads
- Downloads (Last 12 months)238
- Downloads (Last 6 weeks)36
Reflects downloads up to 26 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in