gamedevlists-general

[GD-General] Multiple Inheritance and RTTI

[Oscar C. <osc...@cr...>]

Hi people,

Apologies for the length of this post. I'm interested in hearing about
real-world experiences of using run-time type information with multiple
inheritance in cross-platform (PC, PS2, Xbox, NGC) C++ games.

The situation I'm considering is where all game entities are derived from a
common Entity base class, and implement zero, one or more interface base
classes. I've got a pointer to an Entity object. I want to know if it
supports a particular interface, and get a pointer to that interface if it
is supported.

I'm guessing that there will be less than a hundred derived classes, no more
than thirty two interfaces, and a few hundred object instances at any given
time. I'd expect there to be less than a thousand interface queries per
frame, but this is the least well known metric. Clearly there are a number
of approaches available, but I have no hard facts to suggest which is likely
to be most appropriate.

Out-of-the-box C++ provides the solution by enabling RTTI language support
and using dynamic_cast:

    IRenderable* const renderable = dynamic_cast<IRenderable*>(entity);

    if (renderable != 0)
        renderable->Render();

On the plus side, this is simple and bug-free. However, I've received very
mixed messages about the virtues and vices of dynamic_cast. Some people say
it bloats code, others say it's lean and mean. Some say it's lightning fast,
others that it's appallingly slow. I've never used it heavily enough to
notice a hit.

The next most simple approach seems to be for the Entity base class to
provide a virtual accessor function for each interface, which returns NULL
by default but can be overriden by a derived class:

    IRenderable* const renderable = entity->GetIRenderable();

    if (renderable != 0)
        renderable->Render();

One major drawback here seems to be that the vtable for each Entity class
will be bloated by over a hundred bytes, which seems like a bad move for
cache limited situations.

Finally, the Entity base class could provide a single virtual accessor
function that takes an interface identifier as a parameter:

    IRenderable* const renderable = reinterpret_cast<IRenderable*>(
        entity->QueryInterface(IID_IRenderable));

    if (renderable != 0)
        renderable->Render();

There are two obvious implementations of this method: The derived class
either implements the function as conditional code, or maintains some kind
of look-up table. The former seems more favourable as a cross-platform
solution, again for cache reasons, but contains the most implementation
pitfalls.

Any of these methods could be supplemented with an inexpensive test for
interface support by adding a constant data overhead to each Entity object
(in this case, four bytes). Each interface is assigned an identifier, which
corresponds to a single bit in a bitfield owned by the base class:

    class Entity {
        public: enum InterfaceID { IID_IRenderable = 0x00000001 ,
IID_ICollideable = 0x00000002 };
        public: bool SupportsInterface (const InterfaceID iid) const {
return ((m_iid & iid) != 0); }
        protected: Entity (const unsigned int iid) : m_iid(iid) {};
        private: unsigned int m_iid;
    };

So, has anyone tried more than one of these approaches and found one to be
superior to the other(s) in production code? Are there any other ways to
achieve the same results which may be more suitable? Does anyone have any
tricks or tips they'd like to share?

Cheers,

Oscar Cooper.
Creature Labs.

Re: [GD-General] Multiple Inheritance and RTTI

[Noel L. <ll...@co...>]

On Tue, 04 Feb 2003 10:42:59 +0000
Oscar Cooper <osc...@cr...> wrote:

> I'm guessing that there will be less than a hundred derived classes, no more
> than thirty two interfaces, and a few hundred object instances at any given
> time. 

dynamic_cast is OK. It will do exactly what you want, and I don't expect
it to be so slow as to be noticeable in your case. However, you will be
forced to turn RTTI on for all your classes, which you might not want to
do. Also RTTI code and non-RTTI code don't like to mix, so if you're
using external libraries that don't have RTTI, that might just decide it
for you.

> Finally, the Entity base class could provide a single virtual accessor
> function that takes an interface identifier as a parameter:
> 
>     IRenderable* const renderable = reinterpret_cast<IRenderable*>(
>         entity->QueryInterface(IID_IRenderable));
> 

That's a good, simple approach. It's so simple that there's no need to
involve C++ RTTI. Like somebody else mentioned, I recommend you use only
one function to get all your interfaces instead of one function per
interface. That what I use also.

