Is there any faster way than dynamic_cast to find the object run time type?

S

steve

I am writing for game application. Performance is an issue.

Any advise would be appreiciated.
 
J

JKop

Jason Heyes posted:
Yea. Put the type into the base class.

No No No! This is clearly an instance in which one would
work with a pointer to a pointer to the *DERIVED CLASS*! To
put the type in the base clase is simply ludicrious!

-JKop
 
I

Ioannis Vranos

steve said:
I am writing for game application. Performance is an issue.

Any advise would be appreiciated.



Perhaps sections 15.4.4, 15.4.4.1 and 15.4.5 in TC++PL 3 can be useful
to you.
 
I

Ioannis Vranos

steve said:
I am writing for game application. Performance is an issue.

Any advise would be appreiciated.



Perhaps sections 15.4.4, 15.4.4.1 and 15.4.5 in TC++PL 3 can be useful
to you.
 
P

PKH

steve said:
I am writing for game application. Performance is an issue.

Any advise would be appreiciated.

I'm using the following approach in a game I'm working on. By inlining the
RequestClass functions it should be quite fast. (I posted this earlier in
another thread )


typedef char ClassID;

class CClassIDBase
{
public:
static ClassID
m_cClassID;

virtual CClassIDBase* RequestClass(const ClassID& c)
{
return (&c == &m_cClassID) ? this : NULL;
}
};


class CCow : public CClassIDBase
{
public:
static ClassID
m_cClassID;

public:
void EatGrass(){}
virtual CClassIDBase* RequestClass(const ClassID& c)
{
return (&c == &m_cClassID) ? this : CClassIDBase::RequestClass(c);
}
};


class CBrow : CClassIDBase
{
public:
static ClassID
m_cClassID;

CCow
m_cCow;

public:
virtual CClassIDBase* RequestClass(const ClassID& c)
{
if (&c == &CCow::m_cClassID)
{
return &m_cCow;
}
else
{
return (&c == &m_cClassID) ? this : CClassIDBase::RequestClass(c);
}
}
};


ClassID
CClassIDBase::m_cClassID = 0,
CCow::m_cClassID = 0,
CBrow::m_cClassID = 0;


int main(int argc, char* argv[])
{
CCow
*pcCow;

CBrow
cBrow;

if ((pcCow = (CCow*)cBrow.RequestClass(CCow::m_cClassID)) != NULL)
{
pcCow->EatGrass();
}

return 0;
}
 
N

Niklas Borson

steve said:
I am writing for game application. Performance is an issue.

Any advise would be appreiciated.

Well, the first bit of advice would be to carefully consider whether
you actually need to know the actual type. In general, you should try
to design things so that when you have, say, a pointer-to-Shape you
only need to do Shape things to it and don't really care whether the
object's actual type is Triangle, Ellipse, or Rhombus.

However, assuming you've already considered all that and really do
need to know the type, you have two choices: dynamic_cast and typeid.
It's possible that one is faster than the other. You should probably
test both and see.

They do slightly different things: dynamic_cast will tell you whether
the object's type is *compatible* with the specified type; typeid
tells you the specific type. The following program illustrates the
difference:

#include <iostream>

class A { public: virtual ~A() {} };
class B : public A {};
class C : public B {};

#define TEST(expr) std::cout << #expr " --> " << (expr) << '\n'

int main()
{
C obj;
A* p = &obj;
TEST( dynamic_cast<B*>(p) != 0 );
TEST( dynamic_cast<C*>(p) != 0 );
TEST( typeid(*p) == typeid(B) );
TEST( typeid(*p) == typeid(C) );
return 0;
}

The output is:

dynamic_cast<B*>(p) != 0 --> 1
dynamic_cast<C*>(p) != 0 --> 1
typeid(*p) == typeid(B) --> 0
typeid(*p) == typeid(C) --> 1

--Nick
 
P

Peter Koch Larsen

PKH said:
I'm using the following approach in a game I'm working on. By inlining the
RequestClass functions it should be quite fast. (I posted this earlier in
another thread )

