To RTTI, or not to RTTI?

Someone once told me “If you need to use RTTI then your design is wrong.”

I find that when you meet someone who says stuff like this, the best thing to do is tell them that – having tried both approaches – you totally prefer inheritance to composition; and then sneak away under cover of  the resulting self-righteousness mushroom cloud.

 

Pragmatic? Moi?!?

In game programming we often end up inhabiting an interesting middle ground between engineering best practice and the practicality of getting the job done so we can hit the milestone and keep the company afloat.

In addition to this issue, the Object Oriented goal of localising the logical behaviour of an object into a class that contains the data that it operates on is sometimes at odds with sensibility as well as the other goals of OOP.

For example; I’ve lost track of the number of seemingly well thought out state machine manager classes I’ve seen which, when put into use, produce a system of state classes whose logic about state transitions is so decentralised amongst the various states that it actively works against the maintainability of the code.

For me the issues surrounding use of RTTI are less about philosophy, and more about pragmatics.

There are plenty of situations where you can entirely work around a problem without using typeid or dynamic_cast; but there are also situations where the solution that doesn’t require them involves:

  1. too many layers of abstraction to be readily digested at a later date by anyone who didn’t write the code in the first place, and / or
  2. too much refactoring of existing code given the time and / or
  3. is too risky given the current situation (e.g. in the final run-up to mastering)

In any of these situations I say: “Go for your life; but for the love of Bob please don’t use typeid or dynamic_cast<>.”

 

What’s wrong with typeid and dynamic_cast<>?

Well, there’s nothing actually wrong with them as such; they work as intended, and it’s not like they go around stamping on kittens or anything…

However, you need to leave RTTI turned on to use them; which uses extra memory for typeid (up to 40 bytes per class with virtual functions according to wikipedia, so not actually that  bad), and dynamic_cast<> “can be pretty slow” and definitely isn’t constant time.

To be honest, I – and the other programmers who were founding members of FreeStyleGames – always felt the RTTI functionality was (is)  just another little thing that people will tend to misuse if left to their own devices – so we always turned it off. I still do so now.

At the end of the day, using it has some small fixed and not so fixed penalties, and not using it doesn’t. That was enough to make up my mind for me.

Either way, I’m not writing this to argue coherently about whether you should or shouldn’t use the default C++ RTTI; that’s well trodden ground, people have their opinions and let’s just accept that I’ve decided to live on the side of the fence where we turn it off and use the extra memory for something more useful like storing user defined 1s and 0s.

 

So, what about this type id then?

So, assuming that you’re someone who’s sold on not using RTTI; and that you have a situation where you feel that your best-available-solution requires it (or something like it) then I hope what follows is useful – let’s get on with it shall we?

 

What do we want from our type id?

Firstly, our type id – let’s call it altTypeId – needs to resolve to a unique value for each type that we ask it to give us an altTypeId for.

Secondly, the value it gives for each type needs to be constant throughout the duration of each instance of the execution of our program.

Finally, I think it’s fair to say that it should to usable in a typeid alike fashion.

template and #define are your friends

Unsurprisingly, given that this problem requires a unique value per type we’re going to use a template.

Even more unsurprisingly, since the solution uses a template, we’re going to need a #define macro to wrap it so your code doesn’t become a hideous mess of angle brackets and scope operators.

Volia! Le code est ici!

Let’s start at the beginning, we need a type to hold altTypeId.

It’s pretty unlikely that any code base is going to have more than 0xFFFFFFFF types in total, and the number that might need to be resolved using a type id should be smaller than the total number. This makes an unsigned int (assuming it to be 32bit) a sensible choice.

1
2
// typedef for altTypeId as unsigned int
typedef unsigned int altTypeId;

Ok, so the next part is we need some way to generate unique values for these altTypeIds. My solution to this is a class that contains a single static function which returns 0 the first time it’s called, and then 1 the next, then 2, and so on.

This is only a class because I want to make all of its functionality protected and hide the ability to generate altTypeIds away from anything not derived from it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class CAltTypeIdGen_Base
{
public:
    enum{ ALTTYPEID_INVALID = 0xFFffFFff };
 
protected:
    // generates type Id values starting from 0
    // you would probably want to put this in a .cpp in case you want to use it in a library
    static altTypeId GenerateAltTypeId()
    {
        static altTypeId s_uNextClassID = 0;
        return s_uNextClassID++;
    }
 
    // only constructible from derived types
    CAltTypeIdGen_Base()
    {}
};

I’m assuming that you’re thinking “What?” at this point. The above class doesn’t make a lot of sense without the template that turns it into a one-number-per-type system. Here it is…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template< typename T >
class TAltTypeIdGen : public CAltTypeIdGen_Base
{
public:
    // this generates a typeID for each class that instantiates the template
    static altTypeId GetAltTypeId()
    {
        static altTypeId s_uClassId = GenerateAltTypeId();
        return s_uClassId;
    }
 
    private:
    // no instance of this class can be created.
    TAltTypeIdGen()
    {}
};

Now we have a way of generating a unique altTypeId for each type in the code base – this template type cannot be constructed, and the internal static data of its only accessible function can only be initialised once. Joy.

To finish it off I’ve added a macro that makes it less visually traumatic to use, and a template function that extracts the altTypeId from an instance of a type which is pretty helpful too.

1
2
3
4
5
6
7
8
9
10
11
12
// define to make CAltTypeIdGen_Base::ALTTYPEID_INVALID less visually traumatic
#define ALTTYPEID_INVALID CAltTypeIdGen_Base::ALTTYPEID_INVALID 
 
// macro for getting hold of a type's altTypeId
#define GetAltTypeIdOf( TYPENAME ) ( TAltTypeIdGen< TYPENAME >::GetAltTypeId() ) 
 
