Fast algorithms for compressed multimethod dispatch table generation
- 1 January 1998
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
- Vol. 20 (1), 116-165
- https://doi.org/10.1145/271510.271521
Abstract
The efficiency of dynamic dispatch is a major impediment to the adoption of multimethods in object-oriented languages. In this article, we propose a simple multimethod dispatch scheme based on compressed dispatch tables. This scheme is applicable to any object-oriented language using a method precedence order that satisfies a specific monotonous property (e.g., as Cecil and Dylan) and guarantees that dynamic dispatch is performed in constant time, the latter being a major requirement for some languages and applications. We provide efficient algorithms to build the dispatch tables, provide their worst-case complexity, and demonstrate the effectiveness of our scheme by real measurements performed on two large object-oriented applications. Finally, we provide a detailed comparison of our technique with other existing techniques.Keywords
This publication has 27 references indexed in Scilit:
- Fast and compact dispatching for dynamic object-oriented languagesInformation Processing Letters, 1997
- Reconciling responsiveness with performance in pure object-oriented languagesACM Transactions on Programming Languages and Systems, 1996
- Type-safe relaxing of schema consistency rules for flexible modelling in OODBMSThe VLDB Journal, 1996
- Typechecking and modules for multimethodsACM Transactions on Programming Languages and Systems, 1995
- Selector table indexing & sparse arraysPublished by Association for Computing Machinery (ACM) ,1993
- Static type checking of multi-methodsPublished by Association for Computing Machinery (ACM) ,1991
- Common Lisp Object System specificationACM SIGPLAN Notices, 1988
- CommonLoops: merging Lisp and object-oriented programmingPublished by Association for Computing Machinery (ACM) ,1986
- Optimization of parser tables for portable compilersACM Transactions on Programming Languages and Systems, 1984
- Efficient implementation of the smalltalk-80 systemPublished by Association for Computing Machinery (ACM) ,1984