[snip]

You answered the question: is it possible to detect the object run time type
without using dynamic_cast. I see that it is. Could you also demonstrate
that it is faster than dynamic_cast? (In that case you should quote the
compiler and settings used)


/Peter
 
P

Peter Koch Larsen

steve said:
I am writing for game application. Performance is an issue.

Any advise would be appreiciated.

Just use dynamic_cast until yoy test it and find if it is to slow. Remember
that the compiler writers do try to make our programs work as fast as
possible.


/Peter
 
P

PKH

Peter Koch Larsen said:
PKH said:
I'm using the following approach in a game I'm working on. By inlining
the
RequestClass functions it should be quite fast. (I posted this earlier in
another thread )

[snip]

You answered the question: is it possible to detect the object run time
type
without using dynamic_cast. I see that it is. Could you also demonstrate
that it is faster than dynamic_cast? (In that case you should quote the
compiler and settings used)


/Peter

I hadn't really tested speed, but needed the extra flexibility the ClassID
approach gives.
After doing a test with upcasting from a basepointer which is what I use
most, I was pleasantly suprised.
It's is quite a lot faster in release on the following code.

On an amd 2500+, VC 6.0 for the following code, the results were

In Debug, ClassID 1.03 secs, Dynamic cast 1.34 secs
In Release ClassID 0.13 secs, Dynamic cast 0.81 secs (inline any suitable,
maximize speed)

I checked that EatGrass() was actually called for both loops in release.
Of course the compiler might do some tricks with this code when optimizing,
but I think I can conclude that ClassID is at least as fast as dynamic_cast
(unless there is some mistake in the code).


#include <windows.h>
#include <conio.h>
#include <stdio.h>


typedef char ClassID;

class CClassIDBase
{
public:
static ClassID
m_cClassID;

inline
virtual CClassIDBase* RequestClass(const ClassID& c)
{
return (&c == &m_cClassID) ? this : NULL;
}
};


class CCow : public CClassIDBase
{
public:
static ClassID
m_cClassID;

public:
void EatGrass(){}
inline
virtual CClassIDBase* RequestClass(const ClassID& c)
{
return (&c == &m_cClassID) ? this : CClassIDBase::RequestClass(c);
}
};


class CSuperCow : public CCow
{
public:
static ClassID
m_cClassID;

public:
inline
virtual CClassIDBase* RequestClass(const ClassID& c)
{
return (&c == &m_cClassID) ? this : CCow::RequestClass(c);
}
};



class CBrow : public CClassIDBase
{
public:
static ClassID
m_cClassID;

CCow
m_cCow;

public:
inline
virtual CClassIDBase* RequestClass(const ClassID& c)
{
if (&c == &CCow::m_cClassID)
{
return &m_cCow;
}
else
{
return (&c == &m_cClassID) ? this : CClassIDBase::RequestClass(c);
}
}
};


ClassID
CClassIDBase::m_cClassID = 0,
CCow::m_cClassID = 0,
CSuperCow::m_cClassID = 0,
CBrow::m_cClassID = 0;


int main(int argc, char* argv[])
{
CClassIDBase
*pcBase;

CCow
*pcCow;

CBrow
cBrow;

CSuperCow
cSuperCow;

LARGE_INTEGER
nFreq,
nStartTick,
nEndTick;

BOOL
bRes;

DWORD
i;

float
vFreq,
vClassIDSecs,
vDynamicCastSecs;



bRes = QueryPerformanceFrequency(&nFreq);
vFreq = (float)nFreq.QuadPart;

pcBase = &cSuperCow;

// Class ID
QueryPerformanceCounter(&nStartTick);

for (i = 0; i < 10000000; i++)
{
pcCow = (CCow*)pcBase->RequestClass(CCow::m_cClassID);
if (pcCow)
{
pcCow->EatGrass();
}
}

QueryPerformanceCounter(&nEndTick);
vClassIDSecs = (nEndTick.QuadPart - nStartTick.QuadPart) / vFreq;

// Dynamic_cast
QueryPerformanceCounter(&nStartTick);

for (i = 0; i < 10000000; i++)
{
pcCow = dynamic_cast<CCow*>(pcBase);
if (pcCow)
{
pcCow->EatGrass();
}
}

QueryPerformanceCounter(&nEndTick);
vDynamicCastSecs = (nEndTick.QuadPart - nStartTick.QuadPart) / vFreq;

// You can also do this, which isn't available with dynamic_cast
// since Brow doesn't inherit from cow
if ((pcCow = (CCow*)cBrow.RequestClass(CCow::m_cClassID)) != NULL)
{
pcCow->EatGrass();
}

printf("ClassID: %.2f, DynamicCast: %.2f", vClassIDSecs,
vDynamicCastSecs);

while (!_kbhit());

return 0;
}
 
