Cost of Polymorphic calls - C++

Question

I'm writing a game in C++ that has about 30 different roles that are each slightly different. I have a main class User that contains all of the data required by all of the roles. My first implementation involved just having an enumeration of 30 roles and handling appropriately, but now I'm wondering if it would be better to have User as a base class and each role being its own class that inherits from User.

My main concern is how efficient are polymorphic method calls when there are 30+ classes inheriting from a single base class? I know polymorphic calls involve pointers in a virtual table but I'm not sure if that means a linear search through the entire table for the right method or if it can be done in constant time.

If anyone could comment on the efficiency of polymorphic method calls with a many inherited classes I would appreciate the enlightenment.

Thanks in advance!

Answer 1

Rather than using inheritance, use composition. Just give your 'User' class an object that does the role. So you may end up with 30 'Role' classes. But they don't inherit off 'User', but are given to 'User' to use ( they may inherit off their own base abstract class to define the interface of 'Role')

or if it is just one function.... you might just model it as a bunch of function objects and then just pass those to User.

Answer 2

The cost is negligeable. It doesn't matter how many classes you have, or how many levels of inheritance, the cost of a polymorphic call is a simple addition - the pointer to the vftable plus the offset of the specific function (not standard mandated, but on most, if not all, implementations this is correct).

Answer 3

Unfortunately, the answer of Luchian Grigore is incorrect.

---

It would be correct in the case of Diamond inheritance. Where you have a class D that inherits from B and C which themselves inherits from A. If you call a function of D, there will be an addition operation on the vtable to lookup at D reference.

 (e.g)                   in Memory
                          -------        Classes hierarchy
                     ---> |  A  |                A
the offset here      |    -------               / \
is the pointer   ->  |    | ... |              B   C    <- Diamond Inheritance
addition he is       |    -------              \   /        (usually very bad)
talking about        ---> |  D  |                D
                          -------

---

In your case, for a polymorphic call the compiler will have to do a lookup (read) on the vtable in order to get the proper function you're calling. When it gets worse is when the data where the vtable is pointing to is not cached. In that case you are having a cache miss, which is very expensive.

Moreover, there is one vtable per class and each object of that class share the same vtable. See In C++, what’s a vtable and how does it work?

---

The real answer to your question depends on how many times you will swap between every of those 30 classes and how often you will use them. Will it be used in a loop?

The solution you are describing is often used to work around this potential problem. But in fact, it might be as fast as the polymorphic call depending how it is used.

So in general you can go for the Polymorphic method without worrying about cost, because it will be negligeable. Write clean and maintainable code first, optimize later. :)

EDIT :

Since there was a discussion about the actual compiler code on this thread, I decided to run a sample to find out what's happening for real.

Below you can see the sample of code I used.

#include <stdlib.h>
#include <stdio.h>

class I
{
public:
    virtual void f(void) = 0;
};

class A : public I
{
public:
    void f(void)
    {
        printf("A\n");
    }
};


int main(int argc, char* argv[])
{
    __asm
    {
        int 3
    }

    A* pA = new A();

    __asm
    {
        nop
        nop
    }

    pA->f();

    __asm
    {
        nop
        nop
    }

    A a;
    a.f();

    __asm
    {
        nop
        nop
    }

    return 0;
}

---

Then, you can see the actual assembly code of the sample (how the compiler did interpret it).

int main(int argc, char* argv[])
{
    __asm
    {
        int 3
010E1010  int         3    
    }

    A* pA = new A();
010E1011  push        4    
010E1013  call        operator new (10E10A4h) 
010E1018  add         esp,4 
010E101B  test        eax,eax 
010E101D  je          main+17h (10E1027h) 
010E101F  mov         dword ptr [eax],offset A::`vftable' (10E2104h)
010E1025  jmp         main+19h (10E1029h) 
010E1027  xor         eax,eax 

    __asm
    {
        nop
010E1029  nop              
        nop
010E102A  nop              
    }

    pA->f();
010E102B  mov         edx,dword ptr [eax] 
010E102D  mov         ecx,eax 
010E102F  mov         eax,dword ptr [edx] 
010E1031  call        eax  

    __asm
    {
        nop
010E1033  nop              
        nop
010E1034  nop              
    }

    A a;
    a.f(); //Polymorphic call
010E1035  push        offset string "A\n" (10E20FCh) 
010E103A  call        dword ptr [__imp__printf (10E20ACh)]
010E1040  add         esp,4 

    __asm
    {
        nop
010E1043  nop              
        nop
010E1044  nop              
    }

    return 0;
010E1045  xor         eax,eax 
}

class A : public I
{
public:

    void f(void)
    {
        printf("A\n");
010E1000  push        offset string "A\n" (10E20FCh) 
010E1005  call        dword ptr [__imp__printf (10E20ACh)] 
010E100B  pop         ecx  
    }