How dynamic_cast works internally?

[Bo Yang]

Hi,
I can understand static_cast, reinterpret_cast and const_cast, they
all work at compile time. But I can figure out how the C++'s dynamic-
cast works? Could you please explain how for me?
Thanks in advance!

Regards!
Bo

 

[akshay.saidulu]

Hi,
I can understand static_cast, reinterpret_cast and const_cast, they
all work at compile time. But I can figure out how the C++'s dynamic-
cast works? Could you please explain how for me?
Thanks in advance!

Regards!
Bo

Dynamic cast adjests the offset adress of the perticul type
accordigly .if it does't find the type it will raise the exception (in
case of reference)or it will return null.
Ex:
class base{
};

class base1{
};
class derived : public base1,public base2{
};
deribed temp = new derived;
base2 *p = dynamic_cast<base2*> temp;

it will adject the prt offset to base2 part of the temp object.

Br,
akshay saidulu

 

[Lance Diduck]

Hi,
I can understand static_cast, reinterpret_cast and const_cast, they
all work at compile time. But I can figure out how the C++'s dynamic-
cast works? Could you please explain how for me?
Thanks in advance!

Regards!
Bo

Consider this case:
class A{virtual ~A(){};};
class Bublic A{};
A*a=new B;
B*b =dynamic_cast<B*>(a);
Conceptually, it is like this if is were written in C:

void A_dtor(A* ){}
typeinfo A_RTTI(){
static typeinfo
return typeinfo("A");
}//compiler generated
void(*)() A_vtbl[]={A_dtor,A_RTTI};
struct A{
A_vtbl*vptr;
};
A_ctor(){vptr=A_vtbl;}//compiler generated

void B_dtor(B* ){}
typeinfo B_RTTI(){
static typeinfo
return typeinfo("B");
}//compiler generated
void(*)(B*) B_vtbl[]={B_dtor,B_RTTI};
struct B{
B_vtbl*vptr;
};
B_ctor(){vptr=B_vtbl;}//compiler generated

This is what A and B conceptually look like underneath the hood. Now
when dynamic_cast is called, the compiler generates a function
something like

B* Dynamic_Cast(A*a ){
if(*((a->vptr)+1)()==B_RTTI())
return a;
return 0;
}

From this, it is easy to extrapolate how this can be extended to work

for references.

You can see the reason now why dynamic_cast only works for types that
have "virtual" somewhere, either a function or inheritance.

Lance

 

[Greg Herlihy]

Consider this case:
class A{virtual ~A(){};};
class Bublic A{};
A*a=new B;
B*b =dynamic_cast<B*>(a);. .

B* Dynamic_Cast(A*a ){
if(*((a->vptr)+1)()==B_RTTI())
return a;
return 0;

}

This implementation might work for typeid - because typeid has to
confirm only that type of the object being tested - matches the
specified type exactly.

A dynamic_cast operator however has to perform a much more complicated
test: whether an object (of unknown thype) is related to another type.
And to make do with a lot less information about the classes involved
than existed in the example above. For example:

struct A
{
virtual ~A() {}
};

bool TestA(void *p)
{
assert( p != NULL);
return dynamic_cast<A*>(p) != NULL;
}

Note that no derived classes of A (if any exist) are visible when this
source file is compiled. So no matter how many large or complex this
program's class hierarchy might be, dynamic_cast<> has only the "A"
class declaration with which to work here.

So how is dynamic_cast<> supposed to figure out whether p points to a
type that is somehow related to A? Well, given these constraints,
there is only one way to solve this problem. dynamic_cast must search
p's class hierarchy (essentially, discovering its layout as it goes
along) and to continue the search until either a A class is located
with the hierarchy - or there are no other classes left in the
hierarchy that need to be checked.

Greg

 

[Bo Yang]

(e-mail address removed) ]:

Dynamic cast adjests the offset adress of the perticul type
accordigly .if it does't find the type it will raise the exception (in
case of reference)or it will return null.
Ex:
class base{
};

class base1{
};
class derived : public base1,public base2{
};
deribed temp = new derived;
base2 *p = dynamic_cast<base2*> temp;

it will adject the prt offset to base2 part of the temp object.

Does it just adject the pointer without any additional check of type?

Regards!
Bo

 

[Bo Yang]

Lance Diduck:

Consider this case:
class A{virtual ~A(){};};
class Bublic A{};
A*a=new B;
B*b =dynamic_cast<B*>(a);
Conceptually, it is like this if is were written in C:

