Is virtual table necessary for C++?

Question

I have a doubt about C++ virtual table recently.

Why does C++ use virtual table?

=>Because C++ compiler does not know the actual function address

--->Why?

=>Because C++ compiler does not know the exact type(Cat? Dog? Animal?) of the object the pointer "panimal" points to

---Why? Is that any way compiler can figure out the object type?

=>Yes, I think the compiler can make it via tracking object type.

Let's consider the sources where an object pointer gets its value. 2 sources indeed.

1. another pointer
2. address of class instance Where does "another pointer" get its value? Eventually, there's a pointer that gets its value from "class instance".

So, via tracking the assignment thread backwards to the original source object

　　=> the compiler is able to figure out the exact type of a pointer.

　　=>the compiler knows the address of the exact function being called

　　=>no virtual table is needed.

Object type tracking saves both virtual table memery and virtual table pointer of each class instances.

Where does object type tracking not work?

Library Linking.

If a library function returns a base-class pointer, there's no way for the compiler to track back to the original source object. The compiler can probably adapt to library code and none-library code. For library classes that are exported out, use virtual table. For other classes, just track theire object type to save memory.

I am not sure whether there's some error in above statements, please kindly point it out if any. Thanks in advance~

Answer 1

In some cases, yes, the compiler can figure out the type a pointer points to at compile time. It is quite easy to construct a case where it cannot though.

int x;
cin >> x;
Animal* p;
if (x == 10)
    p = new Cat();
else
    p = new Dog();

If the compiler can, in all cases, prove the type of an object, it is free to eliminate virtual tables from its generated code, as per the as-if rule.

Answer 2

the compiler is able to figure out the exact type of a pointer.

yes, but how do you want it to call the right function at runtime? The compiler knows, but c++ has no virtual machine to tell it the type of the object being passed at runtime, ergo, the need for a vtable for virtual functions of inherited types. Would you rather the compiler creates code for all the different code paths that lead to the execution of each virtual function so it calls the right function at runtime? That would lead to much much bigger binaries, if at all possible.

Answer 3

In this example it becomes clear that, whatever the static code analysis the compiler could take, the actual method that gets called at ptrA->f(); can only be known at runtime.

#include <sys/time.h>
#include <iostream>
#include <stdlib.h>

struct A {
    virtual int f()
    {
        std::cout<<"class A\n";
    }
};

struct B: public A {
    int f()
    {
        std::cout<<"class B\n";
    }
};

int main()
{
    A objA;
    B objB;
    A* ptrA;

    timeval tv;
    gettimeofday(&tv, NULL);

    unsigned int seed = (unsigned int)tv.tv_sec;
    int randVal = rand_r(&seed);
    if( randVal < RAND_MAX/2)
    {
        ptrA=&objA;
    }
    else
    {
        ptrA=&objB;
    }

    ptrA->f();
    return 0;
}`