// resolves to the correct form of TAltTypeIdGen< T >::GetAltTypeId()
template< typename T >
altTypeId GetAltTypeIdOfInstance( T instance )
{
    return TAltTypeIdGen< T >::GetAltTypeId();
}

That was easy, right? Now we can use the altTypeId to make decisions based on the type of variables e.g.:

1
2
3
4
5
int iDemo = 0;
if( GetAltTypeIdOf( int ) == GetAltTypeIdOfInstance( iDemo ) )
{
    // do stuff
}

But… that’s not really useful for anything… is it?

Busted! Ok, so the astute amongst you will have noticed that so far altTypeId is not really mega useful…

So, the first thing to note about what I’ve shown here is that it isn’t a straight replacement for typeid, and it definitely isn’t a straight replacement for dynamic_cast<>. It does however definitely let you solve the majority of problems whose alternate solutions might involve these two C++ language features.

The main limitation of altTypeId is that – without a little extra stitching into your code – can’t be used to do any reasoning about the actual types of objects pointed to by a pointer of a base type.

This is for two reasons:

  1. templates can only operate on what you instantiate them with at compile time – so a pointer to a type will give you a different altTypeId than an instance of the type would, and
  2. a pointer to a base class will always yield the altTypeId of a pointer to a base class – there’s no polymorphic cleverness in altTypeId

To be honest I’m pretty sure that some template black magic could fix the first issue, but I’ve never bothered to because there are lots of reasons type id should maintain the differentiation between the type of an instance and the type of a pointer to that instance. Apart from anything else type and type* are actually different types…

The second issue is definitely fixable – you could either:

  1. have a (pure) virtual function in the base type that returns an altTypeId and implement it in all deriving classes to return their actual altTypeId, or
  2. have a base class that has an altTypeId as a member which is set by an argument to its constructor when derived classes are constructed. This way is more tedious to write, as you have to chain the constructors down the hierarchy if there is > 1 level of derivation from the base class. However it has no virtual function overhead for getting at the altTypeId.

I’ve used both of these approaches myself, and they’re both fine – though the second one takes more explaining to get people to do it correctly.

Summary

The code is here if you want to just download it: http://codepad.org/uqoOP7WW.

Hopefully this was of some interest and not so bleedingly obvious that you, dear reader, were wondering why I bothered to post it.

I’ve had occasion to use this code maybe 4 or 5 times over the years since I originally wrote it and each time I dig it out I usually make a couple of tweaks so this is relatively mature code (I know it’s tiny, but it’s changed quite a lot from the original implementation!).

I’m 99.9% sure that with some extra template magic it could be made into something a lot cleverer – in fact I know it can because I built a reflection system off it, but I can’t give you the source to that since it belongs to Activision.

Incidentally, if you’re interested in templates I highly recommend the book “Modern C++ Design” by Andrei Alexandrescu, the reflection code I wrote drew heavily on this book. Ironically it’s 10 years old now and will probably still blow your mind gaskets unless you’re the kind of person who programs entirely in templates and contributes to boost. Some of the stuff in there is pure genius, and yet it’s almost entirely unused in games where its use would make things good ™ (e.g. policy based design).

Final thought; solutions 1 & 2 in the previous section would also work with an enum containing a value for all derived types of the base class instead of a fancy templatey solution, but if you do it that way you will make Bjarne Stroustrup cry.

Epilogue, or The Benefit of Peer Criticism

Following on from comments made on this by Unai Lander, Michael Nicolella, and Nicolas Silva I have added this epilogue.

Unai suggested a more elegant solution, Michael pointed out a couple of possible issues with run time efficiency of the solution I posted originally, and Nicolas spotted what I was getting at with the phrase “template black magic” – specifically if you want const int, volatile int, and int to return the same altTypeId you will need to use a technique called “qualifier stripping” which uses partial template specialisation and is covered in detail in the Andrescu book “Modern C++ Design”, page 44 [2.10.4 Stripping Qualifiers].

Unai’s solution removes the need to have the base type for the template Id generator type. Like many really elegant solutions it seems bleedingly obivous when you see it :)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef unsigned int altTypeId;
 
template< typename T >
class TAltTypeIdGenerator
{
private:
    // no instance of this class can be created.
    TAltTypeIdGenerator()
    {}
 
public:
    // this generates a typeID for each class that instantiates the template
    static altTypeId GetAltTypeId()
    {
        // I wasn't sure if the char would take up > 1 byte because of alignment.
        // With VS2010 on win32 they take up exactly 1 byte each (and in the pastebin too...)
        static char chAddressOfThisIsTheTypeId;
        return reinterpret_cast< altTypeId >( &chAddressOfThisIsTheTypeId );
    }
};

Michael pointed out that using a function local static introduces the overhead of conditional branching into the function, which is bad for obvious reasons.

So, I did a little empirical experimentation (in VS2010) to see what the assembler did for various cases of function local statics and here’s what I found:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int functionNotInit( void )     // no branches
{
    static int iNotInit;
    return iNotInit;
}
 
int functionNotInitInc( void ) // no branches
{
    static int iNotInit;
    return iNotInit++;
}
 
int functionInitZero( void ) // no branches
{
    static int iInit = 0;
    return iInit;
}
 
int functionInitZeroInc( void )    // no branches
{
    static int iInit = 0;
    return iInit++;
}
 
int functionInitFunction( void ) // conditional branch to call SetValue on first time through
{
    static int iInitFromFunc = SetValue();
    return iInitFromFunc;
}

So, the upshot is that (as an uninitialised function local static appears to have no branch overhead associated with it) I have revised the code to use Unai’s method and whacked the new version into a paste bin for your pleasure here:

http://codepad.org/RXZfzCpo

Thanks to Unai, Michael, and Nicolas :)