Software Engineering is the application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software, and the study of these approaches; that is, the application of engineering to software...
Multiple dispatch or multimethods or function overloading is the feature of some object-oriented programming languages in which a function or method can be dynamically dispatched based on the run time type of more than one of its arguments...
, and a mechanism that dispatches a function call to different concrete functions depending on the runtime types of two objects involved in the call. In most object-oriented systems, the concrete function that is called from a function call in the code depends on the dynamic type of a single object and therefore they are known as single dispatch calls, or simply virtual function
Virtual function
In object-oriented programming, a virtual function or virtual method is a function or method whose behaviour can be overridden within an inheriting class by a function with the same signature...
calls.
Examples
Double dispatch is useful in situations where the choice of computation depends on the runtime types of its arguments. For example, a programmer could use double dispatch in the following situations:
Adaptive collision algorithms usually require that collisions between different objects be handled in different ways. A typical example is in a game environment where the collision between a spaceship and an asteroid is computed differently than the collision between a spaceship and a spacestation.
Painting algorithms that require the intersection points of overlapping sprites
Sprite (computer graphics)
In computer graphics, a sprite is a two-dimensional image or animation that is integrated into a larger scene...
be rendered in a different manner.
Personnel management systems may dispatch different types of jobs to different personnel. A schedule algorithm that is given a person object typed as an accountant and a job object typed as engineering rejects the scheduling of that person for that job.
Event handling systems that use both the event type and the type of the receptor object in order to call the correct event handling routine.
A common idiom
The common idiom in the examples presented above, is that the selection of the appropriate algorithm is based on the call's argument types at runtime. The call is therefore subject to all the usual additional performance costs that are associated with dynamic resolution of calls, usually more than in a language supporting only single method dispatch. In C++
C++
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
, for example, a dynamic function call is usually resolved by a single offset calculation - which is possible because the compiler knows the location of the function in the object's method table
Virtual method table
A virtual method table, virtual function table, dispatch table, or vtable, is a mechanism used in a programming language to support dynamic dispatch ....
and so can statically calculate the offset. In a language supporting double dispatch, this is slightly more costly, because the compiler must generate code to calculate the method's offset in the method table at runtime, thereby increasing the overall instruction path length
Instruction path length
In computer performance, the instruction path length is the number of machine code instructions required to execute a section of a computer program. The total path length for the entire program could be deemed a measure of the algorithm's performance on a particular computer hardware...
(by an amount that is likely to be no more than the total number of calls to the function, which may not be very significant).
Double dispatch is more than function overloading
At first glance, double dispatch appears to be a natural result of function overloading. Function overloading allows the function called to depend on the type of the argument. Function overloading however is done at compile time using "name mangling"
Name mangling
In compiler construction, name mangling is a technique used to solve various problems caused by the need to resolve unique names for programming entities in many modern programming languages....
where the internal name of the function has the argument's type encoded in it. So for example function foo(int) would internally be called "__foo_i" and function foo would be called "__foo_v" ("v" for void). So there is no runtime overhead because there is no name collision and calling an overloaded function goes through at most one virtual table just like any other function. Dynamic dispatch is only based on the type of the calling object. Consider the following example, written in C++
C++
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
, of collisions in a game:
class SpaceShip {};
class GiantSpaceShip : public SpaceShip {};
class Asteroid {
public:
virtual void CollideWith(SpaceShip&) {
cout << "Asteroid hit a SpaceShip" << endl;
}
virtual void CollideWith(GiantSpaceShip&) {
cout << "Asteroid hit a GiantSpaceShip" << endl;
}
};
class ExplodingAsteroid : public Asteroid {
public:
virtual void CollideWith(SpaceShip&) {
cout << "ExplodingAsteroid hit a SpaceShip" << endl;
}
virtual void CollideWith(GiantSpaceShip&) {
cout << "ExplodingAsteroid hit a GiantSpaceShip" << endl;
}
};
If you have
Asteroid theAsteroid;
SpaceShip theSpaceShip;
GiantSpaceShip theGiantSpaceShip;
then, because of function overloading,
theAsteroid.CollideWith(theSpaceShip);
theAsteroid.CollideWith(theGiantSpaceShip);
will print Asteroid hit a SpaceShip and Asteroid hit a GiantSpaceShip respectively, without using any dynamic dispatch. Furthermore
ExplodingAsteroid theExplodingAsteroid;
theExplodingAsteroid.CollideWith(theSpaceShip);
theExplodingAsteroid.CollideWith(theGiantSpaceShip);
will print ExplodingAsteroid hit a SpaceShip and ExplodingAsteroid hit a GiantSpaceShip respectively, again without dynamic dispatch.
With a reference to an Asteroid, dynamic dispatch is used and
Asteroid& theAsteroidReference = theExplodingAsteroid;
theAsteroidReference.CollideWith(theSpaceShip);
theAsteroidReference.CollideWith(theGiantSpaceShip);
prints ExplodingAsteroid hit a SpaceShip and ExplodingAsteroid hit a GiantSpaceShip, again as expected. However,
SpaceShip& theSpaceShipReference = theGiantSpaceShip;
theAsteroid.CollideWith(theSpaceShipReference);
theAsteroidReference.CollideWith(theSpaceShipReference);
prints Asteroid hit a SpaceShip and ExplodingAsteroid hit a SpaceShip, neither of which is correct. The problem is that, while virtual functions are dispatched dynamically in C++, function overloading is done statically.
Double dispatch in C++
The problem described above can be resolved by simulating double dispatch, for example by using a visitor pattern
Visitor pattern
In object-oriented programming and software engineering, the visitor design pattern is a way of separating an algorithm from an object structure on which it operates. A practical result of this separation is the ability to add new operations to existing object structures without modifying those...
. Suppose SpaceShip and GiantSpaceShip both have the function
virtual void CollideWith(Asteroid& inAsteroid) {
inAsteroid.CollideWith(*this);
}
Then, while the previous example still does not work correctly, the following does:
SpaceShip& theSpaceShipReference = theGiantSpaceShip;
Asteroid& theAsteroidReference = theExplodingAsteroid;
theSpaceShipReference.CollideWith(theAsteroid);
theSpaceShipReference.CollideWith(theAsteroidReference);
It prints out Asteroid hit a GiantSpaceShip and ExplodingAsteroid hit a GiantSpaceShip, as expected. The key is that theSpaceShipReference.CollideWith(theAsteroidReference); does the following at run time:
theSpaceShipReference is a reference, so C++ looks up the correct method in the vtable. In this case, it will call GiantSpaceShip::CollideWith(Asteroid&).
Within GiantSpaceShip::CollideWith(Asteroid&), inAsteroid is a reference, so inAsteroid.CollideWith(*this) will result in another vtable lookup. In this case, inAsteroid is a reference to an ExplodingAsteroid so ExplodingAsteroid::CollideWith(GiantSpaceShip&) will be called.
