More Web Proxy on the site http://driver.im/

Article

Free access

Minimizing row displacement dispatch tables

Authors:

Urs HölzleAuthors Info & Claims

OOPSLA '95: Proceedings of the tenth annual conference on Object-oriented programming systems, languages, and applications

Pages 141 - 155

https://doi.org/10.1145/217838.217851

Published: 17 October 1995 Publication History

Abstract

Row displacement dispatch tables implement message dispatching for dynamically-typed languages with a run time overhead of one memory indirection plus an equality test. The technique is similar to virtual function table lookup, which is, however, restricted to statically typed languages like C++. We show how to reduce the space requirements of dispatch tables to approximately the same size as virtual function tables. The scheme is then generalized for multiple inheritance. Experiments on a number of class libraries from five different languages demonstrate that the technique is effective for a broad range of programs. Finally, we discuss optimizations of the row displacement algorithm that allow dispatch table construction of these large samples to take place in a few seconds.

References

[1]

Eric Amiel, Olivier Gruber, and Eric Simon. Optimizing Multi-Method Dispatch Using Compressed Dispatch Tables. In OOPSLA '94 Conference Proceedings, pp. 244-258, October 1994.

Digital Library

[2]

A.V.Aho, J.E.Hopcroft, J.D.Ullman. Data Structures andAIgorithms. Addison-Wesley 1983.

Digital Library

[3]

P. Andr6 and J.-C. Royer. Optimizing Method Search with Lookup Caches and Incremental Coloring. OOPSLA '92 Conference Proceedings, Vancouver, Canada, October 1992.

Digital Library

[4]

Brad Calder and Dirk Grunwald. Reducing Indirect Function Call Overhead in C++ Programs. In 21st Annual A CM Symposium on Principles of Programming Languages, p. 397-408, January 1994.

Digital Library

[5]

Craig Chambers, David Ungar, and Elgin Lee. An Efficient Implementation of SELF, a Dynamically-Typed Object-Oriented Language Based on Prototypes. In OOPSLA '89 Conference Proceedings, p. 49-70, New Orleans, LA, October 1989.

Digital Library

[6]

Craig Chambers, David Ungar, Bay-Wei Chang, and Urs H61zle. Parents are Shared Parts: Inheritance and Encapsulation in SELF. Lisp and Symbolic Computation 4(3), Kluwer Academic Publishers, June 1991.

Digital Library

[7]

T. Conroy and E. Pelegri-Llopart. An Assessment of Method-Lookup Caches for Smalltalk-80 Implementations. In {GR83}.

[8]

O.-J. Dahl and B. Myrhaug. Simula Implementation Guide. Publ. S 47, NCC, March 1973.

[9]

P. Dencker, K. Dtirre, and J. Heuft. Optimization of Parser Tables for Portable Compilers. TOPLAS 6(4):546- 572, 1984.

Digital Library

[10]

L. Peter Deutsch and Alan Schiffman. Efficient Implementation of the Smalltalk-80 System. Proceedings of the llth Symposium on the Principles of Programming Languages, Salt Lake City, UT, 1984.

Digital Library

[11]

R. Dixon, T. McKee, P. Schweitzer, and M. Vaughan. A Fast Method Dispatcher for Compiled Languages with Multiple Inheritance. OOPSLA '89 Conference Proceedings, pp. 211-214, New Orleans, LA, October 1989.

Digital Library

[12]

Karel Driesen. Selector Table Indexing and Sparse Arrays. OOPSLA '93 Conference Proceedings, p. 259- 270, Washington, D.C., 1993.

Digital Library

[13]

Karel Driesen. Method Lookup Strategies in Dynamically Typed Object-Oriented Programming Languages. Master's Thesis, Vrije Universiteit Brussel, 1993.

[14]

Karel Driesen. Compressing Sparse Tables using a Genetic Algorithm. In Proceedings of the GRONICS '94 Student Conference, Groningen, February I994.

[15]

Karel Driesen, Urs H01zle, Jan Vitek. Message Dispatch on Modern Computer Architectures. ECOOP '95 Conference Proceedings,~rhus, Denmark, August 1995.

Digital Library

[16]

P. Dussud. TICLOS: An implementation of CLOS for the Explorer Family. OOPSLA '89 Conference Proceedings, pp. 215-220, New Orleans, LA, October 1989.

Digital Library

[17]

