What Can Make C++ Rtti Undesirable to Use

What can make C++ RTTI undesirable to use?

There are several reasons why LLVM rolls its own RTTI system. This system is simple and powerful, and described in a section of the LLVM Programmer's Manual. As another poster has pointed out, the Coding Standards raises two major problems with C++ RTTI: 1) the space cost and 2) the poor performance of using it.

The space cost of RTTI is quite high: every class with a vtable (at least one virtual method) gets RTTI information, which includes the name of the class and information about its base classes. This information is used to implement the typeid operator as well as dynamic_cast. Because this cost is paid for every class with a vtable (and no, PGO and link-time optimizations don't help, because the vtable points to the RTTI info) LLVM builds with -fno-rtti. Empirically, this saves on the order of 5-10% of executable size, which is pretty substantial. LLVM doesn't need an equivalent of typeid, so keeping around names (among other things in type_info) for each class is just a waste of space.

The poor performance is quite easy to see if you do some benchmarking or look at the code generated for simple operations. The LLVM isa<> operator typically compiles down to a single load and a comparison with a constant (though classes control this based on how they implement their classof method). Here is a trivial example:

#include "llvm/Constants.h"
using namespace llvm;
bool isConstantInt(Value *V) { return isa<ConstantInt>(V); }

This compiles to:

$ clang t.cc -S -o - -O3 -I$HOME/llvm/include -D__STDC_LIMIT_MACROS -D__STDC_CONSTANT_MACROS -mkernel -fomit-frame-pointer
...
__Z13isConstantIntPN4llvm5ValueE:
    cmpb    $9, 8(%rdi)
    sete    %al
    movzbl  %al, %eax
    ret

which (if you don't read assembly) is a load and compare against a constant. In contrast, the equivalent with dynamic_cast is:

#include "llvm/Constants.h"
using namespace llvm;
bool isConstantInt(Value *V) { return dynamic_cast<ConstantInt*>(V) != 0; }

which compiles down to:

clang t.cc -S -o - -O3 -I$HOME/llvm/include -D__STDC_LIMIT_MACROS -D__STDC_CONSTANT_MACROS -mkernel -fomit-frame-pointer
...
__Z13isConstantIntPN4llvm5ValueE:
    pushq   %rax
    xorb    %al, %al
    testq   %rdi, %rdi
    je  LBB0_2
    xorl    %esi, %esi
    movq    $-1, %rcx
    xorl    %edx, %edx
    callq   ___dynamic_cast
    testq   %rax, %rax
    setne   %al
LBB0_2:
    movzbl  %al, %eax
    popq    %rdx
    ret

This is a lot more code, but the killer is the call to __dynamic_cast, which then has to grovel through the RTTI data structures and do a very general, dynamically computed walk through this stuff. This is several orders of magnitude slower than a load and compare.

Ok, ok, so it's slower, why does this matter? This matters because LLVM does a LOT of type checks. Many parts of the optimizers are built around pattern matching specific constructs in the code and performing substitutions on them. For example, here is some code for matching a simple pattern (which already knows that Op0/Op1 are the left and right hand side of an integer subtract operation):

  // (X*2) - X -> X
  if (match(Op0, m_Mul(m_Specific(Op1), m_ConstantInt<2>())))
    return Op1;

The match operator and m_* are template metaprograms that boil down to a series of isa/dyn_cast calls, each of which has to do a type check. Using dynamic_cast for this sort of fine-grained pattern matching would be brutally and showstoppingly slow.

Finally, there is another point, which is one of expressivity. The different 'rtti' operators that LLVM uses are used to express different things: type check, dynamic_cast, forced (asserting) cast, null handling etc. C++'s dynamic_cast doesn't (natively) offer any of this functionality.

In the end, there are two ways to look at this situation. On the negative side, C++ RTTI is both overly narrowly defined for what many people want (full reflection) and is too slow to be useful for even simple things like what LLVM does. On the positive side, the C++ language is powerful enough that we can define abstractions like this as library code, and opt out of using the language feature. One of my favorite things about C++ is how powerful and elegant libraries can be. RTTI isn't even very high among my least favorite features of C++ :) !

-Chris

avoiding RTTI in OO design

There are a ridiculously large number of ways to satisfy this problem using "OO concepts," depending on what you want to emphasize.

Here's the simplest solution that I can come up with:

class Animal {
public:
    virtual void seenBy(Buddy&) = 0;
};

class Buddy {
public:
    void see(Cat&)      { /* ... */ }
    void see(Squirrel&) { /* ... */ }
    // ...
};

class Cat : public Animal {
public:
    virtual seenBy(Buddy& b) { b.see(*this); }
};

class Squirrel : public Animal {
public:
    virtual seenBy(Buddy& b) { b.see(*this); }
};

// classes for Frog, Coyote, Spot...

If you need multiple kinds of "perceiving" animals, it's straightforward to make a virtual wrapper for see (producing a form of double dispatch):

// On a parent class
virtual void see(Animal&) = 0;

// On Buddy
virtual void see(Animal& a) { a.seenBy(*this); }

---

The above requires that the Animal class know something about the Buddy class. If you don't like your methods being passive verbs and want to decouple Animal from Buddy, you can use the visitor pattern:

class Animal {
public:
    virtual void visit(Visitor&) = 0;
};

class Cat : public Animal {
public:
    virtual void visit(Visitor& v) { v.visit(*this); }
};

class Squirrel : public Animal {
public:
    virtual void visit(Visitor& v) { v.visit(*this); }
};

// classes for Frog, Coyote, Spot...

class Visitor {
public:
    virtual void visit(Cat&) = 0;
    virtual void visit(Squirrel&) = 0;
    // ...
};

class BuddyVision : public Visitor {
public:
    virtual void visit(Cat&)      { /* ... */ }
    virtual void visit(Squirrel&) { /* ... */ }
    // ...
};

class Buddy {
public:
    void see(Animal& a) {
        BuddyVision visitor;
        a.visit(visitor);
    }
};

The second mechanism could be used for purposes other than Buddy seeing an animal (possibly for that animal seeing Buddy). It is, however, more complicated.

---

Note that OO is definitely not the only way to solve this problem. Other solutions exist that may be more practical for this problem, such as storing the properties of the various animals that cause Buddy to bark, eat, play, etc. This additionally decouples the Buddy class from the Animal class (even the visitor pattern needs an exhaustive list of everything that Buddy can perceive).

Is using RTTI (or virtual functions that return a type tag) ever OK?

It is not only OK to use dynamic_cast but it is essential in many contexts.

When I see code like that, I use the Open-Closed Principle as a guide.

If I have to revisit that if-else block or the enum when a new derived type is added to the system, I see that as a problem. If not, I don't think of it as a problem.

When you see cascading if-else blocks of code, it usually violates the Open-Closed Principle and should be avoided. The way to avoid that is to use a callback mechanism.

1. Let the base class have a function to register a callback function for derived types.
2. In the business logic of the base class, check whether a function has been registered for the derived type. If yes, call the function. If not, it is either to be ignored silently or an exception needs to be raised.

Why does RTTI seem frowned upon?

1. Because using it usually means you are subverting polymorphism (if (type is foo) { do this; } else if (type is bar) { do that; } else ...), which usually means you have engineered yourself into a corner and need to rethink your design.

2. Because authors of C++ compilers put a lot of effort into optimising polymorphic behaviour, but less so into optimising use of RTTI.

---

Related Topics