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

article

Free access

Minimizing row displacement dispatch tables

Authors:

Urs HölzleAuthors Info & Claims

ACM SIGPLAN Notices, Volume 30, Issue 10

Pages 141 - 155

https://doi.org/10.1145/217839.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

Ducournau R(2011)Implementing statically typed object-oriented programming languagesACM Computing Surveys10.1145/1922649.192265543:3(1-48)Online publication date: 29-Apr-2011
https://dl.acm.org/doi/10.1145/1922649.1922655
Onodera TNakamura H(2006)Optimizing Smalltalk by selector code indexing can be practicalECOOP'97 — Object-Oriented Programming10.1007/BFb0053384(302-323)Online publication date: 23-May-2006
https://doi.org/10.1007/BFb0053384
Arnold MRyder B(2002)Thin GuardsProceedings of the 16th European Conference on Object-Oriented Programming10.5555/646159.680033(498-524)Online publication date: 10-Jun-2002
https://dl.acm.org/doi/10.5555/646159.680033
Show More Cited By

Index Terms

Minimizing row displacement dispatch tables

Recommendations

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

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
Type dispatch for named hierarchical types
ICFP '99: Proceedings of the fourth ACM SIGPLAN international conference on Functional programming

Type dispatch constructs are an important feature of many programming languages. Scheme has predicates for testing the runtime type of a value. Java has a class cast expression and a try statement for switching on an exception's class. Crucial to these ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

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

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.

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 October 1995

Published in SIGPLAN Volume 30, Issue 10

Check for updates

Qualifiers

Article

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

Ducournau R(2011)Implementing statically typed object-oriented programming languagesACM Computing Surveys10.1145/1922649.192265543:3(1-48)Online publication date: 29-Apr-2011
https://dl.acm.org/doi/10.1145/1922649.1922655
Onodera TNakamura H(2006)Optimizing Smalltalk by selector code indexing can be practicalECOOP'97 — Object-Oriented Programming10.1007/BFb0053384(302-323)Online publication date: 23-May-2006
https://doi.org/10.1007/BFb0053384
Arnold MRyder B(2002)Thin GuardsProceedings of the 16th European Conference on Object-Oriented Programming10.5555/646159.680033(498-524)Online publication date: 10-Jun-2002
https://dl.acm.org/doi/10.5555/646159.680033
Arnold MRyder B(2002)Thin Guards: A Simple and Effective Technique for Reducing the Penalty of Dynamic Class LoadingECOOP 2002 — Object-Oriented Programming10.1007/3-540-47993-7_21(498-524)Online publication date: 29-May-2002
https://doi.org/10.1007/3-540-47993-7_21
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
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 Issue’s Table of Contents