I

Ioannis Vranos

Niklas said:
Well, the first bit of advice would be to carefully consider whether
you actually need to know the actual type. In general, you should try
to design things so that when you have, say, a pointer-to-Shape you
only need to do Shape things to it and don't really care whether the
object's actual type is Triangle, Ellipse, or Rhombus.

However, assuming you've already considered all that and really do
need to know the type, you have two choices: dynamic_cast and typeid.
It's possible that one is faster than the other. You should probably
test both and see.

They do slightly different things: dynamic_cast will tell you whether
the object's type is *compatible* with the specified type; typeid
tells you the specific type. The following program illustrates the
difference:

#include <iostream>

class A { public: virtual ~A() {} };
class B : public A {};
class C : public B {};

#define TEST(expr) std::cout << #expr " --> " << (expr) << '\n'

int main()
{
C obj;
A* p = &obj;
TEST( dynamic_cast<B*>(p) != 0 );
TEST( dynamic_cast<C*>(p) != 0 );
TEST( typeid(*p) == typeid(B) );
TEST( typeid(*p) == typeid(C) );
return 0;
}

The output is:

dynamic_cast<B*>(p) != 0 --> 1
dynamic_cast<C*>(p) != 0 --> 1
typeid(*p) == typeid(B) --> 0
typeid(*p) == typeid(C) --> 1



One of the interesting things in the chapters that I mentioned in
another message is:


"15.4.5 Uses and Misuses of RTTI

One should use explicit run-time type information only when necessary.
Static (compile-time) checking is safer, implies less overhead, and –
where applicable – leads to better structured programs.

For example, RTTI can be used to write thinly disguised switch-statements:

// misuse of runtime

type information:
void rotate(const Shape& r)
{
if (typeid(r) == typeid(Circle)) {
// do nothing
}

else if (typeid(r) == typeid(Triangle)) {
// rotate triangle
}
else if (typeid(r) == typeid(Square)) {
// rotate square
}
// ...
}


Using dynamic_cast rather than typeid would improve this code only
marginally.

Unfortunately, this is not a strawman example; such code really does get
written. For many people trained in languages such as C, Pascal,
Modula2,and Ada, there is an almost irresistible urge to organize
software as a set of switch-statements. This urge should usually be
resisted. Use virtual functions (§2.5.5, §12.2.6) rather than RTTI to
handle most cases when run-time discrimination based on type is needed."


And other useful stuff.
 
M

Marcin Kalicinski

Hi,
I am writing for game application. Performance is an issue.
Any advise would be appreiciated.

typeid(...) should be a lot faster than dynamic_cast if your class hierarchy
is large, and especially if you are using multiple or virtual inheritance.
From my experience with Visual C++, dynamic_cast on a large
multi-virtual-hierarchy could take as much as 5000 cpu cycles to execute,
while typeid cost is similar to virtual function call.

Anyway, using too much dynamic type checking in your code usually indicates
a design flaw. You should have designed for static type checking instead.

Best regards,
Marcin
 
S

Stephan Br?nnimann

steve said:
I am writing for game application. Performance is an issue.

Any advise would be appreiciated.

I don't think you should avoid the dynamic_cast when casting the
base class pointer/reference to the concrete class.

We are using the following pattern:

