How can I avoid a virtual call when I know the type?

Question

Consider the following code snippet:

struct Base { virtual void func() { } };
struct Derived1 : Base { void func() override { print("1"); } };
struct Derived2 : Base { void func() override { print("2"); } };

class Manager {
    std::vector<std::unique_ptr<Base>> items;

    public:
        template<class T> void add() { items.emplace_back(new T); }
        void funcAll() { for(auto& i : items) i->func(); }
};

int main() {
    Manager m;
    m.add<Derived1>();
    m.add<Derived2>();
    m.funcAll(); // prints "1" and "2"
};

I'm using virtual dispatch in order to call the correct override method from a std::vector of polymorphic objects.

However, I know what type the polymorphic objects are, since I specify that in Manager::add<T>.

My idea was to avoid a virtual call by taking the address of the member function T::func() and directly storing it somewhere. However that's impossible, since I would need to store it as void* and cast it back in Manager::funcAll(), but I do not have type information at that moment.

My question is: it seems that in this situation I have more information than usual for polymorphism (the user specifies the derived type T in Manager::add<T>) - is there any way I can use this type information to prevent a seemingly unneeded virtual call? (An user should be able to create its own classes that derive from Base in its code, however.)

Answer 1

One trick that can sometimes help in this kind of situation is to sort the vector by type (you should be able to use the knowledge of the type available in the add() function to enforce this) if the order of elements doesn't otherwise matter. If you are mostly going to be iterating over the vector in order calling a virtual function this will help the CPU's branch predictor predict the target of the call. Alternatively you can maintain separate vectors for each type in your manager and iterate over them in turn which has a similar effect.

Your compiler's optimizer can also help you with this kind of code, particularly if it supports Profile Guided Optimization (POGO). Compilers can de-virtualize calls in certain situations, or with POGO can do things in the generated assembly to help the CPU's branch predictor, like test for the most common types and perform a direct call for those with a fallback to an indirect call for the less common types.

Here's the results of a test program that illustrates the performance benefits of sorting by type, Manager is your version, Manager2 maintains a hash table of vectors indexed by typeid:

Derived1::count = 50043000, Derived2::count = 49957000
class Manager::funcAll took 714ms
Derived1::count = 50043000, Derived2::count = 49957000
class Manager2::funcAll took 274ms
Derived1::count = 50043000, Derived2::count = 49957000
class Manager2::funcAll took 273ms
Derived1::count = 50043000, Derived2::count = 49957000
class Manager::funcAll took 714ms

Test code:

#include <iostream>
#include <vector>
#include <memory>
#include <random>
#include <unordered_map>
#include <typeindex>
#include <chrono>

using namespace std;
using namespace std::chrono;

static const int instanceCount = 100000;
static const int funcAllIterations = 1000;
static const int numTypes = 2;

struct Base { virtual void func() = 0; };
struct Derived1 : Base { static int count; void func() override { ++count; } };
int Derived1::count = 0;
struct Derived2 : Base { static int count; void func() override { ++count; } };
int Derived2::count = 0;

class Manager {
    vector<unique_ptr<Base>> items;

public:
    template<class T> void add() { items.emplace_back(new T); }
    void funcAll() { for (auto& i : items) i->func(); }
};

class Manager2 {
    unordered_map<type_index, vector<unique_ptr<Base>>> items;

public:
    template<class T> void add() { items[type_index(typeid(T))].push_back(make_unique<T>()); }
    void funcAll() { 
        for (const auto& type : items) {
            for (auto& i : type.second) {
                i->func();
            }
        }
    }
};

template<typename Man>
void Test() {
    mt19937 engine;
    uniform_int_distribution<int> d(0, numTypes - 1);

    Derived1::count = 0;
    Derived2::count = 0;

    Man man;
    for (auto i = 0; i < instanceCount; ++i) {
        switch (d(engine)) {
        case 0: man.add<Derived1>(); break;
        case 1: man.add<Derived2>(); break;
        }
    }

    auto startTime = high_resolution_clock::now();
    for (auto i = 0; i < funcAllIterations; ++i) {
        man.funcAll();
    }
    auto endTime = high_resolution_clock::now();

    cout << "Derived1::count = " << Derived1::count << ", Derived2::count = " << Derived2::count << "\n"
         << typeid(Man).name() << "::funcAll took " << duration_cast<milliseconds>(endTime - startTime).count() << "ms" << endl;
}

int main() {
    Test<Manager>();
    Test<Manager2>();

    Test<Manager2>();
    Test<Manager>();
}

Answer 2

If I understand well, you want your add method, which is getting the class of the object, to store the right function in your vector depending on that object class. Your vector just contains functions, no more information about the objects.

You kind of want to "solve" the virtual call before it is invoked. This is maybe interesting in the following case: the function is then called a lot of times, because you don't have the overhead of solving the virtual each time.

So you may want to use a similar process than what "virtual" does, using a "virtual table". The implementation of virtual is done at low level, so pretty fast compared to whatever you will come up with, so again, the functions should be invoked a LOT of times before it gets interesting.

Answer 3

However, I know what type the polymorphic objects are, since I specify that in Manager::add<T>.

No you don't. Within add you know the type of the object that's being added; but you can add objects of different types, as you do in your example. There's no way for funcAll to statically determine the types of the elements unless you parametrise Manager to only handle one type.

If you did know the type, then you could call the function non-virtually:

i->T::func();

But, to reiterate, you can't determine the type statically here.