CSC/ECE 517 Fall 2010/ch5 5c IC

Dynamic Dispatch

Introduction

Dynamic dispatch is an object-oriented programming concept that refers to the mapping of a method to an object's dynamic runtime type. It is common in many object-oriented languages. Languages such as Java and C++ use single dispatch, while only a few, such as CLOS, use multiple dispatch. Both types of dispatch will be discussed later.

Advantages

• Flexibility
• Extensibility
• Reduces the effort required to change implementation [4]

Disadvantages

• Lookup overhead
• Counter to safety and increased compile-time knowledge
• Obstacle to optimization
• Hinders compiler in determining exact type of objects

Example in C++

To illustrate the use of dynamic dispatch, we have defined two classes below, A and B, and will show how their methods are inherited and how they are called based on the dynamic type of objects of types A and B.

Class A contains two public virtual methods, method1 and method2. Class B inherits from A, contains two public methods, method1 (which overrides the method defined in class A) and method3.

class A
{
public:
  virtual int method1();
  virtual void method2();
};

class B : public A
{
public:
  int method1();
  double method3();
};

The next section of code shows a basic implementation of these methods within these two classes.

class A
{
  
  virtual int method1()
  {
    cout << "method1 in class A" << endl;
  }

  virtual int method2()
  {
    cout << "method2 in class A" << endl;
  }
};

class B : public A
{
  virtual int method1()
  {
    cout << "method1 in class B" << endl;
  }

  virtual int method3()
  {
    cout << "method3 in class B" << endl;
  }
};

Since C++ supports the use of polymorphism, an object can be created with a static type of A but a dynamic type of B.

A ab = new B();

Where this presents a challenge is when a method in a subclass overrides a method in a superclass. Since the object ab is of two types, the question arises: From which class will that method be called? Due to dynamic dispatch, the method from the dynamic runtime type will be called. For example, calling method1 on the object ab will call method1 implemented in class B, the object's dynamic type.

ab.method1();

>> method1 in class B

Single Dispatch

Dynamic dispatch comes in 2 types: single and multiple dispatch. In single dispatch in the case of method overriding, only a method parameter's static type determines which method is called of the list of potential methods to call.

For example, if we modify the above example to include parameters and change the declaration of method1 in class A to

virtual int method1(A a);

and change method1 in class B to

virtual int method1(B b);

we could call method1 on our object ab in several ways; however, we will get different results based on the compile-time type of the parameters passed to method1.

A a = new A();
B b = new B();
A ab2 = new B();

// passing in an object of type A
ab.method1(a);

// passing in an object of type B
ab.method1(b);

// passing in object of compile-time type A
ab.method1(ab2);

Because object ab has a dynamic type of B, the program will first look in class B for method1. For the first example

ab.method1(a);

even though class B contains a method1, the definition for method1 in class A will be called since the method in A requires an object of type A to be passed and since object ab2 is of compile-time type A.

Multiple Dispatch

For languages such as CLOS (Common Lisp Object System) that support multiple dispatch (also known as method overloading or multimethods), a dispatched method is determined by the runtime types of parameters passed to the method.

Using the same classes as above:

A ab1 = new B();
A ab2 = new B();
ab1.method1(ab2);

Under single dispatch, the runtime type of object ab1 and the compile time type of its parameters would determine which version of method1 is called. However, under multiple dispatch, the runtime type of object ab2, which is B in this case, also determines which method is called on object ab1. Because class B contains a version of method1 that takes an object of type B and because the runtime type of object ab2 is also B, method1 from class B is called under multiple dispatch.

Virtual Method Table

The virtual method table (VMT) (also known as virtual function table (VFT) or dispatch table) is a lookup table that contains the addresses of an object's dynamically bound virtual methods. There is one dispatch table per class, so every object of a particular type share a VMT. In C++, a pointer to each method in the VMT is 4 bytes [2].

C++ is able to use a VMT because it is a strongly-typed language and can guarantee that the concrete type of an object is always a subtype of its abstract type [2].

Memory Usage

As stated in the Virtual_Method_Table section, each entry in the VMT table for C++ code is 4 bytes long. A 4 byte pointer to the VMT table is also stored as part of the class for each class. If a program, for example, has 1000 classes, each with 50 methods, there will be at most 204,000 bytes, or 0.204 MB of data stored in all the VMTs for the program. For modern machines, this is negligible, since many contains more than 1 GB of system memory.

Speed

In order to dynamically dispatch the correct method, a lookup for the correct method has to be performed at runtime to find the correct method implementation to be called for an object. The lookup must start at the bottom of the hierarchy where the dynamic type of the object resides. It must then procede up through the hierarchy until it finds a method with the correct signature. The efficiency with which a lookup is done depends upon the height of the object's inheritance hierarchy tree.

The diagram below show the inheritance hierarchy of 4 classes, and several methods defined for each. Each uppercase character represents a class while each numeral represents a method.

For example, if we created an object and called a method on it like so:

A d = new D();
d.method2();

To determine the which method would be called, the program first checks within the class of the object that is passed the message (in this case, that class is D). If it is not defined, it searches up the inheritance hierarchy until it finds an appropriate implementation of the called method. In this case, it is the implementation of method2 inherited from class A.

References

[1] “Dynamic Dispatch in Object-Oriented Languages”, 2004.

[2] M. Muller, “Message Dispatch in Dynamically-Typed Object-Oriented Languages”, Master’s Thesis, University of New Mexico, 1995.

[3] http://en.wikipedia.org/wiki/Dynamic_dispatch

[4] D. Schmidt, "Dynamic Binding C++", http://www.cs.wustl.edu/~schmidt/PDF/C++-dynamic-binding4.pdf, 2006.

[5] O. Zendra, D. Colnet, S. Collin, "Efficient Dynamic Dispatch without Virtual Function Tables: The SmallEiffel Compiler", Proceedings of the 12th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, 1997, pp. 125-141.