Double dispatch

Theories and practice of polymorphism
Double dispatch Multiple dispatch Operator overloading Polymorphism in computer science Polymorphism in OOP Subtyping Virtual function Single & dynamic dispatch Parametric polymorphism

In software engineering, double dispatch is a special form of multiple dispatch, 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 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 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++, 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 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 (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" 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++, of collisions in a game:

class SpaceShip {};
class ApolloSpacecraft : public SpaceShip {};
 
class Asteroid {
public:
  virtual void CollideWith(SpaceShip&) {
    cout << "Asteroid hit a SpaceShip" << endl;
  }
  virtual void CollideWith(ApolloSpacecraft&) {
    cout << "Asteroid hit an ApolloSpacecraft" << endl;
  }
};
 
class ExplodingAsteroid : public Asteroid {
public:
  virtual void CollideWith(SpaceShip&) {
    cout << "ExplodingAsteroid hit a SpaceShip" << endl;
  }
  virtual void CollideWith(ApolloSpacecraft&) {
    cout << "ExplodingAsteroid hit an ApolloSpacecraft" << endl;
  }
};

If you have

Asteroid theAsteroid;
SpaceShip theSpaceShip;
ApolloSpacecraft theApolloSpacecraft;

then, because of function overloading,

theAsteroid.CollideWith(theSpaceShip); 
theAsteroid.CollideWith(theApolloSpacecraft);

will print Asteroid hit a SpaceShip and Asteroid hit an ApolloSpacecraft respectively, without using any dynamic dispatch. Furthermore

ExplodingAsteroid theExplodingAsteroid;
theExplodingAsteroid.CollideWith(theSpaceShip); 
theExplodingAsteroid.CollideWith(theApolloSpacecraft);

will print ExplodingAsteroid hit a SpaceShip and ExplodingAsteroid hit an ApolloSpacecraft respectively, again without dynamic dispatch.

With a reference to an Asteroid, dynamic dispatch is used and

Asteroid& theAsteroidReference = theExplodingAsteroid;
theAsteroidReference.CollideWith(theSpaceShip); 
theAsteroidReference.CollideWith(theApolloSpacecraft);

prints ExplodingAsteroid hit a SpaceShip and ExplodingAsteroid hit an ApolloSpacecraft, again as expected. However,

SpaceShip& theSpaceShipReference = theApolloSpacecraft;
//note the type of the pointer and the type of the object.
theAsteroid.CollideWith(theSpaceShipReference);
theAsteroidReference.CollideWith(theSpaceShipReference);

The desired behaviour is to bind these calls to the function that takes theApolloSpacecraft as its argument, as that is the instantiated type of the variable, meaning the expected output would be Asteroid hit an ApolloSpacecraft and ExplodingAsteroid hit an ApolloSpacecraft, but the output is actually Asteroid hit a SpaceShip and ExplodingAsteroid hit a SpaceShip. 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. Suppose SpaceShip and ApolloSpacecraft 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 = theApolloSpacecraft;
Asteroid& theAsteroidReference = theExplodingAsteroid;
theSpaceShipReference.CollideWith(theAsteroid);
theSpaceShipReference.CollideWith(theAsteroidReference);

It prints out Asteroid hit an ApolloSpacecraft and ExplodingAsteroid hit an ApolloSpacecraft, as expected. The key is that theSpaceShipReference.CollideWith(theAsteroidReference); does the following at run time:

1. theSpaceShipReference is a reference, so C++ looks up the correct method in the vtable. In this case, it will call ApolloSpacecraft::CollideWith(Asteroid&).
2. Within ApolloSpacecraft::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(ApolloSpacecraft&) will be called.

See also

• Visitor pattern
• Multiple dispatch
• Virtual table

External links

• Double dispatch in java and an example