How expensive is getting the RTTI ?

[Vikram]

I was just curious to know how are calls like say dynamic_cast
implemented. Is it really expensive to get the exact type of an object
being pointed to by the baseclass pointer?

The reason I am asking is because of the well known issue of pointer
arithmetic not going well with polymorphism. Consider a function like

void myFunc( baseC ptr[], int length) {
for (int i=0; i<length; i++)
ptr[i].someField = somevalue;
}

Here baseC is some base class. Now, this function will not work as
intended if I pass in an array of derived class objects. (because
ptr[i] gets mapped to (ptr + i*sizeof(baseC)) )

Is it really expensive for the Compiler to generate proper code here
rather than just the sizeof addition? By proper code, I mean get the
type info for the actual objects pointed at by ptr and use that size.
If it indeed is that expensive, can it just do it for cases like above
where I can specifically give some kind of hint that myFunc can
"possibly" be invoked with an array of derived class objects.

Thanks,
Vikram

[Vikram]

Vikram wrote:

I was just curious to know how are calls like say dynamic_cast
implemented. Is it really expensive to get the exact type of an object
being pointed to by the baseclass pointer?

The reason I am asking is because of the well known issue of pointer
arithmetic not going well with polymorphism. Consider a function like

void myFunc( baseC ptr[], int length) {
for (int i=0; i<length; i++)
ptr[i].someField = somevalue;
}

Here baseC is some base class. Now, this function will not work as
intended if I pass in an array of derived class objects. (because
ptr[i] gets mapped to (ptr + i*sizeof(baseC)) )

Is it really expensive for the Compiler to generate proper code here
rather than just the sizeof addition? By proper code, I mean get the
type info for the actual objects pointed at by ptr and use that size.
If it indeed is that expensive, can it just do it for cases like above
where I can specifically give some kind of hint that myFunc can
"possibly" be invoked with an array of derived class objects.

Thanks,
Vikram

Oops! I think I already realized one of the reasons compilers dont even
try this. Like derived classes can be defined in different files so no
way a compiler would know about them when it is looking at this current
file.

Anyway, please let me know how expensive is getting run-time type info
in general. Dynamic_cast in particular

[benben]

> Anyway, please let me know how expensive is getting run-time type info

in general. Dynamic_cast in particular

Generally how exactly expensive RTTI is an issue of quality of
implementation. RTTI is almost certainly built on top of the virtual
function mechanism. It can be implemented as an anonymous virtual
function that traces down the inheritance graph. So you can assume O(n)+
complexity for n level of inheritance [Correct me if I am so wrong here.]

There is a polymorphic_downcast<> function template from boost cast
library you can use. It acts like dynamic cast for debug builds, and
like static_cast for release builds. Nevertheless, use it with great
caution.

Regards,
Ben

[Vikram]

benben wrote:

Anyway, please let me know how expensive is getting run-time type info
in general. Dynamic_cast in particular

Generally how exactly expensive RTTI is an issue of quality of
implementation. RTTI is almost certainly built on top of the virtual
function mechanism. It can be implemented as an anonymous virtual
function that traces down the inheritance graph. So you can assume O(n)+
complexity for n level of inheritance [Correct me if I am so wrong here.]

There is a polymorphic_downcast<> function template from boost cast
library you can use. It acts like dynamic cast for debug builds, and
like static_cast for release builds. Nevertheless, use it with great
caution.

Regards,
Ben

Thanks Ben. As of now, instead of dynamic_cast, we have just put
virtual int getSize() { return sizeof(*this);}
in all the classes of the hierarchy (some 4-5). And in myFunc, we did
ptr + i*ptr->getSize()
instead of using ptr[i]

I know this is not very elegant and especially if someone adds a new
class, he _has_ to override this method. But this is some old legacy
code and I dont want to change a lot here. And am pretty sure, there
wont be new classes added.

Thanks,
Vikram

[Luke Meyers]

benben wrote:

Generally how exactly expensive RTTI is an issue of quality of
implementation. RTTI is almost certainly built on top of the virtual
function mechanism. It can be implemented as an anonymous virtual
function that traces down the inheritance graph. So you can assume O(n)+
complexity for n level of inheritance [Correct me if I am so wrong here.]

I don't believe that to be the case. My understanding is that because
the vtable for each instance of a particular concrete class is the
same, and all the information necessary to construct it is available at
compile time, virtual dispatch overhead is independent of inheritance
depth -- basically it's an extra pointer deref, period (plus an
addition op for indexing? I'm not 100% sure). The only thing that has
to be done at runtime is to determine, by looking at the hidden vtable
pointer in each polymorphic class instance, which vtable to use.

Luke

[Thomas J. Gritzan]

Vikram schrieb:

benben wrote:

Anyway, please let me know how expensive is getting run-time type info
in general. Dynamic_cast in particular

