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 use virtual to send the correct override method from std::vector polymorphic objects.

However, I know what type of polymorphic objects, since I indicate that in Manager::add<T> .

My idea was to avoid calling virtual by taking the address of the member function T::func() and storing it directly somewhere. However, this is not possible, since I need to save it as void* and return it back to Manager::funcAll() , but at this moment I have no type information.

My question is: it seems that in this situation I have more information than usual for polymorphism (the user indicates the derived type T in Manager::add<T> ) - is there a way to use this type information to prevent the seemingly unnecessary call to virtual ? (However, the user must be able to create their own classes derived from Base in their code.)

Answer 1

However, I know what type of polymorphic objects, since I indicate that in Manager::add<T> .

No no. Within add you know the type of object to add; but you can add objects of different types, as in your example. There is no way funcAll statically determine element types unless you parameterize Manager to process only one type.

If you know the type, you can call the function practically:

 i->T::func(); 

But again, you cannot define the type statically here.

Answer 2

If I understand well, you want your add method, which receives the class of the object, to store the correct function in your vector, depending on this class of the object. Your vector simply contains functions, more information about objects.

You want to "solve" a virtual call before it is called. This may be interesting in the following case: the function is then called many times because you do not have the overhead of solving the virtual every time.

Thus, you can use a similar process than "virtual" using the "virtual table". The implementation of the virtual is performed at a low level, so it’s pretty fast compared to what you come up with, so again you need to call it many times before it becomes interesting.

Answer 3

One trick that can sometimes help in this 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 ensure that it is executed) if the order of the elements fails otherwise. If you are mainly going to iterate over a vector to call a virtual function, this will help the processor branch predictor predict the purpose of the call. Alternatively, you can maintain separate vectors for each type in your manager and iterate over them one by one, which has a similar effect.

The compiler optimizer can also help you with such code, especially if it supports profiled optimization (POGO). Compilers can de-virtualize calls in certain situations or with POGO can do something in the generated assembly to help the processor branch predictor, for example, test the most common types and make a direct call for those who have rejected an indirect call for less common types.

Here are 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>(); }