That way you get no bloating of vtables and it's a cleaner interface
(although you'll have to cast the returned pointer from void * to
whatever you want).

> There are two obvious implementations of this method: The derived class
> either implements the function as conditional code, or maintains some kind
> of look-up table. The former seems more favourable as a cross-platform
> solution, again for cache reasons, but contains the most implementation
> pitfalls.

I just did it with conditional statements. They seemed to be just fine.
 
> Any of these methods could be supplemented with an inexpensive test for
> interface support by adding a constant data overhead to each Entity object
> (in this case, four bytes). Each interface is assigned an identifier, which
> corresponds to a single bit in a bitfield owned by the base class:

That's an interesting optimization. I doubt you will need it calling it
only 1000 times per frame but it's worth keeping in mind. I guess it
depends whether most of your objects inherit from a lot of the
interfaces or just a couple.

Also, if you do that, you'll be forced to come up with some way of
giving unique identifiers to each interface, which is not trivial,
especially if other people are extending your code. You might have to
register interfaces somehow and all that bookkeeping.

> So, has anyone tried more than one of these approaches and found one to be
> superior to the other(s) in production code? Are there any other ways to
> achieve the same results which may be more suitable? Does anyone have any
> tricks or tips they'd like to share?

That's pretty much it. You've covered all the main points.

I found the book Inside COM to be extremely enlightening. The author
goes step by step developing a COM-like approach (until it becomes
full-blown COM), which is pretty much what you want to see.

You can check out one of my articles in Game Programming Gems 2. It
talks about exactly this topic, and it provides some sample code
(although it seems you have figured it all of it by yourself already).

Finally, at the danger of blowing my own trumpet too much, I have a
whole chapter dedicated to this in my upcoming book "C++ for Game
Programmers" (http://www.amazon.com/exec/obidos/ASIN/1584502274)


--Noel
ll...@co...

Re: [GD-General] Multiple Inheritance and RTTI

[brian s. <pud...@po...>]

I would 3rd the recommendation for Inside COM, and point out that there 
are some other tricks you can pull off with a QueryInterface approach 
that can't be achieved with dynamic_cast (or rather, I don't see how to 
achieve them).  

The most useful one to my mind is aggregation.  An object can be built 
as a collection of other objects (has-a rather than is-a), and those 
objects can delegate all QI calls to their parent.  By doing this, given 
one interface pointer from the parent object, you can cross-cast to 
another interface, even though those 2 interfaces are implemented in 
separate classes.  A rotten example:

class COneTwo : public IUnknown {
    IOne * mOne;
    ITwo * mTwo;
    ...
}

With aggregation, one can get an IOne interface off the COneTwo object, 
and then get an ITwo interface off that IOne interface.  But the actual 
implementations of IOne and ITwo are in completely different classes.

When you picture being able to bolt on orthogonal behavior to objects, 
like combining IDebugRender with objects that implement other 
interfaces, this gets more interesting.  No more do you have to put 
IDebugRender near the top of your inheritance tree; you just give an 
implementation to objects that need it, without modifying the 
implementation of the other interfaces that the object supports.  Groovy!

ATL Internals is a great book to read if you want to set up your COM 
system to support this and other such exotica (tear-off interfaces, etc).

Question: there were references to code bloat produced by RTTI.  Is that 
really a big issue?  It's just some bytes added per vtable - I'm 
wondering if anyone's measured it to come up with a more exact number 
than that.  My gut feeling is that it wouldn't be that significant, but 
I'm wondering if my gut is lying...or maybe the feeling in my gut is 
really coming from the Mexican food I had at lunch...

--brian

Noel Llopis wrote:

>I found the book Inside COM to be extremely enlightening. The author
>goes step by step developing a COM-like approach (until it becomes
>full-blown COM), which is pretty much what you want to see.
>
>You can check out one of my articles in Game Programming Gems 2. It
>talks about exactly this topic, and it provides some sample code
>(although it seems you have figured it all of it by yourself already).
>
>Finally, at the danger of blowing my own trumpet too much, I have a
>whole chapter dedicated to this in my upcoming book "C++ for Game
>Programmers" (http://www.amazon.com/exec/obidos/ASIN/1584502274)
>
>
>--Noel
>ll...@co...
>
>  
>

