Dynamic Dispatch in Object Oriented Languages

A C++ subclass B of a class A overrides a method f.

A B instance is created with new, but the pointer is assigned to an A pointer variable:

class A {                       class B: public A {

public:                         public:

   virtual void f();               virtual void f();

   ...                          ...

};                              };

 

 

int main()

{

   A *pa = new B();

 

   pa->f();

   ...

}

Question: To which implementation is the call to f() bound? The one in class A or the one in class B?

Answer:

 

Class B's f.

 

Dynamic Dispatch means that the binding of the method is determined at run time depending on the type of the object pointed to by pa.

Static Dispatch in C++

C++ doesn't always use dynamic dispatch:

int main()

{

  A a; // An A instance is created on the stack

  B b; // A B instance, also on the stack

 

  a = b;  // Only the A part of 'b' is copied into a.

 

  a.f();  // Static dispatch. This determines the binding

          // of f to A's f and this is done at compile time.

 

The binding of f is done statically; that is, at compile time based on the declared type of the variable a.

Recalling a previous lecture discussion of 'value' types versus 'reference' types, the situation in C++ is:

When does C++ use Dynamic Dispatch

 

        Value or              f virtual     Static or

Type    Reference?  Call      in A?         Dynamic Dispatch?

--------------------------------------------------------------

A a    Value        a.f()     virtual         static

A a    Value        a.f()     not virtual     static

A *pa  reference   pa->f()    virtual         dynamic

A *pa  reference   pa->f()    not virtual     static

 

Variables of value types are represented by memory to hold an actual value.

Variables of reference type are represented by memory to hold an address of a value.

Dynamic Dispatch in Java

All class types are reference types in Java:

 

        Value or              f final     Static or

Type    Reference?  Call      in A?       Dynamic Dispatch?

--------------------------------------------------------------

A a    Reference    a.f()     final         static

A a    Reference    a.f()     not final     dynamic

 

That is, the default in Java is that methods are bound dynamically according to the type of the object referenced at run time, but if the method is declared final, the binding is static.

The default in C++ is that methods are bound statically according to the declared type of any class pointer variable, but if the method is declared virtual, then binding is dynamic.

For value types in C++ (including all non-pointer class variables), static binding is always used regardless of whether the method is declared virtual or not.

Implementation of Dynamic Dispatch in OO Programming Languages

This sketch will use C++ as an example, but the concepts apply equally as well to Java.

Consider the following two classes:

class A                    class B : public A

{                          {

public:                    public:

   virtual void f();          virtual void f();

   virtual void g();          virtual void k();

   void h();               };

};

All the instances of class A will share the class A's Virtual Function Table. This table contains the beginning addresses of the code for each of the virtual functions of a class (declared directly in the class or inherited).

Virtual Function Tables for class A and class B

 

Class A's vtable                 Class B's vtable

  +-----------+                    +-----------+

0 |   A::f    |                  0 |   B::f    |

  +-----------+                    +-----------+

1 |   A::g    |                  1 |   A::g    |

  +-----------+                    +-----------+

                                 2 |   B::k    |

                                   +-----------+

Compiler Code for Calling Virtual Methods

Although dynamic dispatch means that the method called will be determined by the run time, the compiler must still generate code that when executed at run time will determine the correct method implementation based on the run time type of the object.

Each instance of class A will contain in addition to its data members, a pointer to class A's vtable. This pointer will be referred to as 'vptr' for this sketch. Similarly each instance of the subclass B will contain 'vptr' in the same offset location, but it will point to B's vtable.

Example 1

The run time object is an instance of the base class.

Example 1:

 

A *pa;

 

pa = new A();

pa->f();

 

Compler generated code:

 

pa->vptr[0]();      // 0 is because f is at that index

                    // 1 would be used for g

 

         A instance               A's vtable

pa ---> +--------+              +-----------+

        | vptr --|----------> 0 |   A::f    |

        |------- |              +-----------+

        | rest   |            1 |   A::g    |

        | of     |              +-----------+

        | A's    |

        | data   |

        | members|

        +--------+

Example 2

The run time object is an instance of the subclass. Note that the code generated is the same, but since the vptr in the object points to a different vtable, this code looks up a different implementation of f at run time than Example 1.

Example 1:

 

A *pa;

 

pa = new B();

pa->f();

 

Compler generated code:

 

pa->vptr[0]();      // 0 is because f is at that index

                    // 1 would be used for g

 

         B instance               B's vtable

pa ---> +--------+              +-----------+

        | vptr --|----------> 0 |   B::f    |

        |------- |              +-----------+

        | rest   |            1 |   A::g    |

        | of     |              +-----------+

        | B's    |            2 |   B::k    |

        | data   |              +-----------+

        | members|

        +--------+

A Java Example

There are three classes: A, B, and C plus a test class.

Here is the A class

class A

{

  public void f()

  {

    System.out.println("A::f calls g() [ which one? A::g or B::g or C::g]");

    this.g();

  }

 

  public void g()

  {

    System.out.println("A::g()");

  }

 

}

Class B

 

class B extends A

{

  public void f()

  {

    System.out.println("B::f calls super.f() (B |> A)");

    super.f();

  }

  public void g()

  {

    System.out.println("B::g()");

  }

}

Class C and the test class

 

class C extends B

{

  public void f()

  {

    System.out.println("C::f calls super.f() (C |> B |> A)");

    super.f();

  }

 

  public void g()

  {

    System.out.println("C::g()");

  }

 

}

 

public class test

{

 

  public static void main(String[] args)

  {

    A a = new C();

 

    a.f();

  }

}

Output

C::f calls super.f() (C |> B |> A)

B::f calls super.f() (B |> A)

A::f calls g() [ which one? A::g or B::g or C::g]

C::g()

Notes:

 

For a call to super.f() in class C, the compiler will use the

vtable of the super class of C (that is, B's vtable) to look up the

implementation to use for f.

 

This implementation of the meaning of super

can be stated as saying the "search" for method f begins not in

class C but in C's super class, B.

 

Note however, that the run time object hasn't

changed its class. It is still the same C object.

 

So when the f() in A finally executes and calls

this.g(), this still references the original C

object. That C object's vptr will point to C's vtable. So the

implementation of dynamic dispatch will mean that C's implementation

of g will be called, as can be seen by the output above.

 

Shallow versus Deep Copying and Cloning

Another subtle difference between C++ and Java arises from the fact that C++ has object value types as well as object reference (pointer) types, while Java only has object reference types.

C++

void f(const A& x)

{

  A a; // creates an A object on the stack

 

  a = x; // A copy of x is stored in a

         // and a can now be modified

         // without changing x

}

 

Java 

void f(A x)

{

  A a; // No A object created and 'a' does not

       // reference any A object yet

 

  a = x;  // No copy is made of the A object

          // referenced by x. Both a and x now

          // reference the same A object.

}       

Cloning

Since Java only uses references for object types, to make a distinct copy of an object requires using a method instead of simple assignment.

The Object class contains the 'clone' method which makes a shallow copy:

Java

void f(A x)

{

  A a;

 

  a = x.clone();

  // a == x is false; a and x are not identical

  // but (usually)

  //        a.getClass() == b.getClass() is true

  // and    a.equals(x) is true

}

Shallow Copy

A shallow copy of a object just makes 'copies' of the data members of the object.

If the data member is a value type (int, boolean, etc.) a copy is made of the value, but if the data member is a reference type (any class type) a copy is made only of the reference, not of the referenced object.

So if a class contains only value types, then a shallow copy of an object of this class type actually makes a complete separate copy and modifying the the original or the copy has no effect on the other object. The new copy is not an alias for the original object.

Another case where shallow copy prevents changes in either object from affecting the other object is if the class contains only value types and immutable types. For example, the objects of the String class or the Integer class are immutable - once created the object cannot be modified.

Shallow Copying Objects with Mutable Data Members

If a class has mutable object data members, then shallow copying will imply sharing of such members. So changes to a mutable data member of one object will be observed as changes to the (shared) mutable data member of a cloned object.

Remarks on Object Allocation/Deallocation in C++ versus Java

As noted already ...

All objects are allocated in heap storage in Java (with new).

In C++ objects can be allocated on the heap using new as well, but also on the stack by declaring a variable of object value type (instead of a pointer/reference to an object).

The style of writing functions that return objects in C++ or Java is different, but the difference also includes the fact that:

Java uses garbage collection to deallocate heap storage, and C++ does not.

Example

Problem:

 

Write a function, add(pr1, pr2), that takes two "pairs" of

integers and returns a new pair calculated like this:

 

If pr1 is the pair (1,3) and pr2 is the pair (10,20) then

 

        pr3 = add (pr1, pr2)

 

should assign pr3 the value (11,23).

   

Assume a class definition like this:

C++                 Java

class Pair                         class Pair

{                                  {

public:                              public int x;

  int x;                             public int y;

  int y;                             public Pair(int xval, int yval)

  Pair(int xval, int yval)           {

  {                                    x = xval;

    x = xval;                          y = yval;

    y = yval;                        }

  }                                }

};

Solutions

C++

Pair add(const Pair& pr1, const Pair& pr2)

{

  Pair result(0,0);

 

  result.x = pr1.x + pr2.x;

  result.y = pr1.y + pr2.y;

 

  return result;  // Storage for result is about to be

                  // deallocated!

}

 

Java

 

Pair add(Pair pr1, Pair pr2)

{

  Pair result;

 

  result = new Pair( pr1.x + pr2.x, pr1.y + pr2.y);

 

  return result;  // Not deallocated until the garbage

                  // collector notices there are no

                  // more references.

}

Comments

If the Java solution was used in C++ (i.e, allocate the result on the heap and then return it), garbage can be created. But unlike Java, this will create a memory leak since C++ has no garbage collector and the storage for the returned value will likely never be explicitly deallocated.