Margaret A. Ellis and Bjarne Stroustrup. The Annotated C++ Reference Manual. Addison-Wesley, Reading, MA, 1990.

Digital Library

[18]

Adele Goldberg and David Robson. SmalItalk-80: The Language and its Implementation. Second Edition, Addison-Wesley, Reading, MA, 1985.

Digital Library

[19]

Shih-Kun Huang, Deng-Jyi Chen. Two-way Coloring Approaches for Method Dispatching in Object-Oriented Programming Systems. Proceedings of the Sixteenth Annual International Computer Software and Applications Conference, pp. 39-44, Chicago, 1992.

[20]

Urs HOlzle, Craig Chambers, and David Ungar. Optimizing Dynamically-Typed Object-Oriented Languages with Polymorphic Inline Caches. In ECOOP "91 Conference Proceedings, Geneva, 1991.

Digital Library

[21]

Urs H61zle and David Ungar. Optimizing dynamicallydispatched calls with run-time type feedback. In PLDI "94 Conference Proceedings, pp. 326-335, Orlando, FL, June 1994.

[22]

Ralph Johnson. Workshop on Compiling and Optimizing Object-Oriented Programming Languages. OOPSLA '87 Addendum to the Proceedings, 1988.

Digital Library

[23]

Gregor Kiczales and Louis Rodriguez. Efficient Method Dispatch in PCL. Proc. A CM Cot~ on Lisp and Functional Programming, 1990. Also in {Pae93}.

Digital Library

[24]

Glenn Krasner. Smalltalk-80: Bits of History, Words of Advice. Addison-Wesley, Reading, MA, 1983.

Digital Library

[25]

Stein Krogdahl. Multiple inheritance in Simula-like languages. BIT 25, pp. 318-326, 1985.

Digital Library

[26]

Mark Linton, John Vlissides, PauI Calder. Composing User Interfaces with Interviews. IEEE Computer 22(2), pp. 8-22, February 1989.

Digital Library

[27]

S. Milton and Heinz W. Schmidt. Dynamic Dispatch in Object-Oriented Languages. Technical Report TR-CS- 94-02, The Australian National University, Canberra, January 1994.

[28]

Andreas Paepcke (ed.). Object-Oriented Programming: The CLOS Perspective, MIT Press, 1993.

Digital Library

[29]

John Rose. Fast Dispatch Mechanisms for Stock Hardware. OOPSLA '88 Conference Proceedings, p. 27-35, San Diego, CA, November 1988.

Digital Library

[30]

R.E.Tarjan, A.C.Yao. Storing a Sparse Table. Communications of the ACM, 22(11), November 1979, pp. 606- 611.

Digital Library

[31]

Kresten Krab Thorup. Optimizing Method Lookup in Dynamic Object-Oriented Languages with Sparse Arrays. Proceedings of the Annual SUUG Conference on Free Software 1993, Moscow, Russia 1993.

[32]

David Ungar and David Patterson. What Price Smalltalk? In IEEE Computer 20(1), January 1987.

Digital Library

[33]

Jan Vitek and R. N. Horspool. Taming Message Passing: Efficient Method Look-Up for Dynamically-Typed Languages. In ECOOP '94 Conference Proceedings, Bologna, italy, 1994.

Digital Library

[34]

Jan Vitek. Compact Dispatch Tables for Dynamically Typed Object-Oriented Languages. M.S. Thesis, University of Victoria, B.C., forthcoming

[35]

A. Weinand, E. Gamma, and R. Marty. ET++---An Object-Oriented Application Framework in C++. OOPSLA '88 Conference Proceedings, pp. 46-57, October 1988.

Digital Library

Cited By

Sonntag BColnet D(2014)Efficient compilation strategy for object-oriented languages under the closed-world assumptionSoftware—Practice & Experience10.1002/spe.217444:5(565-592)Online publication date: 1-May-2014
https://dl.acm.org/doi/10.1002/spe.2174
Harikrishnan SKumar R(2012)Space efficient non-constant time multi-method dispatch in object oriented systemsACM SIGSOFT Software Engineering Notes10.1145/2108144.210815337:2(1-6)Online publication date: 3-Apr-2012
https://dl.acm.org/doi/10.1145/2108144.2108153
Ferreira RCarro L(2012)Adaptive SoftwareAdaptable Embedded Systems10.1007/978-1-4614-1746-0_9(279-304)Online publication date: 20-Oct-2012
https://doi.org/10.1007/978-1-4614-1746-0_9
Show More Cited By

