Efficient run-time type checking in C++

Question

I've two class named 'Expression' and 'BinExp' as following codes:

class Expression
{
public:
    virtual BinExp* IsBinaryExp() { return NULL; }
};
class BinExp : public Expression
{
public:
    virtual BinExp* IsBinaryExp() { return this; }
};

As example, I've a pointer variable type of Expression* but initialized as new BinExp and send as argument to a analyse function as following code:

int main()
{
    Expression* e = new BinExp;
    analyse(e);
}

Inside the analyse function, I need to know whether the e is pointer to Expression type or BinExp type. In my hand, there is three way to do this.

First:

BinExp* be = e->IsBinaryExp();
if ( be )
{
    printf("Yes, `e` is a binary expression\n");
}

Second:

BinExp* be = dynamic_cast<BinExp*>(e);
if ( be )
{
    printf("Yes, `e` is a binary expression\n");
}

And the third:

if ( typeid(*e) == typeid(BinExp) )
{
    BinExp* be = e->IsBinaryExp(); // or dynamic_cast<BinExp*>(e);
    printf("Yes, `e` is a binary expression\n");
}

But I want to know which of those ways ( or any other ) will be more efficient and effective when I need to perform the checking frequently inside a loop where performance is a matter. Any kind of suggestion I will appreciate.

You've written a pretty good question, but you don't specify what kind of platforms you're interested in running on. Between mobile and desktop is a pretty large difference, for example, with cache behaving very differently. — Kaganar, Jan 27 '15 at 14:03
You could always benchmark this sort of thing yourself -- if you're worried about low level performance then you're going to want to have a profiling platform at your disposal anyway. May as well start now. — Kaganar, Jan 27 '15 at 14:04
You have a fourth possibility: Use *visitor*. `dynamic_cast` and *visitor* seems the cleaner for me. — Jarod42, Jan 27 '15 at 14:07
I think that if you have a loop where performance is a matter, you could try redesigning your code so there is no need for RTTI at all, or even better - no need for virtual calls at all. They will trash your cache and do complex magic under-the-hood, which might be a great overkill for distinguishing between unary and binary expression of any kind. — cubuspl42, Jan 27 '15 at 14:08
Are you actually having performance problems? If so, profile. If not, use the construct that most clearly express intent. Design priories are Simplicity, Elegance, Trivially Verifiable Correctness, and, on a very distant 4rth place, Efficiency. — sp2danny, Jan 27 '15 at 14:32

score 3 · Accepted Answer · answered Jan 27 '15 at 14:18

The fastest way would be to keep a member variable , say an enum , then define in the base class a inline getter, then you can compare if the result is what you expect.

Sample (uncompiled, some errors might occur) :

  enum eExpTypes {
        ET_UNDEFINED,
        ET_BINARY
  }
  class Expresion
  {
      protected:
            eExpTypes myType;
      public:
            Expresion(): myType(ET_UNDEFINED){};
            inline eExpTypes getType(){return myType;};
  }

  class BinExpresion : public Expresion
  {
     public:
            BinExpresion():myType(ET_BINARY){};
  }

Performance gain :

you will take out two indiections : from pointer to vfptable , from vfptable to function
your class size will be less if the type function is the only virtual function

Dynamic cast is usually slower then making your own type check mechanism, so in case of your 3 examples the first one should be the fastest.

Your answer would be great for me. But can you tell me why `dynamic_cast` is slow? — Farhad Reza, Jan 27 '15 at 14:53
In short : it has to look up object type at runtime, throughout it's whole hierarchy (makes more sense if you take as example a very deep inheritance hierarchy,which also involves composition of two type of objects). So it's dependend on how deep and broad the hierarchy is. Here's a related topic on SO : http://stackoverflow.com/questions/4050901/performance-of-dynamic-cast . — MichaelCMS, Jan 27 '15 at 15:09

score 0 · Answer 2 · answered Jan 27 '15 at 14:18

The fastest will be:

e->printIsBinExp();

Where you make that virtual method that either prints or is a noop.

I'm only partially joking. The point of virtual methods is to encapsulate different types' handling of a particular method - not to write a program to just do a runtime switch on what the different runtime types could be.

Suppose the dynamic_cast was fastest. Would you then write:

if (BinExp* be = dynamic_cast<BinExp*>(e)) {
    // ...
}
else if (UnExp* ue = dynamic_cast<UnExp*>(e)) {
    // ...
}
else if (TernExp* te = dynamic_cast<TernExp*>(e)) {
    // ...
}

Hopefully not. That code is going to be very brittle. You'll definitely want to come up with a design such that:

e->eval();

just does the right thing as a single virtual call.

score -1 · Answer 3 · answered Jan 27 '15 at 14:22

-1

Number 3 is the most elegant.

To find out if or which one is the most efficient, some simple code can be used to measure execution time of each case...

#include <iostream>
#include <chrono>

/*
Case
*/

int main()
{
    const clock_t begin_time = clock();
    // Case
    std::cout << float(clock() - begin_time) / CLOCKS_PER_SEC;

    system("pause");
    return 0;
}

answered Jan 27 '15 at 14:22

dspfnder

1,135
1
8
13

"Number 3 is the most elegant. " Based on what? Imagination? – edmz Jan 27 '15 at 14:38
Based on that it uses a language feature for type checking. – dspfnder Jan 27 '15 at 14:41
`dynamic_cast` can do the same thing and so can other strategies. – edmz Jan 27 '15 at 14:45

Efficient run-time type checking in C++

3 Answers3

Linked