Does anyone know of an efficient implementation of Multiple Dispatch, comparable to Smalltalk's Inline Caching of messages or C++'s vtbl mechanism? What is the best one can do for the common or average case?
The naive implementation is to have a list of class-method pairs to be searched. The same caching strategy as in Smalltalk can be used: store the class(es) of the last dispatch and the selected method next to the call site, and compare these with the classes of the arguments the next time this particular form is called. If they are equal, use the cached method.
If you only need Double Dispatch you can implement it using the Gang Of Four Visitor Pattern.
Andrei Alexandrescu's book on Modern Cee Plus Plus Design contains a chapter titled "Multimethods" that discusses several schemes to implement Double Dispatch in standard Cee Plus Plus.
Several years ago, I did the multimethod implementation for a constraint language called Kaleidescope. The strategy we used was to create a Finite State Machine for each method name. The arcs contained the possible function parameters, and we used the parameter list from the method we were trying to call as input for walking through the fsm. So, for example, let's say you have defined the following methods:
f(x), f(x, y), f(x, x, y) and f(z)
where x, y and z are types of arguments, then the fsm looks like this:
initial state: on x goto 1 on z return f(z) on end-of-input or anything else return error
state 1: on end-of-input return f(x) on x goto 2 on y return f(x, y) on anything else return error
state 2: on y return f(x, x, y) on end-of-input or anything else return error
So suppose you are trying to resolve a call to f(x, y). You start in the initial state and read an x (the first parameter to the function call). The FSM tells you to go to state 1. In state 1, you read a y. The FSM tells you that the function you want is f(x, y), and it actually returns the compiled method to you. Tada!
It's not too efficient compared with, say, Smalltalk method dispatch, but then again it's not too bad either. The analysis we did showed that there was in practice not too much variation amongst the methods, so we could get some compression on the FSMs. Also, the most heavily overloaded methods tended to be the arithmetic ones (eg +, -, *, **), and they only had two arguments, which means that this isn't much traversal to begin with. -- Anthony Lander
Does the FSM technique work if actual method arguments can be subtypes of declared method arguments? I'm not convinced.
Sure. Put all of the subtypes into the fsm.
In the case of single inheritance, there's a simple implementation technique that will allow you to compute the IS-A predicate in constant time. (I.e. it allows you, in constant time, to check if an object is an instance of a class or one of its subclasses.)
To do this, we associate a unique identifier with every class. Now suppose we have a root class P with subclasses C1 and C2, while C2 itself has a subclass G. In every instance, instead of storing a pointer to a method table, we store a pointer to an array of class identifiers.
For an instance of P, this array has one element:
+--+ |P | +--+
For an instance of C1, this array has two elements:
+--+--+ |P |C1| +--+--+
For an instance of G, this array has three elements:
+--+--+--+ |P |C2|G | +--+--+--+
Now to check if an object is an instance of, say, C2, do the following:
Check if the array has at least 2 elements.
Check if the second element is C2.
Obviously, this takes only constant time.
I use a similar technique in Tree In Sql. It is time-optimal for lookups. -- Richard Henderson
This technique uses up to quadratic space (if the class hierarchy is deep.) You can get by with linear space by assigning preorder and postorder numbers to the classes in the hierarchy. Class A is a superclass of class B iff pre(A) is less than pre(B) and post(A) is greater than post(B). -- Paul Dietz
[However, the preorder/postorder trick has one flaw--it assumes a closed system of classes (in other words, all classes are known at a particular time). In systems where modules are combined at runtime--especially under the control of the program itself rather than under the control of a language runtime--this constraint is violated.
And of course, it also doesn't work in the case of Multiple Inheritance]
I believe the alleged flaw of the preorder/postorder trick isn't a flaw, and the alleged fixed class hierarchy constraint isn't a constraint. Paul Dietz turns out to be one author of a paper giving an algorithm to maintain an order as new elements are inserted arbitrarily. As I understand it (not having read the original paper yet) that paper uses this trick as an example of what the order algorithm is good for. The paper is behind the ACM wall, but see Bender et al., Two Simplified Algorithms for Maintaining Order in a List, citeseer.ist.psu.edu 
, for a more recent treatment. (Their Final Thought:
Dietz and Sleator is quite influential with its tags and its proofs by potential but to teach it in class is a pain in the emdash so our new result is preferential.
) -- William Newman
The best implementation paper I know of is from the Cecil/Vortex project (see Cecil Language) at www.cs.washington.edu . It is effectively an FSM, with the transitions between states done by an array look-up, linear search or binary search; it aims for a near-optimal combination.
Also check out this paper:
citeseer.nj.nec.com
It provides an algorithm using compressed dispatch tables that dispatches in constant time. The tables themselves are created in O(n^2) time, but I believe that's a compile-time cost only.
See original on c2.com