void A_dtor(A* ){}
typeinfo A_RTTI(){
static typeinfo
return typeinfo("A");
}//compiler generated
void(*)() A_vtbl[]={A_dtor,A_RTTI};
struct A{
A_vtbl*vptr;
};
A_ctor(){vptr=A_vtbl;}//compiler generated

void B_dtor(B* ){}
typeinfo B_RTTI(){
static typeinfo
return typeinfo("B");
}//compiler generated
void(*)(B*) B_vtbl[]={B_dtor,B_RTTI};
struct B{
B_vtbl*vptr;
};
B_ctor(){vptr=B_vtbl;}//compiler generated

This is what A and B conceptually look like underneath the hood. Now
when dynamic_cast is called, the compiler generates a function
something like

B* Dynamic_Cast(A*a ){
if(*((a->vptr)+1)()==B_RTTI())
return a;
return 0;
}

Thank you for your detailed explaination. And you mean all dynamic_cast
use RTTI inside. yes?

for references.

You can see the reason now why dynamic_cast only works for types that
have "virtual" somewhere, either a function or inheritance.

Yes, class with no virtual has no virtual table at all.

Thanks!

Regards!
Bo

 

[Bo Yang]

Greg Herlihy :

This implementation might work for typeid - because typeid has to
confirm only that type of the object being tested - matches the
specified type exactly.

A dynamic_cast operator however has to perform a much more complicated
test: whether an object (of unknown thype) is related to another type.
And to make do with a lot less information about the classes involved
than existed in the example above. For example:

struct A
{
virtual ~A() {}
};

bool TestA(void *p)
{
assert( p != NULL);
return dynamic_cast<A*>(p) != NULL;
}

Note that no derived classes of A (if any exist) are visible when this
source file is compiled. So no matter how many large or complex this
program's class hierarchy might be, dynamic_cast<> has only the "A"
class declaration with which to work here.

So how is dynamic_cast<> supposed to figure out whether p points to a
type that is somehow related to A? Well, given these constraints,
there is only one way to solve this problem. dynamic_cast must search
p's class hierarchy (essentially, discovering its layout as it goes
along) and to continue the search until either a A class is located
with the hierarchy - or there are no other classes left in the
hierarchy that need to be checked.

So, how C++ go along the classes hierarchy at runtime? RTTI? Is RTTI a
standard of C++? I think RTTI is not a standard part of C++!

Regards!
Bo

 

[dasjotre]

You can see the reason now why dynamic_cast only works for types that
have "virtual" somewhere, either a function or inheritance.

only for upcast.

downcast must work too regardless to
virtuals:

struct B{};
struct D : B {};
D d;
B & b = dynamic_cast<B&>(d); // OK,
B & b1 = d; // is OK too

DS

 

[Pete Becker]

So, how C++ go along the classes hierarchy at runtime? RTTI? Is RTTI a
standard of C++? I think RTTI is not a standard part of C++!

Well, yes, there is no specification of anything called RTTI in the
language definition. But RTTI is shorthand for the usual implementation
technique for dynamic_cast and for catching exceptions. The compiler
generates type information that's used at runtime to match types as
needed. Hence, RunTime Type Information.

 

[Guest]

Greg Herlihy :

So, how C++ go along the classes hierarchy at runtime? RTTI? Is RTTI a
standard of C++? I think RTTI is not a standard part of C++!

RTTI is part of the C++ standard, do not confuse it with reflection
though. One way to accomplish this (though I do not think that is how it
is done) would be to add a second pointer (in addition to the vtable)
which points to a type object looking something like this:

class Type
{
char name[];
Type* super[];
Type* derived[];
};

That way typeid could (conceptually) be implemented something like this:

template<typename T>
type_info typeid(T t)
{
return type_info(t->typePtr->name)
}

And using some simple tree walking algorithms you can find out if a type
is in the same type-hierarchy as another.

 

[dasjotre]

only for upcast.

ahmm, that would be 'downcast' instead

downcast must work too regardless to

and that would be 'upcast' instead

 

[Bo Yang]

Erik Wikström

Greg Herlihy :
So, how C++ go along the classes hierarchy at runtime? RTTI? Is RTTI a
standard of C++? I think RTTI is not a standard part of C++!

