How expensive is RTTI?

Question

I understand that there is a resource hit from using RTTI, but how big is it? Everywhere I've looked just says that "RTTI is expensive," but none of them actually give any benchmarks or quantitative data reguarding memory, processor time, or speed.

So, just how expensive is RTTI? I might use it on an embedded system where I have only 4MB of RAM, so every bit counts.

Edit: As per S. Lott's answer, it would be better if I include what I'm actually doing. I am using a class to pass in data of different lengths and that can perform different actions, so it would be difficult to do this using only virtual functions. It seems that using a few dynamic_casts could remedy this problem by allowing the different derived classes to be passed through the different levels yet still allow them to act completely differently.

From my understanding, dynamic_cast uses RTTI, so I was wondering how feasable it would be to use on a limited system.

Answer 1

It depends on the scale of things. For the most part it's just a couple checks and a few pointer dereferences. In most implementations, at the top of every object that has virtual functions, there is a pointer to a vtable that holds a list of pointers to all the implementations of the virtual function on that class. I would guess that most implementations would use this to either store another pointer to the type_info structure for the class.

For example in pseudo-c++:

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

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


int main()
{
    Base *d = new Derived();
    const char *name = typeid(*d).name(); // C++ way

    // faked up way (this won't actually work, but gives an idea of what might be happening in some implementations).
    const vtable *vt = reinterpret_cast<vtable *>(d);
    type_info *ti = vt->typeinfo;
    const char *name = ProcessRawName(ti->name);       
}

In general the real argument against RTTI is the unmaintainability of having to modify code everywhere every time you add a new derived class. Instead of switch statements everywhere, factor those into virtual functions. This moves all the code that is different between classes into the classes themselves, so that a new derivation just needs to override all the virtual functions to become a fully functioning class. If you've ever had to hunt through a large code base for every time someone checks the type of a class and does something different, you'll quickly learn to stay away from that style of programming.

If your compiler lets you totally turn off RTTI, the final resulting code size savings can be significant though, with such a small RAM space. The compiler needs to generate a type_info structure for every single class with a virtual function. If you turn off RTTI, all these structures do not need to be included in the executable image.

Answer 2

RTTI can be "expensive" because you've added an if-statement every single time you do the RTTI comparison. In deeply nested iterations, this can be pricey. In something that never gets executed in a loop it's essentially free.

The choice is to use proper polymorphic design, eliminating the if-statement. In deeply nested loops, this is essential for performance. Otherwise, it doesn't matter very much.

RTTI is also expensive because it can obscure the subclass hierarchy (if there even is one). It can have the side-effect of removing the "object oriented" from "object oriented programming".

Answer 3

For a simple check, RTTI can be as cheap as a pointer comparison. For inheritance checking, it can be as expensive as a strcmp for every type in an inheritance tree if you are dynamic_cast-ing from the top to the bottom in one implementation out there.

You can also reduce the overhead by not using dynamic_cast and instead checking the type explicitly via &typeid(...)==&typeid(type). While that doesn't necessarily work for .dlls or other dynamically loaded code, it can be quite fast for things that are statically linked.

Although at that point it's like using a switch statement, so there you go.

Answer 4

So, just how expensive is RTTI?

That depends entirely on the compiler you're using. I understand that some use string comparisons, and others use real algorithms.

Your only hope is to write a sample program and see what your compiler does (or at least determine how much time it takes to execute a million dynamic_casts or a million typeids).

Answer 5

It's always best to measure things. In the following code, under g++, the use of hand coded type identification seems to be about three times faster than RTTI. I'm sure that a more realistic hand coded implementtaion using strings instead of chars would be slower, bringing the timings close together..

#include <iostream>
using namespace std;

struct Base {
    virtual ~Base() {}
    virtual char Type() const = 0;
};

struct A : public Base {
    char Type() const {
        return 'A';
    }
};

struct B : public Base {;
    char Type() const {
        return 'B';
    }
};

int main() {
    Base * bp = new A;
    int n = 0;
    for ( int i = 0; i < 10000000; i++ ) {
#ifdef RTTI
        if ( A * a = dynamic_cast <A*> ( bp ) ) {
            n++;
        }
#else
        if ( bp->Type() == 'A' ) {
            A * a = static_cast <A*>(bp);
            n++;
        }
#endif
    }
    cout << n << endl;
}

Answer 6

The standard way:

cout << (typeid(Base) == typeid(Derived)) << endl;

Standard RTTI is expensive because it relies on doing a underlying string compare and thus the speed of RTTI can vary depending on the class name length.

The reason why string compares are used is to make it work consistently across library/DLL boundaries. If you build your application statically and/or you are using certain compilers then you can probably use:

cout << (typeid(Base).name() == typeid(Derived).name()) << endl;

Which is not guaranteed to work (will never give a false positive, but may give false negatives) but can be up to 15 times faster. This relies on the implementation of typeid() to work in a certain way and all you are doing is comparing an internal char pointer. This is also sometimes equivalent to:

cout << (&typeid(Base) == &typeid(Derived)) << endl;

You can however use a hybrid safely which will be very fast if the types match, and will be worst case for unmatched types:

cout << ( typeid(Base).name() == typeid(Derived).name() || 
          typeid(Base) == typeid(Derived) ) << endl;

To understand whether you need to optimize this you need to see how much of your time you spend getting a new packet, compared to the time it takes to process the packet. In most cases a string compare will probably not be a large overhead. (depending on your class or namespace::class name length)

The safest way to optimize this is to implement your own typeid as an int (or a enum Type : int ) as part of your Base class and use that to determine the type of the class, and then just use static_cast<> or reinterpret_cast<>

For me the difference is roughly 15 times on unoptimized MS VS 2005 C++ SP1.

Answer 7

RTTI can be cheap and doesn't necessarly need a strcmp. The compiler limits the test to perform the actual hierarchy, in reverse order. So if you have a class C that is a child of class B which is a child of class A, dynamic_cast from a A* ptr to a C* ptr imply only one pointer comparison and not two (BTW, only the vptr table pointer is compared). The test is like "if (vptr_of_obj == vptr_of_C) return (C*)obj"

Another example, if we try to dynamic_cast from A* to B*. In that case, the compiler will check both case (obj being a C, and obj being a B) in turns. This can also be simplified to a single test (most of times), as virtual function table is a made as an aggregation, so the test resume to "if (offset_of(vptr_of_obj, B) == vptr_of_B)" with

offset_of = return sizeof(vptr_table) >= sizeof(vptr_of_B) ? vptr_of_new_methods_in_B : 0

The memory layout of

vptr_of_C = [ vptr_of_A | vptr_of_new_methods_in_B | vptr_of_new_methods_in_C ]

How does the compiler know of to optimize this at compile time ?

At compile time, the compiler knows the current hierarchy of objects, so it refuse to compile different type hierarchy dynamic_casting. Then it just has to handle the hierarchy depth, and add the invert amount of tests to match such depth.

For example, this doesn't compile:

void * something = [...]; 
// Compile time error: Can't convert from something to MyClass, no hierarchy relation
MyClass * c = dynamic_cast<MyClass*>(something);