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. The virtual keyword in C++ is used to indicate that a method is intended to be overridden in a subclass.

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, the runtime type of the object receiving the method call and the static type of the method's parameters determine 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. This is an example of method overloading, since a version of method1 is added to class B in addition to the version inherited from class A.

Multiple Dispatch

For languages such as CLOS (Common Lisp Object System) that support multiple dispatch (also known as multimethods), a dispatched method is determined not just by the runtime time of the object on which the method is called, but also 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.

Despite its flexibility, there are downsides to using multiple dispatch. Since many methods take several parameters, looking up alternate versions of a method that correspond to the dynamic runtime type of all of its parameters can be costly. Furthermore, definitions for every combination of parameter types would have to be written, increasing code size considerably.

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 [2]. A 4 byte pointer to the VMT table is also stored as part of the 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.

Conclusion

Through the use of dynamic dispatch, programs can be more flexible and and extensible. They can have more dynamic behavior tuned to more specialized subclasses. However, there is time overhead for each dynamic method dispatch since additional lookups must be performed to determined the specific implementation of a method for a dynamic object type. This also creates a security issue, since potential errors that come about from using a dynamic object type cannot be caught at compile time. Furthermore, there is memory overhead since pointers to different versions of methods for subclasses must be maintained within the program memory.

References

[1] S. Milton, H.W. Schmidt, “Dynamic Dispatch in Object-Oriented Languages”, CSIRO -- Division of Information Technology, 1994.

[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.