Qual è il costo delle prestazioni di avere un metodo virtuale in una class C ++?

Avere almeno un metodo virtuale in una class C ++ (o una qualsiasi delle sue classi padre) significa che la class avrà una tabella virtuale e ogni istanza avrà un puntatore virtuale.

Quindi il costo della memoria è abbastanza chiaro. Il più importante è il costo di memoria sulle istanze (specialmente se le istanze sono piccole, ad esempio se si intende contenere un intero: in questo caso avere un puntatore virtuale in ogni istanza potrebbe raddoppiare la dimensione delle istanze. lo spazio di memoria utilizzato dalle tabelle virtuali, immagino che di solito è trascurabile rispetto allo spazio utilizzato dal codice del metodo effettivo.

Questo mi porta alla mia domanda: c’è un costo misurabile delle prestazioni (impatto della velocità) per rendere un metodo virtuale? Ci sarà una ricerca nella tabella virtuale in fase di runtime, su ogni chiamata al metodo, quindi se ci sono chiamate molto frequenti a questo metodo e se questo metodo è molto breve, potrebbe esserci un impatto misurabile sulle prestazioni? Immagino dipenda dalla piattaforma, ma qualcuno ha eseguito alcuni benchmark?

La ragione per cui la sto chiedendo è che mi sono imbattuto in un bug che era dovuto a un programmatore che si dimentica di definire un metodo virtuale. Questa non è la prima volta che vedo questo tipo di errore. E ho pensato: perché aggiungiamo la parola chiave virtuale quando necessario invece di rimuovere la parola chiave virtuale quando siamo assolutamente sicuri che non sia necessaria? Se il costo delle prestazioni è basso, penso che raccomanderò semplicemente quanto segue nel mio team: semplicemente rendere ogni metodo virtuale di default, incluso il distruttore, in ogni class, e rimuoverlo solo quando è necessario. Ti sembra pazzesco?

Ho eseguito alcuni cronometri su un processore PowerPC in ordine da 3 ghz. Su questa architettura, una chiamata di funzione virtuale costa 7 nanosecondi più a lungo di una chiamata di funzione diretta (non virtuale).

Quindi, non vale la pena preoccuparsi del costo a meno che la funzione non sia qualcosa di simile a una semplice Accessor () / Set (), in cui qualsiasi cosa diversa da quella in linea è una sorta di spreco. Un sovraccarico di 7ns su una funzione che è in linea a 0,5ns è grave; un sovraccarico di 7ns su una funzione che richiede 500 ms per essere eseguito è privo di significato.

Il grosso costo delle funzioni virtuali non è in realtà la ricerca di un puntatore a funzione nel vtable (che di solito è solo un singolo ciclo), ma che il salto indiretto di solito non può essere predetto sul ramo. Ciò può causare una bolla di pipeline di grandi dimensioni poiché il processore non può recuperare alcuna istruzione finché il salto indiretto (la chiamata attraverso il puntatore della funzione) non è più attivo e viene calcolato un nuovo puntatore di istruzioni. Quindi, il costo di una chiamata di funzione virtuale è molto più grande di quanto possa sembrare guardando l’assemblaggio … ma solo 7 nanosecondi.

Modifica: Andrew, Not Sure, e altri sollevano anche il buon punto che una chiamata di funzione virtuale può causare una mancanza di istruzioni cache: se si salta a un indirizzo di codice che non è nella cache allora l’intero programma si ferma in un punto morto mentre il le istruzioni vengono recuperate dalla memoria principale. Questo è sempre uno stallo significativo: su Xenon, circa 650 cicli (dai miei test).

Tuttavia, questo non è un problema specifico delle funzioni virtuali perché anche una chiamata di funzione diretta causerà un errore se si salta alle istruzioni che non sono nella cache. Ciò che importa è se la funzione è stata eseguita prima di recente (è più probabile che si trovi nella cache) e se l’architettura può prevedere i rami statici (non virtuali) e recuperare tali istruzioni nella cache in anticipo. Il mio PPC no, ma forse l’hardware più recente di Intel.

I miei tempi controllano l’influenza delle mancanze di icache sull’esecuzione (deliberatamente, poiché stavo cercando di esaminare la pipeline della CPU in isolamento), quindi non tengono conto di quel costo.

L’overhead è sicuramente misurabile quando si chiama una funzione virtuale: la chiamata deve utilizzare il vtable per risolvere l’indirizzo della funzione per quel tipo di object. Le istruzioni extra sono l’ultima delle tue preoccupazioni. Non solo i vtables impediscono molte ottimizzazioni del compilatore (dato che il tipo è polimorfico del compilatore) possono anche danneggiare la tua I-Cache.

Ovviamente, se queste sanzioni sono significative o meno dipende dalla vostra applicazione, quanto spesso vengono eseguiti quei percorsi di codice e i vostri modelli di ereditarietà.

A mio parere però, avere tutto come virtuale di default è una soluzione generale per un problema che potresti risolvere in altri modi.

Forse potresti vedere come le classi sono progettate / documentate / scritte. Generalmente l’intestazione per una class dovrebbe chiarire quali funzioni possono essere sostituite dalle classi derivate e come vengono chiamate. Avere programmatori che scrivono questa documentazione è utile per assicurarsi che siano contrassegnati correttamente come virtuali.

Direi anche che dichiarare ogni funzione come virtuale potrebbe portare a più bug che dimenticare semplicemente di contrassegnare qualcosa come virtuale. Se tutte le funzioni sono virtuali, tutto può essere sostituito da classi base – pubbliche, protette, private – tutto diventa un gioco equo. Per sottoclassi di incidente o intenzione, è ansible modificare il comportamento delle funzioni che causano problemi quando vengono utilizzate nell’implementazione di base.

Dipende. 🙂 (Ti aspettavi qualcos’altro?)

Una volta che una class ottiene una funzione virtuale, non può più essere un tipo di dati POD (potrebbe non esserlo nemmeno prima, nel qual caso ciò non farà la differenza) e ciò rende imansible un’intera gamma di ottimizzazioni.

std :: copy () su tipi POD semplici può ricorrere a una semplice routine memcpy, ma i tipi non POD devono essere gestiti con maggiore attenzione.

La costruzione diventa molto più lenta perché il vtable deve essere inizializzato. Nel peggiore dei casi, la differenza di prestazioni tra i tipi di dati POD e non POD può essere significativa.

Nel peggiore dei casi, si può vedere 5 volte più lenta esecuzione (quel numero è preso da un progetto universitario che ho fatto recentemente per reimplementare alcune classi di librerie standard. Il nostro contenitore ha impiegato circa 5 volte il tempo necessario per build non appena il tipo di dati memorizzato vtable)

Naturalmente, nella maggior parte dei casi, è improbabile che si notino differenze di prestazioni misurabili, ma è sufficiente sottolineare che in alcuni casi di confine può essere costoso.

Tuttavia, le prestazioni non dovrebbero essere la tua considerazione principale qui. Rendere tutto virtuale non è una soluzione perfetta per altri motivi.

Consentire che tutto sia sovrascritto nelle classi derivate rende molto più difficile mantenere invarianti di class. In che modo una class garantisce che rimanga in uno stato coerente quando uno qualsiasi dei suoi metodi può essere ridefinito in qualsiasi momento?

Rendere tutto virtuale può eliminare alcuni potenziali bug, ma ne introduce anche di nuovi.

Se hai bisogno della funzionalità di spedizione virtuale, devi pagare il prezzo. Il vantaggio del C ++ è che è ansible utilizzare un’implementazione molto efficiente del dispatch virtuale fornito dal compilatore, piuttosto che una versione potenzialmente inefficiente da implementare.

Tuttavia, se ti muovi con il sovraccarico se non lo usi, forse è un po ‘troppo lontano. E la maggior parte delle classi non è progettata per essere ereditata da – creare una buona class base richiede più che rendere virtuali le sue funzioni.

L’invio virtuale è un ordine di grandezza più lento rispetto ad alcune alternative – non a causa di indirezione così tanto come la prevenzione dell’inlining. Sotto, illustro che confrontando il dispatch virtuale con un’implementazione incorporando un “tipo (identificativo)” negli oggetti e usando un’istruzione switch per selezionare il codice specifico del tipo. Ciò evita completamente il sovraccarico della chiamata di funzione – basta fare un salto locale. Esiste un costo potenziale per la manutenzione, le dipendenze di ricompilazione, ecc. Tramite la localizzazione forzata (nel commutatore) della funzionalità specifica del tipo.


IMPLEMENTAZIONE

 #include  #include  // virtual dispatch model... struct Base { virtual int f() const { return 1; } }; struct Derived : Base { virtual int f() const { return 2; } }; // alternative: member variable encodes runtime type... struct Type { Type(int type) : type_(type) { } int type_; }; struct A : Type { A() : Type(1) { } int f() const { return 1; } }; struct B : Type { B() : Type(2) { } int f() const { return 2; } }; struct Timer { Timer() { clock_gettime(CLOCK_MONOTONIC, &from); } struct timespec from; double elapsed() const { struct timespec to; clock_gettime(CLOCK_MONOTONIC, &to); return to.tv_sec - from.tv_sec + 1E-9 * (to.tv_nsec - from.tv_nsec); } }; int main(int argc) { for (int j = 0; j < 3; ++j) { typedef std::vector V; V v; for (int i = 0; i < 1000; ++i) v.push_back(i % 2 ? new Base : (Base*)new Derived); int total = 0; Timer tv; for (int i = 0; i < 100000; ++i) for (V::const_iterator i = v.begin(); i != v.end(); ++i) total += (*i)->f(); double tve = tv.elapsed(); std::cout << "virtual dispatch: " << total << ' ' << tve << '\n'; // ---------------------------- typedef std::vector W; W w; for (int i = 0; i < 1000; ++i) w.push_back(i % 2 ? (Type*)new A : (Type*)new B); total = 0; Timer tw; for (int i = 0; i < 100000; ++i) for (W::const_iterator i = w.begin(); i != w.end(); ++i) { if ((*i)->type_ == 1) total += ((A*)(*i))->f(); else total += ((B*)(*i))->f(); } double twe = tw.elapsed(); std::cout << "switched: " << total << ' ' << twe << '\n'; // ---------------------------- total = 0; Timer tw2; for (int i = 0; i < 100000; ++i) for (W::const_iterator i = w.begin(); i != w.end(); ++i) total += (*i)->type_; double tw2e = tw2.elapsed(); std::cout << "overheads: " << total << ' ' << tw2e << '\n'; } } 

RISULTATI DELLE PRESTAZIONI

Sul mio sistema Linux:

 ~/dev g++ -O2 -o vdt vdt.cc -lrt ~/dev ./vdt virtual dispatch: 150000000 1.28025 switched: 150000000 0.344314 overhead: 150000000 0.229018 virtual dispatch: 150000000 1.285 switched: 150000000 0.345367 overhead: 150000000 0.231051 virtual dispatch: 150000000 1.28969 switched: 150000000 0.345876 overhead: 150000000 0.230726 

Ciò suggerisce che un approccio in linea di tipo a commutazione di numero è circa (1,28 - 0,23) / (0,344 - 0,23) = 9,2 volte più veloce. Naturalmente, questo è specifico per il sistema esatto testato / flag del compilatore e versione ecc., Ma generalmente indicativo.


COMMENTI RE VIRTUAL DISPATCH

Va detto però che le overhead delle chiamate di funzione virtuali sono qualcosa che è raramente significativo, e solo per le cosiddette funzioni banali (come getter e setter). Anche in questo caso, potresti essere in grado di fornire una singola funzione per ottenere e impostare un sacco di cose contemporaneamente, riducendo al minimo i costi. Le persone si preoccupano troppo del dispatch virtuale - così fanno la profilazione prima di trovare alternative scomode. Il problema principale con loro è che eseguono una chiamata di funzione fuori linea, anche se delocalizzano anche il codice eseguito che cambia i modelli di utilizzo della cache (per meglio o (più spesso) peggio).

Il costo aggiuntivo non è praticamente nulla nella maggior parte degli scenari. (scusate il gioco di parole). ejac ha già pubblicato misure relative sensibili.

La cosa più grande che ti arrendi sono le possibili ottimizzazioni dovute all’inlinazione. Possono essere particolarmente utili se la funzione viene chiamata con parametri costanti. Questo raramente fa la differenza, ma in alcuni casi, questo può essere enorme.


Per quanto riguarda le ottimizzazioni:
È importante conoscere e considerare il costo relativo dei costrutti della tua lingua. La notazione Big O è metà della storia – come scala la tua applicazione . L’altra metà è il fattore costante di fronte ad essa.

Come regola empirica, non farei di tutto per evitare le funzioni virtuali, a meno che non vi siano indicazioni chiare e specifiche che si tratti di un collo di bottiglia. Un design pulito viene sempre prima di tutto, ma è solo uno degli stakeholder che non dovrebbe offendere indebitamente gli altri.


Esempio di contrived: un distruttore virtuale vuoto su un array di un milione di piccoli elementi può attraversare almeno 4 MB di dati, danneggiando la cache. Se tale distruttore può essere distanziato, i dati non verranno toccati.

Quando si scrive codice libreria, tali considerazioni sono lungi dall’essere premature. Non sai mai quanti anelli verranno messi attorno alla tua funzione.

Mentre tutti gli altri hanno ragione circa le prestazioni dei metodi virtuali e così via, penso che il vero problema è se il team conosce la definizione della parola chiave virtuale in C ++.

Considera questo codice, qual è l’output?

 #include  class A { public: void Foo() { printf("A::Foo()\n"); } }; class B : public A { public: void Foo() { printf("B::Foo()\n"); } }; int main(int argc, char** argv) { A* a = new A(); a->Foo(); B* b = new B(); b->Foo(); A* a2 = new B(); a2->Foo(); return 0; } 

Niente di sorprendente qui:

 A::Foo() B::Foo() A::Foo() 

Come nulla è virtuale. Se la parola chiave virtuale viene aggiunta alla parte anteriore di Foo in entrambe le classi A e B, otteniamo questo risultato per l’output:

 A::Foo() B::Foo() B::Foo() 

Praticamente quello che tutti si aspettano.

Ora, hai detto che ci sono bug perché qualcuno ha dimenticato di aggiungere una parola chiave virtuale. Quindi considera questo codice (dove la parola chiave virtuale viene aggiunta ad A, ma non alla class B). Qual è l’output allora?

 #include  class A { public: virtual void Foo() { printf("A::Foo()\n"); } }; class B : public A { public: void Foo() { printf("B::Foo()\n"); } }; int main(int argc, char** argv) { A* a = new A(); a->Foo(); B* b = new B(); b->Foo(); A* a2 = new B(); a2->Foo(); return 0; } 

Risposta: lo stesso come se la parola chiave virtuale fosse aggiunta a B? Il motivo è che la firma per B :: Foo corrisponde esattamente a A :: Foo () e perché A’s Foo è virtuale, così come B.

Consideriamo ora il caso in cui B’s Foo è virtuale e A non lo è. Qual è l’output allora? In questo caso, l’output è

 A::Foo() B::Foo() A::Foo() 

La parola chiave virtuale funziona verso il basso nella gerarchia, non verso l’alto. Non rende mai virtuali i metodi della class base. La prima volta che si incontra un metodo virtuale nella gerarchia si ha quando inizia il polimorfismo. Non c’è un modo per le classi successive per rendere le classi precedenti hanno metodi virtuali.

Non dimenticare che i metodi virtuali significano che questa class sta dando alle classi future la possibilità di sovrascrivere / modificare alcuni dei suoi comportamenti.

Quindi, se hai una regola per rimuovere la parola chiave virtuale, potrebbe non avere l’effetto desiderato.

La parola chiave virtuale in C ++ è un concetto potente. Dovresti assicurarti che ogni membro del team conosca davvero questo concetto in modo che possa essere utilizzato come progettato.

A seconda della piattaforma, il sovraccarico di una chiamata virtuale può essere molto indesiderabile. Dichiarando ogni funzione virtuale, le stai essenzialmente chiamando attraverso un puntatore a funzione. Per lo meno si tratta di un dereferimento extra, ma su alcune piattaforms PPC utilizzerà istruzioni microcodice o comunque lente per ottenere ciò.

Raccomanderei contro il tuo suggerimento per questo motivo, ma se ti aiuta a prevenire i bug allora potrebbe valere la pena. Non posso fare a meno di pensare che ci deve essere una via di mezzo che vale la pena di trovare, però.

Richiederà solo un paio di istruzioni extra asm per chiamare il metodo virtuale.

Ma non penso che ti preoccupi che il divertimento (int a, int b) abbia un paio di istruzioni extra “push” rispetto a fun (). Quindi non preoccuparti anche dei virtual, finché non ti trovi in ​​una situazione speciale e vedi che questo porta davvero a dei problemi.

PS Se hai un metodo virtuale, assicurati di avere un distruttore virtuale. In questo modo eviterete possibili problemi


In risposta ai commenti di “xtofl” e “Tom”. Ho fatto piccoli test con 3 funzioni:

  1. Virtuale
  2. Normale
  3. Normale con 3 parametri int

Il mio test è stato una semplice iterazione:

 for(int it = 0; it < 100000000; it ++) { test.Method(); } 

E qui i risultati:

  1. 3.913 sec
  2. 3,873 sec
  3. 3.970 secondi

È stato compilato da VC ++ in modalità di debug. Ho fatto solo 5 test per metodo e calcolato il valore medio (quindi i risultati potrebbero essere piuttosto imprecisi) ... In ogni caso, i valori sono quasi uguali supponendo 100 milioni di chiamate. E il metodo con 3 extra push / pop è stato più lento.

Il punto principale è che se non ti piace l'analogia con il push / pop, pensa a extra se / else nel tuo codice? Pensi alla pipeline della CPU quando aggiungi extra se / else 😉 Inoltre, non sai mai su quale CPU verrà eseguito il codice ... Il solito compilatore può generare codice più ottimale per una CPU e meno ottimale per un'altra ( Intel Compilatore C ++ )