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.

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.