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
v · d · e

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.^[1]
• 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 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. 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:

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

See also

• Visitor pattern
• Multiple dispatch
• Virtual table

References

1. ^ More Effective C++ by Scott Meyers(Addison-Wesley, 1996)

External links

• Double dispatch in java and an example