RTTI is part of the C++ standard, do not confuse it with reflection
though. One way to accomplish this (though I do not think that is how it
is done) would be to add a second pointer (in addition to the vtable)
which points to a type object looking something like this:

class Type
{
char name[];
Type* super[];
Type* derived[];
};

That way typeid could (conceptually) be implemented something like this:

template<typename T>
type_info typeid(T t)
{
return type_info(t->typePtr->name)
}

And using some simple tree walking algorithms you can find out if a type
is in the same type-hierarchy as another.

So, C++ type conversion will be time-consuming and space-consuming,
right? And maybe that is why C++ program is much more big than C's?

Regards!
Bo

 

[Bo Yang]

dasjotre :

ahmm, that would be 'downcast' instead


and that would be 'upcast' instead

Yeah, I know. Thanks!

 

[Guest]

Erik Wikström

Greg Herlihy :
I can understand static_cast, reinterpret_cast and const_cast, they
all work at compile time. But I can figure out how the C++'s dynamic-
cast works? Could you please explain how for me?
Thanks in advance!
Regards!
Bo
Consider this case:
class A{virtual ~A(){};};
class Bublic A{};
A*a=new B;
B*b =dynamic_cast<B*>(a);. .
B* Dynamic_Cast(A*a ){
if(*((a->vptr)+1)()==B_RTTI())
return a;
return 0;

}
This implementation might work for typeid - because typeid has to
confirm only that type of the object being tested - matches the
specified type exactly.

A dynamic_cast operator however has to perform a much more complicated
test: whether an object (of unknown thype) is related to another type.
And to make do with a lot less information about the classes involved
than existed in the example above. For example:

struct A
{
virtual ~A() {}
};

bool TestA(void *p)
{
assert( p != NULL);
return dynamic_cast<A*>(p) != NULL;
}

Note that no derived classes of A (if any exist) are visible when this
source file is compiled. So no matter how many large or complex this
program's class hierarchy might be, dynamic_cast<> has only the "A"
class declaration with which to work here.

So how is dynamic_cast<> supposed to figure out whether p points to a
type that is somehow related to A? Well, given these constraints,
there is only one way to solve this problem. dynamic_cast must search
p's class hierarchy (essentially, discovering its layout as it goes
along) and to continue the search until either a A class is located
with the hierarchy - or there are no other classes left in the
hierarchy that need to be checked.
So, how C++ go along the classes hierarchy at runtime? RTTI? Is RTTI a
standard of C++? I think RTTI is not a standard part of C++!

RTTI is part of the C++ standard, do not confuse it with reflection
though. One way to accomplish this (though I do not think that is how it
is done) would be to add a second pointer (in addition to the vtable)
which points to a type object looking something like this:

class Type
{
char name[];
Type* super[];
Type* derived[];
};

That way typeid could (conceptually) be implemented something like this:

template<typename T>
type_info typeid(T t)
{
return type_info(t->typePtr->name)
}

And using some simple tree walking algorithms you can find out if a type
is in the same type-hierarchy as another.

So, C++ type conversion will be time-consuming and space-consuming,
right? And maybe that is why C++ program is much more big than C's?

As I said, that was only a conceptual example, I do not know how they
really do it in a compiler. But you should notice that all but
dynamic_cast can be done at compile-time without any extra run-time
information, so to claim that C++ casts are more costly than C casts are
not really true. On the other hand, added type-safety obviously does not
come for free, so some extra overhead is inevitable.

 

[Bo Yang]

Erik Wikström :

Erik Wikström

On 2007-10-22 15:19, Bo Yang wrote:
Greg Herlihy :
I can understand static_cast, reinterpret_cast and const_cast, they
all work at compile time. But I can figure out how the C++'s dynamic-
cast works? Could you please explain how for me?
Thanks in advance!
Regards!
Bo
Consider this case:
class A{virtual ~A(){};};
class Bublic A{};
A*a=new B;
B*b =dynamic_cast<B*>(a);. .
B* Dynamic_Cast(A*a ){
if(*((a->vptr)+1)()==B_RTTI())
return a;
return 0;

}
This implementation might work for typeid - because typeid has to
confirm only that type of the object being tested - matches the
specified type exactly.

A dynamic_cast operator however has to perform a much more complicated
test: whether an object (of unknown thype) is related to another type.
And to make do with a lot less information about the classes involved
than existed in the example above. For example:

struct A
{
virtual ~A() {}
};