Index Terms

Minimizing row displacement dispatch tables

Recommendations

Minimizing row displacement dispatch tables

Row displacement dispatch tables implement message dispatching for dynamically-typed languages with a run time overhead of one memory indirection plus an equality test. The technique is similar to virtual function table lookup, which is, however, ...
Minimizing Row Displacement Dispatch Tables
Practical predicate dispatch
OOPSLA '04

<i>Predicate dispatch</i> is an object-oriented (OO) language mechanism for determining the method implementation to be invoked upon a message send. With predicate dispatch, each method implementation includes a predicate guard specifying the conditions ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

OOPSLA '95: Proceedings of the tenth annual conference on Object-oriented programming systems, languages, and applications

October 1995

496 pages

ISBN:0897917030

DOI:10.1145/217838

Chairman:
Robecca J. Wirfs-Brock
ParcPlace-Digitals, Inc.

ACM SIGPLAN Notices Volume 30, Issue 10
Oct. 17, 1995
493 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/217839
Editor:
Rebecca Wirfs-Brock
ParcPlace-Digitalk, Inc.
Issue’s Table of Contents

Copyright © 1995 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]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 October 1995

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

OOPSLA95

Sponsor:

SIGPLAN

OOPSLA95: Conference on Object Oriented Programming Systems Languages and Applications

October 15 - 19, 1995

Texas, Austin, USA

Acceptance Rates

Overall Acceptance Rate 268 of 1,244 submissions, 22%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
714
Total Downloads

Downloads (Last 12 months)133
Downloads (Last 6 weeks)25

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sonntag BColnet D(2014)Efficient compilation strategy for object-oriented languages under the closed-world assumptionSoftware—Practice & Experience10.1002/spe.217444:5(565-592)Online publication date: 1-May-2014
https://dl.acm.org/doi/10.1002/spe.2174
Harikrishnan SKumar R(2012)Space efficient non-constant time multi-method dispatch in object oriented systemsACM SIGSOFT Software Engineering Notes10.1145/2108144.210815337:2(1-6)Online publication date: 3-Apr-2012
https://dl.acm.org/doi/10.1145/2108144.2108153
Ferreira RCarro L(2012)Adaptive SoftwareAdaptable Embedded Systems10.1007/978-1-4614-1746-0_9(279-304)Online publication date: 20-Oct-2012
https://doi.org/10.1007/978-1-4614-1746-0_9
Ducournau R(2011)Coloring, a versatile technique for implementing object-oriented languagesSoftware—Practice & Experience10.1002/spe.102241:6(627-659)Online publication date: 1-May-2011
https://dl.acm.org/doi/10.1002/spe.1022
de Oliveira Guimarães J(2009)The Green language type systemComputer Languages, Systems and Structures10.1016/j.cl.2008.09.00135:4(435-447)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.1016/j.cl.2008.09.001
Ducournau R(2008)Perfect hashing as an almost perfect subtype testACM Transactions on Programming Languages and Systems10.1145/1391956.139196030:6(1-56)Online publication date: 30-Oct-2008
https://dl.acm.org/doi/10.1145/1391956.1391960
Bettini LCapecchi SVenneri BAmaral V(2007)Featherweight Java with multi-methodsProceedings of the 5th international symposium on Principles and practice of programming in Java10.1145/1294325.1294337(83-92)Online publication date: 5-Sep-2007
https://dl.acm.org/doi/10.1145/1294325.1294337
Gil JZibin Y(2007)Efficient dynamic dispatching with type slicingACM Transactions on Programming Languages and Systems10.1145/1290520.129052530:1(5-es)Online publication date: 1-Nov-2007
https://dl.acm.org/doi/10.1145/1290520.1290525
Bettini LCapecchi SVenneri B(2006)Double dispatch in C++Software—Practice & Experience10.5555/1133013.113301536:6(581-613)Online publication date: 1-May-2006
https://dl.acm.org/doi/10.5555/1133013.1133015
Pontelli ERanjan DGupta G(2006)The complexity of late-binding in dynamic object-oriented languagesPrinciples of Declarative Programming10.1007/BFb0056616(213-229)Online publication date: 2-Jun-2006
https://doi.org/10.1007/BFb0056616
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents