C++: fighting polymorphism overhead

Question

I know that polymorphism can add a noticeable overhead. Calling a virtual function is slower than calling a non-virtual one. (All my experience is about GCC, but I think/heard that this is true for any realcompiler.)

Many times a given virtual function gets called on the same object over and over; I know that object type doesn't change, and most of the times compiler could easily deduct that has well:

BaseType &obj = ...;
while( looping )
    obj.f(); // BaseType::f is virtual

To speed up the code I could rewrite the above code like this:

BaseType &obj = ...;
FinalType &fo = dynamic_cast< FinalType& >( obj );
while( looping )
    fo.f(); // FinalType::f is not virtual

I wonder what's the best way to avoid this overhead due to polymorphism in these cases.

The idea of upper-casting (as shown in the second snippet) doesn't look that good to me: BaseType could be inherited by many classes, and trying to upper-cast to all of them would be pretty prolix.

Another idea could be that of storing obj.f in a function pointer (didn't test this, not sure it would kill run-time overhead), but again this method doesn't look perfect: as the above method, it would require to write more code and it wouldn't be able to exploit some optimizations (eg: if FinalType::f was an inline function, it wouldn't get inlined -- but I guess the only way to avoid this would be to upper-cast obj to its final type...)

So, is there any better method?

Edit: Well, of course this is not going to impact that much. This question was mostly to know if there was something to do, since it looks like this overhead is given for free (this overhead looks to be very easy to kill) I don't see why not to.

An easy keyword for little optimizations, like C99 restrict, to tell compiler a polymorphic object is of a fixed type is what I was hoping for.

Anyway, just to answer back to comments, a little overhead is present. Look at this ad-hoc extreme code:

struct Base { virtual void f(){} };
struct Final : public Base { void f(){} };

int main( ) {
    Final final;
    Final &f = final;
    Base &b = f;

    for( int i = 0; i < 1024*1024*1024; ++ i )
#ifdef BASE
        b.f( );
#else
        f.f( );
#endif

    return 0;
}

Compiling and running it, taking times:

$ for OPT in {"",-O0,-O1,-O2,-O3,-Os}; do
    for DEF in {BASE,FINAL}; do
        g++ $OPT -D$DEF -o virt virt.cpp &&
        TIME="$DEF $OPT: %U" time ./virt;
    done;
  done           
BASE : 5.19                                                                                                                                                                         
FINAL : 4.21                                                                                                                                                                        
BASE -O0: 5.22                                                                                                                                                                      
FINAL -O0: 4.19                                                                                                                                                                     
BASE -O1: 3.55                                                                                                                                                                      
FINAL -O1: 1.53                                                                                                                                                                     
BASE -O2: 3.61                                                                                                                                                                      
FINAL -O2: 0.00                                                                                                                                                                     
BASE -O3: 3.58                                                                                                                                                                      
FINAL -O3: 0.00                                                                                                                                                                     
BASE -Os: 6.14                                                                                                                                                                      
FINAL -Os: 0.00

I guess only -O2, -O3 and -Os are inlining Final::f.

And these tests have been run on my machine, running the latest GCC and an AMD Athlon(tm) 64 X2 Dual Core Processor 4000+ CPU. I guess it could be a lot slower on a cheaper platform.

Listerism

So, I take it you're saying your code is crawling-slow, and you profiled it and found the issue is in polymorphism? – Castera

If f is virtual in BaseType and FinalType is derived from BaseType, then f is also virtual in FinalType. – Samarasamarang

Also. dynamic_cast<>() has a cost of a check at runtime, and the cost of polymorphism is a single pointer dereference. I suggest whenever you say the word "overhead" make sure you say exactly what that overhead is, at least the first time you talk about that overhead. Just so we're clear what we're trying to eliminate here. And so, now, I take it you profiled the two approaches and found polymorphism is slower than your hack? – Castera

And also, regarding fighting: it's cute. – Castera

@wilhelmtell: dynamic_cast would be ran only once, to upper-cast the object. After that I would always use the most derived class object; casting cost would be absorbed. – Listerism

@peoro: If the parameter types of FinalType::f are the same as the parameter types of BaseType::f, then FinalType::f is virtual and overrides BaseType::f. It doesn't matter whether the function is declared with the keyword virtual in the derived class. In your example, since f has no parameters, FinalType::f does override BaseType::f. – Samarasamarang

Even if you know that FinalType is always the most derived class, it's often difficult or impossible for the compiler to know that. While the compiler can optimize some virtual function calls and determine which function to call at compile-time, it can't in most cases. Your example test where all the classes are declared, defined, and used in a single translation unit is a rare example of when a compiler can make this optimization. – Samarasamarang

Answer 1

If dynamic dispatch is a performance bottleneck in your program, then the way to solve the problem is not to use dynamic dispatch (don't use virtual functions).

You can replace some run-time polymorphism with compile-time polymorphism by using templates and generic programming instead of virtual functions. This may or may not result in better performance; only a profiler can tell you for sure.

To be clear though, as wilhelmtell has already pointed out in comments to the question, it's rare that the overhead caused by dynamic dispatch is significant enough to worry about. Be absolutely sure that it's your performance hot-spot before you go replacing built-in convenience with an unwieldy custom implementation.

Samarasamarang

Sometimes you are "forced" to use polymorphism (and thus dynamic dispatch, I was missing the term until now). Of course you can upper-cast your polymorphic pointer/reference, and then use it (pass it to template functions or whatever); that is what I had in mind with the upper-casting solution. As said after editing the original post, it is mostly a doubt about how things work. Thanks for the answer, btw. – Listerism

Answer 2

If you need to use polymorphism, then use it. There is really no faster way to do it.

However, I would respond with another question: Is this your biggest problem? If so, your code is already optimal or nearly so. If not, find out what the biggest problem is, and concentrate on that instead.

Mussorgsky