dynamic_cast

[Mark]

can someone explain, purely for my information, how
dynamic_cast is implemented using only C++ language
facilities.

I don't mean how to use it, rather what is going on under the
hood.

Thanks

Mark

 

[Mike Wahler]

can someone explain, purely for my information, how
dynamic_cast is implemented using only C++ language
facilities.

It's not.

I don't mean how to use it, rather what is going on under the
hood.

That's an implementation detail that can and does vary
among implementations. Since here we only discuss the
language itself, you'll need to ask about this where
your particular compiler is discussed (or perhaps
its vendor's web site).

-Mike

 

[Siemel Naran]

can someone explain, purely for my information, how
dynamic_cast is implemented using only C++ language
facilities.

I think one way to implement it is this: The virtual pointer of a class
points to the virtual table, in the virtual table is a pointer to a
std::type_info object that represents the type info for class, and there is
also a pointer to the virtual table of the parent class.

Suppose you have

Something * s = new MoreDerivedSomething();

Now when you say dynamic_cast<DerivedSomething*>(s), that system gets the
virtual pointer of 's', namely something like s.__vptr. Then check if the
type_info object pointed to in DerivedSomething is the same as the type_info
object pointed to by MoreDerivedSomething. They're not equal. So then
traverse to the virtual table of the parent class, which is the virtual
table of class DerivedSomething and repeat the test. If there is no parent
class then dynamic_cast returns NULL.

This algorithm is O(N) where N is the depth of the hierarchy. Furthermore,
comparing two type_info objects for equality may be O(M) where M is the
length of the class name including namespaces, because there may be multiple
copies of std::type_info objcets for a single class or even multiple copies
of the virtual table, so std::type_info:perator== would have to compare
class names.

This is pretty slow. I'm sure dynamic_cast is required to be a fast
operation. Is it O(1)? How might one achieve this?

 

[Siemel Naran]

That's an implementation detail that can and does vary
among implementations. Since here we only discuss the
language itself, you'll need to ask about this where
your particular compiler is discussed (or perhaps
its vendor's web site).

General topics about implementation are valid as it might shed light on the
performance hit of using a certain feature, and provide insight for better
future implementations. So one often asks about the cost of iostreams over
printf, vector over array, exceptions over returning ints, and dynamic_cast
over other designs.

 

[Jerry Coffin]

This is pretty slow. I'm sure dynamic_cast is required to be a fast

operation. Is it O(1)? How might one achieve this?

First of all, dynamic_cast usually _is_ relatively slow (though I've
never done enough testing to figure out whether/to what degree its
speed varies with inheritance depth and such).

As far as making things faster, at least a few things are usually
pretty easy: normally, all objects of a particular class (that has
virtual functions) share a single vtable. As such, finding whether two
objects are of the same class requires only comparing their vtable
pointers rather than retrieving and comparing type_info objects.
Pointers can normally be compared in a single operation, reducing this
to O(1) instead of O(N) on the type_info size.

I doubt anybody does a lot to minimize the time taken to traverse the
inheritance tree -- the typical expectation is that inheritance trees
are fairly shallow, and dynamic_casts are fairly rare. If you're
talking about 4 pointer comparisons happening once an hour, nothing you
do with it is going to make any noticeable difference in speed.

If you honestly had a good reason to do so, I'm pretty sure you could
do this with an expected complexity of O(1). Instead of walking the
list of vtable pointers, you'd create a hash-table indexed by the value
of the vtable pointer of the current class. The value it looked up
would be a boolean indicating whether that class could be converted to
the target type for the dynamic_cast.

If you were doing this in a lot of places, you could make it a
two-dimensional lookup, first looking up the table for a given target
type, then looking up the source pointer in that table to find whether
that particular conversion could take place.

As I said, however, I doubt anybody does this -- it would only make
sense if you expected many dynamic_casts, extremely deep inheritance
trees, or both. In fact, you pretty much expect neither.

 

[Ioannis Vranos]

can someone explain, purely for my information, how
dynamic_cast is implemented using only C++ language
facilities.

I don't mean how to use it, rather what is going on under the
hood.

Usually it is *not* implemented with C++ facilities. However all newer
C++ casts keep a templatised syntax, showing the way on how you can
write your own casts (brute force conversions).


Once I had written a cast converting from whatever pointer to another
pointer type, which always points at the beginning of an object, even in
multiple inheritance.


It was in the style:


#include <iostream>


template <class BasePointer, class CurrentPointer>
inline BasePointer base_cast(CurrentPointer cp)
{
return reinterpret_cast<BasePointer>(static_cast<void *>(cp));
}

class A
{};

int main()
{
A a;

unsigned char *p= base_cast<unsigned char *>(&a);
}