Generally how exactly expensive RTTI is an issue of quality of
implementation. RTTI is almost certainly built on top of the virtual
function mechanism. It can be implemented as an anonymous virtual
function that traces down the inheritance graph. So you can assume O(n)+
complexity for n level of inheritance [Correct me if I am so wrong here.]

There is a polymorphic_downcast<> function template from boost cast
library you can use. It acts like dynamic cast for debug builds, and
like static_cast for release builds. Nevertheless, use it with great
caution.

Regards,
Ben

Thanks Ben. As of now, instead of dynamic_cast, we have just put
virtual int getSize() { return sizeof(*this);}
in all the classes of the hierarchy (some 4-5). And in myFunc, we did
ptr + i*ptr->getSize()
instead of using ptr[i]

I hope you convert ptr to (char*) before. Doing ptr[i*ptr->getSize()] is
not what you want.

Thomas

[benben]

> I don't believe that to be the case. My understanding is that because

the vtable for each instance of a particular concrete class is the
same, and all the information necessary to construct it is available at
compile time, virtual dispatch overhead is independent of inheritance
depth -- basically it's an extra pointer deref, period (plus an
addition op for indexing? I'm not 100% sure). The only thing that has
to be done at runtime is to determine, by looking at the hidden vtable
pointer in each polymorphic class instance, which vtable to use.

Luke

Ya that's true. But you are talking about virtual function, and I was
talking about dynamic_cast.

Virtual function by its own is a mere O(0) operation. I was talking
about the algorithm inside that possible virtual function that is O(n)
by its simplest.

Regards,
Ben

[benben]

> Thanks Ben. As of now, instead of dynamic_cast, we have just put

virtual int getSize() { return sizeof(*this);}
in all the classes of the hierarchy (some 4-5). And in myFunc, we did
ptr + i*ptr->getSize()
instead of using ptr[i]

I know this is not very elegant and especially if someone adds a new
class, he _has_ to override this method. But this is some old legacy
code and I dont want to change a lot here. And am pretty sure, there
wont be new classes added.

Thanks,
Vikram

Wow, I didn't know you have an array to BaseC instead of an array to
BaseC*. How did you convert DerivedC[], say, to BaseC[]?

There is a design problem here: why do you have an array to BaseC (not
BaseC*) instead of an array to DerivedC?

As with the legacy code, if you 1) are so confident that the BaseC[]
array is indeed a DerivedC array, and 2)want to bypass the runtime type
checking, then why don't you just use static_cast?

void myFunc( baseC ptr[], int length) {
DerivedC* ptr2 = static_cast<DerivedC*>(&ptr[0]);

for (int i=0; i<length; i++)
ptr2[i].someField = somevalue;
}

Regards,
Ben

[Luke Meyers]

benben wrote:

I don't believe that to be the case. My understanding is that because
the vtable for each instance of a particular concrete class is the
same, and all the information necessary to construct it is available at
compile time, virtual dispatch overhead is independent of inheritance
depth -- basically it's an extra pointer deref, period (plus an
addition op for indexing? I'm not 100% sure). The only thing that has
to be done at runtime is to determine, by looking at the hidden vtable
pointer in each polymorphic class instance, which vtable to use.

Luke

Ya that's true. But you are talking about virtual function, and I was
talking about dynamic_cast.

Virtual function by its own is a mere O(0) operation.

O(1). There are no O(0) operations. Review the formal definition
(e.g. on Wikipedia) if you are unclear as to why.
I was talking
about the algorithm inside that possible virtual function that is O(n)
by its simplest.

By what rationale? The O(n) exploration of the inheritance hierarchy
necessary to determine the validity of a dynamic_cast can be, and
surely is in any reasonable implementation, done at compile time. I
seriously doubt there's any reason the runtime operation can't be O(1).

Luke

[Thomas J. Gritzan]

benben schrieb:

>Thanks Ben. As of now, instead of dynamic_cast, we have just put
virtual int getSize() { return sizeof(*this);}
in all the classes of the hierarchy (some 4-5). And in myFunc, we did
ptr + i*ptr->getSize()
instead of using ptr[i]

I know this is not very elegant and especially if someone adds a new
class, he _has_ to override this method. But this is some old legacy
code and I dont want to change a lot here. And am pretty sure, there
wont be new classes added.
Thanks,
Vikram

Wow, I didn't know you have an array to BaseC instead of an array to
BaseC*. How did you convert DerivedC[], say, to BaseC[]?

There is a design problem here: why do you have an array to BaseC (not
BaseC*) instead of an array to DerivedC?

As with the legacy code, if you 1) are so confident that the BaseC[]
array is indeed a DerivedC array, and 2)want to bypass the runtime type
checking, then why don't you just use static_cast?

void myFunc( baseC ptr[], int length) {
DerivedC* ptr2 = static_cast<DerivedC*>(&ptr[0]);

for (int i=0; i<length; i++)
ptr2[i].someField = somevalue;
}

Because he wants to use this function polymorphically with baseC[] and
DericedC[]?

Thomas