What can make C++ RTTI undesirable to use?

Question

Looking at the LLVM documentation, they mention that they use "a custom form of RTTI", and this is the reason they have isa<>, cast<> and dyn_cast<> templated functions.

Usually, reading that a library reimplements some basic functionality of a language is a terrible code smell and just invites to run. However, this is LLVM we're talking of: the guys are working on a C++ compiler and a C++ runtime. If they don't know what they're doing, I'm pretty much screwed because I prefer clang to the gcc version that ships with Mac OS.

Still, being less experienced than them, I'm left wondering what are the pitfalls of the normal RTTI. I know that it works only for types that have a v-table, but that only raises two questions:

• Since you just need a virtual method to have a vtable, why don't they just mark a method as virtual? Virtual destructors seem to be good at this.
• If their solution doesn't use regular RTTI, any idea how it was implemented?

Answer 1

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

Answer 2

The LLVM coding standards seem to answer this question fairly well:

In an effort to reduce code and executable size, LLVM does not use RTTI (e.g. dynamic_cast<>) or exceptions. These two language features violate the general C++ principle of "you only pay for what you use", causing executable bloat even if exceptions are never used in the code base, or if RTTI is never used for a class. Because of this, we turn them off globally in the code.

That said, LLVM does make extensive use of a hand-rolled form of RTTI that use templates like isa<>, cast<>, and dyn_cast<>. This form of RTTI is opt-in and can be added to any class. It is also substantially more efficient than dynamic_cast<>.

Answer 3

Here is a great article on RTTI and why you might need to roll your own version of it.

I'm not an expert on the C++ RTTI, but I have implemented my own RTTI as well because there are definitely reasons why you would need to do that. First, the C++ RTTI system is not very feature-rich, basically all you can do is type casting and getting basic information. What if, at run-time, you have a string with the name of a class, and you want to construct an object of that class, good luck doing this with C++ RTTI. Also, C++ RTTI is not really (or easily) portable across modules (you cannot identify the class of an object that was created from another module (dll/so or exe). Similarly, the C++ RTTI's implementation is specific to the compiler, and it typically is expensive to turn on in terms of additional overhead to implement this for all types. Finally, it is not really persistent, so it can't really be used for file saving/loading for example (e.g. you might want to save the data of an object to a file, but you would also want to save the "typeid" of its class, such that, at load time, you know which object to create in order to load this data, that cannot be done reliably with C++ RTTI). For all or some of these reasons, many frameworks have their own RTTI (from very simple to very feature-rich). Examples are wxWidget, LLVM, Boost.Serialization, etc.. this really isn't that uncommon.

Since you just need a virtual method to have a vtable, why don't they just mark a method as virtual? Virtual destructors seem to be good at this.

That's probably what their RTTI system uses too. Virtual functions are the basis for dynamic binding (run-time binding), and thus, it is basically required for doing any kind of run-time type identification/information (not just required by the C++ RTTI, but any implementation of RTTI will have to rely on virtual calls in one way or another).

If their solution doesn't use regular RTTI, any idea how it was implemented?

Sure, you can look up RTTI implementations in C++. I have done my own and there are many libraries that have their own RTTI as well. It is fairly simple to write, really. Basically, all you need is a means to uniquely represent a type (i.e. the name of the class, or some mangled version of it, or even a unique ID for each class), some sort of structure analogous to type_info that contains all the information about the type that you need, then you need a "hidden" virtual function in each class that will return this type information on request (if this function is overriden in each derived class, it will work). There are, of course, some additional things that can be done, like a singleton repository of all types, maybe with associated factory functions (this can be useful for creating objects of a type when all that is known at run-time is the name of the type, as a string or the type ID). Also, you may wish to add some virtual functions to allow dynamic type casting (usually this is done by calling the most-derived class' cast function and performing static_cast up to the type that you wish to cast to).

Answer 4

The predominant reason is that they struggle to keep memory usage as low as possible.

RTTI is only available for classes which feature at least one virtual method, which means that instances of the class will contain a pointer to the virtual table.

On a 64-bits architecture (which is common today), a single pointer is 8 bytes. Since the compiler instantiate lots of small objects, this adds up pretty quickly.

Therefore there is an ongoing effort to remove virtual functions as much as possible (and practical), and implement what would have been virtual functions with the switch instruction, which has similar execution speed but a significantly lower memory impact.

Their constant worry for memory consumption has paid off, in that Clang consumes significantly less memory than gcc, for example, which is important when you offer the library to clients.

On the other hand, it also means that adding a new kind of node usually results in editing code in a good number of files because each switch need to be adapted (thankfully compilers issue warning if you miss an enum member in a switch). So they accepted to make maintenance a tad more difficult in the name of memory efficiency.