RTTI Sniping

As observed with vptr jamming, the polymorphic behavior of an object instance is controlled by what vtbl[] its vptr is pointing too. It's not a big leap from that to realize that by testing the value in the vtbl[], the type of the object can be determined.

The usual way to determine the derived type of an object is by doing a dynamic_cast. If the dynamic_cast to a derived class succeeds, it returns a pointer to the derived class. If it fails, it returns NULL:

dynamic_cast is slooooww. For example:

struct A
{
    virtual int foo();
};

struct B : A
{
    int foo();
};

int test(A *a)
{
    return dynamic_cast<B*>(a) != 0;
}

Here's the generated assembly code for the test to see if a is really an instance of B:

mov     EAX,4[ESP]
test    EAX,EAX
je      L24
push    0
push    offset FLAT:___ti?AUB@@
push    offset FLAT:___ti?AUA@@
push    EAX
mov     ECX,[EAX]
push    dword ptr -4[ECX]
call    near ptr ?__rtti_cast@@YAPAXPAX0PBD1H@Z
add     ESP,014h
jmp short       L26
L24:    xor     EAX,EAX
L26:    neg     EAX
sbb     EAX,EAX
neg     EAX
ret

There are lots of instructions being executed, and a function call. It also relies on RTTI being generated for the class, which is bbllooaatt.

If only we could snipe the RTTI and figure out the type directly. If we've got the need for speed, we can do the following:

B tmp;

int test(A *a)
{
    return *(void**)a == *(void**)&tmp;
}

All this does is compare the vptr in a with the vptr in tmp. Most compilers put the vptr as the first member in a class most of the time, so this will work. When it doesn't, adjust the offset to a and &tmp to match.

The generated assembler code looks like:

mov     EAX,4[ESP]
mov     ECX,[EAX]
cmp     ECX,?tmp@@3UB@@A
mov     EAX,1
je      L15
xor     EAX,EAX
L15:    ret

Holy hotrod, Batman! That brought the test for the type down to two instructions. We can even do slightly better. The Digital Mars C++ compiler has special support for RTTI sniping with the __istype pseudo member function:

int test(A *a)
{
    return a->__istype(B) != 0;
}

and we're down to one instruction:

mov     EAX,4[ESP]
cmp     dword ptr [EAX],offset FLAT:??_QB@@6B@[4]
mov     EAX,1
je      L13
xor     EAX,EAX
L13:    ret

The obvious question is, why doesn't dynamic_cast produce the short, fast code? The answer is that RTTI sniping only works if the class type being tested for is the most derived class in the class heirarchy (because that determines the vtbl[]), whereas dynamic_cast needs to work for any derived class.

Once again, there are problems with RTTI sniping:

Some implementations are able to share vtbl[]s between classes, so the vptr for class B and class A, where B is derived from A, point to the same value. This clever compiler optimization must be defeated, sometimes it can be via a switch to "turn on RTTI", or by some other switch. Worst case, avoid using RTTI sniping between classes derived from one another.
Some (generally older) compilers can generate multiple vtbl[]s for the same class, so that two vptrs can hold different addresses, but still be the same type. Fortunately, such compilers are rarely used these days. But the problem can still crop up if one DLL generates one instance while another DLL generates another. The moral is to have all the constructors for a particular object implemented in one source file, and have that be only in one DLL, not many.

The Counterfeit `this`

The two conventional methods for hiding the implementation of a class are:

Declare the implementation as private:
```
#include "implementation.h"

class Foo
{
private:
    ... the implementation ...

// the interface
public:
    void bar()
    {
        ... manipulate the implementation ...
    }
};
```
The trouble with this, of course, is that the implementation is still there with its bare face hanging out, and in order to compile it, every irrelevant thing that the implementation needs has to be in scope, too.

Use the PIMPL idiom as described by Herb Sutter, where the class contains a pointer to the implementation of the class:

// User sees this class definition

class Implementation;       // stub definition

class Foo
{
private:
    Implementation *pimpl;

// the interface
public:
    Foo();

    void bar();
};

// Separate, hidden version of Foo

#include "implementation.h"

Foo::Foo() : pimpl(new Implementation())
{
}

void Foo::bar()
{
    pimpl->bar();
}

This succeeds in hiding the implementation details, at the cost of another layer of allocation and an extra object instance.

But there's a way to hide the implementation completely without having an extra object. The idea is to counterfeit the this pointer, so that the user thinks it is one type, but the implementation knows it is another:

// User sees this class definition
class Foo
{
// the interface
public:
    Foo *factory(); // create and initialize an instance

    void bar();
};

// Separate, hidden version of Foo

#include "implementation.h"

Foo *Foo::factory()
{
    return reinterpret_cast<Foo *>new Implementation();
}

void Foo::bar()
{
    (reinterpret_cast<Implementation *>this)->bar();
}

The reinterpret_cast is doing the dirty work of counterfeiting the type of the object from Implementation to Foo and back again.

Caveats:

The class Foo cannot have any data members, even hidden ones like a vptr. Therefore, it cannot have any virtual functions.
Foo cannot have any constructors, because we aren't constructing a real Foo, only a counterfeit one.

Conclusion

C++ provides great tools for under the hood optimization, but its use is uniformly and actively discouraged. If you're willing to accept that you're going outside all recommended practice, there are some neat things to be done to hotrod your C++ application.

These techniques are also applicable to the D programming language[1].

Sometimes, you just feel the need for speed.

Talk back!

Have an opinion on the ideas presented in this article? Please post them in the forum topic for this article, Backyard Hotrodding C++.

Notes and References

http://www.digitalmars.com/d/index.html.

About the Author

Walter Bright graduated from Caltech in 1979 with a degree in mechanical engineering. He worked for Boeing for 3 years on the development of the 757 stabilizer trim system. He then switched to writing software, in particular compilers, and has been writing them ever since.

<< Page 3 of 3