bool TestA(void *p)
{
assert( p != NULL);
return dynamic_cast<A*>(p) != NULL;
}

Note that no derived classes of A (if any exist) are visible when this
source file is compiled. So no matter how many large or complex this
program's class hierarchy might be, dynamic_cast<> has only the "A"
class declaration with which to work here.

So how is dynamic_cast<> supposed to figure out whether p points to a
type that is somehow related to A? Well, given these constraints,
there is only one way to solve this problem. dynamic_cast must search
p's class hierarchy (essentially, discovering its layout as it goes
along) and to continue the search until either a A class is located
with the hierarchy - or there are no other classes left in the
hierarchy that need to be checked.
So, how C++ go along the classes hierarchy at runtime? RTTI? Is RTTI a
standard of C++? I think RTTI is not a standard part of C++!
RTTI is part of the C++ standard, do not confuse it with reflection
though. One way to accomplish this (though I do not think that is how it
is done) would be to add a second pointer (in addition to the vtable)
which points to a type object looking something like this:

class Type
{
char name[];
Type* super[];
Type* derived[];
};

That way typeid could (conceptually) be implemented something like this:

template<typename T>
type_info typeid(T t)
{
return type_info(t->typePtr->name)
}

And using some simple tree walking algorithms you can find out if a type
is in the same type-hierarchy as another.

So, C++ type conversion will be time-consuming and space-consuming,
right? And maybe that is why C++ program is much more big than C's?

As I said, that was only a conceptual example, I do not know how they
really do it in a compiler. But you should notice that all but
dynamic_cast can be done at compile-time without any extra run-time
information, so to claim that C++ casts are more costly than C casts are
not really true. On the other hand, added type-safety obviously does not
come for free, so some extra overhead is inevitable.

Yeah, thank you very much!

Regards!
Bo

 

[James Kanze]

Erik Wikström [...]

RTTI is part of the C++ standard, do not confuse it with reflection
though. One way to accomplish this (though I do not think that is how it
is done) would be to add a second pointer (in addition to the vtable)
which points to a type object looking something like this:
class Type
{
char name[];
Type* super[];
Type* derived[];
};
That way typeid could (conceptually) be implemented something like this:
template<typename T>
type_info typeid(T t)
{
return type_info(t->typePtr->name)
}
And using some simple tree walking algorithms you can find out if a type
is in the same type-hierarchy as another.

The "extra pointer" is usually in the vtbl, not in the object
itself. Types with a virtual function will have a vptr to the
vtbl anyway, so RTTI is essentially free for them if they don't
use it. (It increases the size of the static data associated
with the type, but this is typically a negligeable part of the
total program size.)

In the simplest implementation, all of the necessary information
will be wrapped up in the type_info object, there will be
exactly one type_info object per type, and its address serves as
the identity. From what I understand, this isn't possible for
some implementations of dynamically loaded objects, where you
end up with a type_info object per dynamically loaded object; in
such cases, typically, the implementation will first tree walk
using the addresses for identity, and if this fails, will repeat
using string comparisons on the names.

So, C++ type conversion will be time-consuming and
space-consuming, right?

Dynamic_cast will take a bit more time than a static_cast. On
the other hand, it leads to a lot less core dumps.

Space consumation is generally very small, not nearly as much as
what is required for a good implementation of exceptions, for
example. Probably less that 100 bytes per polymorphic type.

And maybe that is why C++ program is much more big than C's?

I doubt it. In my experience, the main reason why C++ programs
are bigger is because they do much more. With a good class
library, it's easy to add functionality which would cost too
much to add in C.

 

[James Kanze]

[...]

As I said, that was only a conceptual example, I do not know how they
really do it in a compiler. But you should notice that all but
dynamic_cast can be done at compile-time without any extra run-time
information, so to claim that C++ casts are more costly than C casts are
not really true. On the other hand, added type-safety obviously does not
come for free, so some extra overhead is inevitable.

The standard doesn't say anything about time or space overhead
for a cast, but typically: reinterpret_cast and const_cast
generate no code, static_cast will sometimes generate no code,
and rarely more than one or two machine instructions (except for
static_cast's involving floating point types on machines without
hardware floating point support), and dynamic_cast will involve
10's or 100's of machine instructions, depending on the
case.

Note too that in some cases, the compiler can resolve the
dynamic_cast directly, and implement it much as it would a
static_cast. I think all compilers do this for dynamic_cast's
from derived to base.