Re: [GD-General] Multiple Inheritance and RTTI

[Noel L. <ll...@co...>]

On Tue, 04 Feb 2003 14:43:36 -0800
brian sharon <pud...@po...> wrote:

> Question: there were references to code bloat produced by RTTI.  Is that 
> really a big issue?  It's just some bytes added per vtable - I'm 
> wondering if anyone's measured it to come up with a more exact number 
> than that. 

You are right, it is probably not all that significant. I haven't
measured it, and it can vary from implementation to implementation, but
it's not going to amount to a lot of memory.

Most implementations add one extra entry to the vtable to every class
that already has a vtable (if a class doesn't, you're not treating it
polymorphically, so you don't need RTTI). So that's one dword per class.
Big deal.

In addition to that you have the actual information kept by each class.
At least it's going to be the information contained in the type_info
structure: decorated class name and sequence number. It probably has
some other internal data. Even so, we're probably talking about 100
bytes per class? 

At a round 128 bytes per class, if you have 1000 classes with virtual
functions, it will take 128 KB. So it's not totally peanuts in the case
of a console with 32 MB or even 64 MB, but it's not a huge amount.

Still, that's with 1000 different polymorphic classes, which is probably
way on the high end for a normal game today. I'd guess that a lot of
games are only using more on the order of a hundred polymorphic classes,
which brings it down to a more reasonable 15-20 KB.

Having said all that, I still don't like using C++'s RTTI for getting
the interface pointers to classes. I prefer using the custom
QueryInterface function we talked about. And for regular RTTI, I much
prefer a custom system. They are so simple to implement too, that with
the added flexibility they provide, there's almost not reason not to.


--Noel
ll...@co...

Re: [GD-General] Multiple Inheritance and RTTI

[Thatcher U. <tu...@tu...>]

On Feb 04, 2003 at 10:42 -0000, Oscar Cooper wrote:
> 
> On the plus side, this is simple and bug-free. However, I've received very
> mixed messages about the virtues and vices of dynamic_cast. Some people say
> it bloats code, others say it's lean and mean. Some say it's lightning fast,
> others that it's appallingly slow. I've never used it heavily enough to
> notice a hit.

It's slow if you use it too much; we've seen some horrible
dynamic_cast<> spikes in VTune.

> The next most simple approach seems to be for the Entity base class to
> provide a virtual accessor function for each interface, which returns NULL
> by default but can be overriden by a derived class:
> 
>     IRenderable* const renderable = entity->GetIRenderable();
> 
>     if (renderable != 0)
>         renderable->Render();
> 
> One major drawback here seems to be that the vtable for each Entity class
> will be bloated by over a hundred bytes, which seems like a bad move for
> cache limited situations.

My personal recommendation is to use a combination of this, and
dynamic_cast<>.  Use dynamic_cast<> for the rarer situations, and use
GetInterfaceX() for the cases where you want to call it frequently.
This should require fewer interfaces than the full number of
interfaces in your code, so less vtable bloat.

Although I concur with most of the other comments in the thread -- any
of these approaches should work, and I don't think there's any
super-nice one you left out.

Re combining approaches, you could cook up some template trickery to
avoid exposing the optimization to the client code:

----

// In the Entity header:

class DerivedClass;	// forward opaque decl

class Entity {
public:
	virtual DerivedClass*	GetDerivedClass();
};

template<class T>
T DynamicCastFast(Entity* e)
{
       	return dynamic_cast<T>(e);
}

// Here's a specialization, to avoid dynamic_cast when we're casting
// to DerivedClass*.
template<DerivedClass*>
DerivedClass*	DynamicCastFast(Entity* e)
{
	return e->GetDerivedClass();
}


// Off in its own header...
class DerivedClass : virtual public Entity
{
	DerivedClass*	GetDerivedClass() { return this; }
};

// Client code does this, and doesn't have to care whether the
// shortcut is implemented or not:
{
	DerivedClass*	dc = DynamicCastFast<DerivedClass*>(entity);
}

-- 
Thatcher Ulrich
http://tulrich.com