Time complexity of typeid and dynamic_cast operations in C++

0
votes

Setting aside all the concerns about the necessity of using typeid and dynamic_cast and their questionable effects on code maintenance, is there any information about the performance of these two dynamic type introspection mechanisms? The Wikipedia article on RTTI claims that:

The use of typeid, in a non-polymorphic context, is often preferred over dynamic_cast<class_type> in situations where just the class information is needed, because typeid is always a constant-time procedure, whereas dynamic_cast may need to traverse the class derivation lattice of its argument at runtime.

However no citation is provided. As such I wanted to ask if this claim is true and if one of these two mechanisms should definitely be preferred performance-wise over the other. I wasn't able to find information about any bounds on time complexity of these operations.

1
c++time-complexityrttidynamic-casttypeid
Maybe, have a look at cppreference.com: typeid operator: When applied to an expression of polymorphic type, evaluation of a typeid expression may involve runtime overhead (a virtual table lookup), otherwise typeid expression is resolved at compile time. - Scheff's Cat
Thanks for the quote. To me it suggests that the complexity is constant, as a vtable lookup would be just a couple pointer dereferences, but it is not explicitly stated if that is indeed the case. - janekb04
It seems so: Fiddling on Compiler Explorer - Scheff's Cat
Though, maybe, the comparison is not quite fair. With typeid, you can check for a specific type but not whether the type is compatible (like you could with dynamic_cast): Counter Example on Compiler Explorer - Scheff's Cat
It seems like type_info doesn't really have to be that cheap. This question speaks of implementations that use strcmp: stackoverflow.com/questions/49773686/… . This libstdc++ file seems to confirm: gcc.gnu.org/onlinedocs/gcc-7.5.0/libstdc++/api/… . - janekb04

1 Answers

1
votes

The language standard doesn't impose any requirements about the complexity of either operation. As such, the statement that you quote isn't backed up by specification. It is presumably based on either how the functionality can be, or has been implemented in practice.

Bigger problem with the claim of preferability is that it is quite unclear how dynamic_cast even could be used in a non-polymorphic context.

If you're doing object oriented dynamic polymorphism, then what you should prefer is virtual functions.