class Base {
public:
enum Type {
typeA = 1,
typeB,
// ...
typeX
};
public:
virtual Type type() const = 0;
};

class TypeA : public Base {
public:
Type type() const { return typeA; }
};

// downcasting
void showBase(const Base& base)
{
switch (base.type()) {
case Base::typeA: {
const TypeA* typeA = dynamic_cast<const TypeA*>(base);
if (0 == typeA) throw ...; // somebody cheats!
typeA->typeASpecific();
}
// other cases
...
// no default: let compiler warn
}
}

In the real code things are somewhat more complicated, basically
in order to allow declaration of Base::Type without the need to
include the header file.

Stephan Brönnimann
(e-mail address removed)
Open source rating and billing engine for communication networks.
 
T

Tom Widmer

PKH said:
I'm using the following approach in a game I'm working on. By inlining the
RequestClass functions it should be quite fast. (I posted this earlier in
another thread )

[snip]

You answered the question: is it possible to detect the object run time type
without using dynamic_cast. I see that it is. Could you also demonstrate
that it is faster than dynamic_cast? (In that case you should quote the
compiler and settings used)

dynamic_cast is notoriously slow on MSVC, since string comparisons are
used. Any reasonable home-grown solution will be faster than that.

Obviously, it is best to avoid the need for dynamic_cast full stop, or
at least limit to IO code where performance won't be an issue.

Tom
 
M

Mike Smith

JKop said:
Jason Heyes posted:



No No No! This is clearly an instance in which one would
work with a pointer to a pointer to the *DERIVED CLASS*! To
put the type in the base clase is simply ludicrious!

I think what he means is that the base class could be defined with
either a member variable or virtual function (or both) that can be used
to indicate type, which can be overridden by derived classes.

#define CLASS_ID_BASE 0
#define CLASS_ID_DERIVED_A 1
#define CLASS_ID_DERIVED_B 2
/* ... */

class Base
{
public:
Base() : m_class_id(CLASS_ID_BASE) {}
Base(int a) : m_class_id(a) {}
virtual int GetClassID();
private:
int m_class_id;
};

int Base::GetClassID() {return m_class_id;}

class DerivedA : public Base
{
public:
DerivedA() : Base(CLASS_ID_DERIVED_A) {};
private:
int m_class_id;
};

class DerivedB : public Base
{
public:
DerivedB() : Base(CLASS_ID_DERIVED_B) {};
private:
int m_class_id;
};

and so on. With such a system, an application that has a Base *p can
call p->GetClassID() to obtain type info. The OP indicated that speed
was an issue; in this scenario the program can switch() on the value
returned from GetClassID(), or use it as an array index, etc.
 
X

Xenos

Mike Smith said:
#define CLASS_ID_BASE 0
#define CLASS_ID_DERIVED_A 1
#define CLASS_ID_DERIVED_B 2
/* ... */
Wow, do people still write code like that? How about a little type safety
and easier maintainability?

enum class_id_type {
CLASS_ID_BASE,
CLASS_ID_DERIVED_A,
CLASS_ID_DERIVED_B
};


and so on. With such a system, an application that has a Base *p can
call p->GetClassID() to obtain type info. The OP indicated that speed
was an issue; in this scenario the program can switch() on the value
returned from GetClassID(), or use it as an array index, etc.

You think switching on a class id is "better" or faster than just calling a
virtual member?
 
M

Mike Smith

Xenos said:
Wow, do people still write code like that? How about a little type safety
and easier maintainability?

enum class_id_type {
CLASS_ID_BASE,
CLASS_ID_DERIVED_A,
CLASS_ID_DERIVED_B
};

Yeah, yeah, OK. I was just looking to get something down that explained
the idea, and that's the first thing I thought of.
You think switching on a class id is "better" or faster than just calling a
virtual member?

I was responding to the question raised by the OP. Whether or not there
might be other ways to do what he "really" wants to achieve is a
different question, answering which would require telepathic abilities
on my part.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,900
Latest member
Nell636132

Latest Threads

Top