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.