Come posso evitare una chiamata virtuale quando conosco il tipo?

Question

Si consideri il seguente frammento di codice:

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" 
}; 

sto usando virtual spedizione al fine di chiamare il override metodo corretto da un std::vector di oggetti polimorfici.

Tuttavia, so di che tipo sono gli oggetti polimorfici, poiché lo specifica in Manager::add<T>.

La mia idea era di evitare una chiamata virtual prendendo l'indirizzo della funzione membro T::func() e memorizzandolo direttamente da qualche parte. Tuttavia, è impossibile, dal momento che avrei bisogno di memorizzarlo come void* e di ricollocarlo nel Manager::funcAll(), ma in quel momento non ho informazioni sul tipo.

La mia domanda è: sembra che in questa situazione ho più informazioni rispetto al solito per il polimorfismo (l'utente specifica il tipo derivato T in Manager::add<T>) - c'è un modo posso usare questo tipo di informazioni per evitare che un apparentemente inutili virtual chiamata? (Un utente dovrebbe essere in grado di creare le proprie classi che derivano dalla Base nel suo codice, tuttavia.)

Answer 1

Tuttavia, sapere che tipo gli oggetti polimorfici sono, dal momento Preciso che in Manager::add<T>.

No, non è così. Entro add si conosce il tipo di oggetto che si sta aggiungendo; ma puoi aggiungere oggetti di diverso tipo, come fai nel tuo esempio. Non è possibile per funcAll determinare in modo statico i tipi di elementi a meno che non si parametrizzi Manager per gestire solo un tipo.

Se avete fatto conoscere il tipo, allora si potrebbe chiamare la funzione non virtualmente:

i->T::func(); 

Ma, per ribadire, non è possibile determinare il tipo statico qui.

Answer 2

Se ho capito bene, vuoi che il tuo metodo add, che sta ottenendo la classe dell'oggetto, memorizzi la funzione corretta nel tuo vettore in base a quella classe di oggetti. Il vettore contiene solo funzioni, non più informazioni sugli oggetti.

Si desidera "risolvere" la chiamata virtuale prima che venga invocata. Questo è forse interessante nel seguente caso: la funzione viene quindi chiamata un sacco di volte, perché non si ha il sovraccarico di risolvere il virtuale ogni volta.

Quindi si consiglia di utilizzare un processo simile a quello che fa "virtuale", utilizzando una "tabella virtuale". L'implementazione del virtual è fatta a basso livello, quindi piuttosto veloce rispetto a qualsiasi cosa tu voglia, quindi di nuovo, le funzioni dovrebbero essere invocate MOLTE volte prima che diventi interessante.

Answer 3

Un trucco che a volte può aiutare in questo tipo di situazione consiste nell'ordinare il vettore in base al tipo (dovresti essere in grado di utilizzare la conoscenza del tipo disponibile nella funzione add() per applicarlo) se l'ordine degli elementi non importa altrimenti. Se si sta per lo più iterando sul vettore per chiamare una funzione virtuale, ciò aiuterà il predittore di ramo della CPU a prevedere l'obiettivo della chiamata.In alternativa puoi mantenere vettori separati per ogni tipo nel tuo manager e iterare su di essi a loro volta che ha un effetto simile.

L'ottimizzatore del compilatore può anche aiutare con questo tipo di codice, in particolare se supporta l'ottimizzazione guidata dei profili (POGO). I compilatori possono de-virtualizzare le chiamate in determinate situazioni, oppure con POGO può fare cose nell'assembly generato per aiutare il predittore di ramo della CPU, come test per i tipi più comuni ed eseguire una chiamata diretta per quelli con un fallback a una chiamata indiretta per tipi meno comuni.

Ecco i risultati di un programma di test che illustra i vantaggi di prestazioni di ordinamento per tipo, Manager è la versione, Manager2 mantiene una tabella hash di vettori indicizzate da 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 

Codice di prova:

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