question: cost of dynamic cast?
Author
hi all,
the following question is for C++ guru's: what is the cost of a dynamic (pointer) cast in C++? what is the typical way a c++ compiler (for example GNU's g++) to implement the dynamic cast? (My first thought was gnerating a large matrix of functions for which the entries perform the dynamic cast, but this way requires O(n^2) memory where n=#of types in a source file, so seems kind of high, when one considers how many types one gets just by doing a few includes)
Best Regards
typeof is a O(1) operation.
dynamic_cast<A>(b) will call a typeof-like function on A and b, and then determine if typeof(A) can be reached from typeof(b) in the type lattice of your program. As such, dynamic_cast is an O(n) operation, where n is the number of parents of the type of b.
This is because in a hierarchy like:
class A;
class B : public A;
class C : public B;
class D;
class E : public D, public C;
you can use dynamic_cast to cast an object of type E to A, B, C, D and E (which means just as many checks in the worst case).
I am currently working on a comparison between various RTTI methods, you can find it on this page. It's not complete yet, though, in particular I want to redo the entire benchmarking and add typeof comparison.
dynamic_cast<A>(b) will call a typeof-like function on A and b, and then determine if typeof(A) can be reached from typeof(b) in the type lattice of your program. As such, dynamic_cast is an O(n) operation, where n is the number of parents of the type of b.
This is because in a hierarchy like:
class A;
class B : public A;
class C : public B;
class D;
class E : public D, public C;
you can use dynamic_cast to cast an object of type E to A, B, C, D and E (which means just as many checks in the worst case).
I am currently working on a comparison between various RTTI methods, you can find it on this page. It's not complete yet, though, in particular I want to redo the entire benchmarking and add typeof comparison.
Quote:DELETEDOriginal post by moeron
It may be cheesy but I've always leaned more toward using ENUMS or some other method for determining RTTI.
I don't know if this is optimal for all solutions, but its worked for me. I'm sure there are many other similar ways to avoid dynamic casts.
This method is faster than dynamic_cast (could be as much as 5 times faster), and you can see an implementation of it in the above link. This has several problems:
- It's unsafe, you can create very nasty bugs by casting manually objects.
- It does not emulate dynamic_cast, because it cannot be used to cast to a supertype of the actual type, only to the actual type.
If you only need the reduced functionality of being able to cast to the actual type of the object, you can still use RTTI and typeof, as such:
if( typeof(object) == typeof(expected_type) ) { cast( ); } else { fail( ); }
This will not require the additional overhead of having to keep type information for your objects on your own.
I've used a variant of the enum approach several times. Instead of the "type" member only being a specific enum, it is an int that represents a bitfield.
Something like this
This lets you keep your hierarchy pretty much intact, and in your base class create a function that just checks your bit.
This allows you to take a BaseEntity* and do
so the limitation of being able to cast to only the specific type is gone. Obviously it still require the overhead of making a nre #define(or const) for new types you add, with proper unique bits and in their constructor setting their type variable, but its a little less limiting that using an enum.
Something like this
#define BASEENTITY 0x1000000000000000 #define ACTOR ( BASEENTITY | 0x0000100000000000 ) #define MONSTER ( ACTOR | 0x0000001000000000 ) #define PLAYER ( ACTOR | 0x0000002000000000 )This lets you keep your hierarchy pretty much intact, and in your base class create a function that just checks your bit.
This allows you to take a BaseEntity* and do
if(pBaseEnt->Is(ACTOR)) can cast to actorif(pBaseEnt->Is(MONSTER)) can cast to monsterif(pBaseEnt->Is(PLAYER)) can cast to playerso the limitation of being able to cast to only the specific type is gone. Obviously it still require the overhead of making a nre #define(or const) for new types you add, with proper unique bits and in their constructor setting their type variable, but its a little less limiting that using an enum.
Quote:Original post by DrEvil
so the limitation of being able to cast to only the specific type is gone. Obviously it still require the overhead of making a nre #define(or const) for new types you add, with proper unique bits and in their constructor setting their type variable, but its a little less limiting that using an enum.
However, this will still cause problems with multiple inheritance, when you cannot use plain casts because of the offset in the class. Also, I would advise for this purpose to use a virtual-function-based casting system which solves this problem (and is safer) and requires just as much code - without an important overhead.
DrEvil: While your method is nice *in principle*, it restricts you to 32 (for int) or 64 (for int64) different classes and requires much discipline or some nasty pre-processor hacks for class definition.
A flexible, less restricted system (even using enums or uids) would end up in an equal complexity as dynamic_cast.
The idea is very good for simple cases, however.
A flexible, less restricted system (even using enums or uids) would end up in an equal complexity as dynamic_cast.
The idea is very good for simple cases, however.
Quote:Original post by darookie
A flexible, less restricted system (even using enums or uids) would end up in an equal complexity as dynamic_cast.
Incorrect. The usual implementation of dynamic_cast requires a lattice traversal because storing statically type-casting data for all the types in the program would, as the OP mentions, take up too much memory in the executable.
However, if you restrict RTTI to only a small area of your program, such as a dozen classes, then you can use a constant-time implementation by (moderately) sacrificing memory use.
Using virtual functions to perform casts allows dynamic_cast semantics in O(1) time but O(n²) memory (unlike O(n) for both for dynamic_cast). If you have a small enough number of classes to use RTTI on, you can use this method and actually gain execution time.
I agree it's not perfect, but I doubt even any commercial games have enough classes they need this on for the number limitation to be much of a problem. And I wouldn't say adding 2 lines of code(a #define and a m_Type= in the ctr) requires any more discipline than adding the requirements for the other methods. I tend to avoid multiple inheritance as well.
I mentioned it as an alternative to the enum idea because someone mentioned you could only check for the specific class, not parents. Not because it is a one size fits all method. I don't especially like it much either. I've been considering lately of just using dynamic_cast. Thanks for posting some alternatives.
I mentioned it as an alternative to the enum idea because someone mentioned you could only check for the specific class, not parents. Not because it is a one size fits all method. I don't especially like it much either. I've been considering lately of just using dynamic_cast. Thanks for posting some alternatives.
Quote:Original post by ToohrVyk
typeof is a O(1) operation.
dynamic_cast<A>(b) will call a typeof-like function on A and b, and then determine if typeof(A) can be reached from typeof(b) in the type lattice of your program. As such, dynamic_cast is an O(n) operation, where n is the number of parents of the type of b.
This is because in a hierarchy like:
class A;
class B : public A;
class C : public B;
class D;
class E : public D, public C;
you can use dynamic_cast to cast an object of type E to A, B, C, D and E (which means just as many checks in the worst case).
I am currently working on a comparison between various RTTI methods, you can find it on this page. It's not complete yet, though, in particular I want to redo the entire benchmarking and add typeof comparison.
That was an interesting article. I also tried my hand at a "better RTTI" a while back. It works like this:
class TypeInfo{ // info on a type (name and up to 4 parent pointers)};class DynamicTypeObject{ bool IsA (const TypeInfo& type); bool IsA (const char* type); // performs lookup of registered types virtual const TypeInfo* GetType () = 0;};It would be used like this:
class Item : virtual public DynamicTypeObject{ static TypeInfo Type; const TypeInfo* GetType () { return &Type; }};TypeInfo Item::Type("Item"); // in .cpp fileclass Potion : public Item{ static TypeInfo Type; const TypeInfo* GetType () { return &Type; }};TypeInfo Potion::Type("Potion", &Item::Type); // in .cpp fileclass Scroll : public Item{ static TypeInfo Type; const TypeInfo* GetType () { return &Type; }};TypeInfo Scroll::Type("Scroll", &Item::Type); // in .cpp fileAnd finally you would use it like this:
void Drink (Item* i){ // basic RTTI equivalent if (i->IsA(Potion::Type)) { // it's a potion // (this does not address multiple inheritance...) Potion* p = (Potion*)i; } // something RTTI could never dream of doing if (i->IsA("Potion")) { }}This still does not address multiple inheritance, but I have not really thought that far since I never needed to yet. I think a solution to that would not be so hard.
The main advantage of this method seems to be that you only have to use as many TypeInfo objects as you actually need, instead of for every single class.
But it occured to me that if I can be selective in this way, then why can't the compiler be as well? After all, if you don't use dynamic_cast anywhere, you don't need any RTTI (even if it's enabled). If you only use dynamic_cast<Potion*> then the compiler knows it only needs type info for Potion and its parent(s). Something like this sounds simple to optimize.
Also, I benchmarked my implementation against RTTI and it was about 3 times slower (optimized VC++ 7). So unless I am doing something horribly wrong, then the "RTTI is slow" argument is out the window, as far as I'm concerned. Not that typecasting is going to take up much CPU % anyway, but thought I'd mention it anyway.
So overall, RTTI doesn't seem so bad after all. It's fast and if my assumption is correct, is lightweight (or at least could be).
I'm still using my own method though. Querying with strings, mmmmm.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
