C++: polimorfismo da combattimento in testa

Question

So che il polimorfismo può aggiungere un notevole overhead. Chiamare una funzione virtuale è più lento che chiamare uno non virtuale. (Tutta la mia esperienza riguarda GCC, ma penso/sentito che questo è vero per qualsiasi realcompiler.)

Molte volte una determinata funzione virtuale viene chiamata sullo stesso oggetto più e più volte; So che tipo di oggetto non cambia, e il più delle volte compilatore potrebbe facilmente dedurre che ha ben:

BaseType &obj = ...; 
while(looping) 
    obj.f(); // BaseType::f is virtual 

Per accelerare il codice ho potuto riscrivere il codice di cui sopra in questo modo:

BaseType &obj = ...; 
FinalType &fo = dynamic_cast< FinalType& >(obj); 
while(looping) 
    fo.f(); // FinalType::f is not virtual 

Mi chiedo quale sia il modo migliore per evitare questo sovraccarico dovuto al polimorfismo in questi casi.

L'idea di fusione in alto (come mostrato nel secondo frammento) non mi sembra buona: il BaseType potrebbe essere ereditato da molte classi e provare a eseguire il cast in maiuscolo a tutti sarebbe molto prolisso.

Un'altra idea potrebbe essere quella di memorizzare obj.f in un puntatore a funzione (non testarlo, non è sicuro che ucciderebbe l'overhead di runtime), ma ancora una volta questo metodo non sembra perfetto: come il metodo precedente, richiederebbe di scrivere più codice e non sarebbe in grado di sfruttare alcune ottimizzazioni (ad esempio: se FinalType::f era una funzione inline, non si sarebbe in linea, ma suppongo che l'unico modo per evitare questo sarebbe quello di cast superiore obj al suo tipo finale ...)

Quindi, c'è un metodo migliore?

Modifica: Beh, ovviamente questo non ha un impatto così importante. Questa domanda era principalmente per sapere se c'era qualcosa da fare, dal momento che sembra che questo overhead sia dato gratuitamente (questo overhead sembra essere molto facile da uccidere) Non vedo perché non farlo.

Una parola chiave facile per piccole ottimizzazioni, come C99 restrict, per dire al compilatore che un oggetto polimorfico è di un tipo fisso è quello che speravo.

In ogni caso, solo per rispondere ai commenti, è presente un piccolo overhead. Un'occhiata a questo codice ad hoc estrema:

struct Base { virtual void f(){} }; 
struct Final : public Base { void f(){} }; 

int main() { 
    Final final; 
    Final &f = final; 
    Base &b = f; 

    for(int i = 0; i < 1024*1024*1024; ++ i) 
#ifdef BASE 
     b.f(); 
#else 
     f.f(); 
#endif 

    return 0; 
} 

Compilazione ed esecuzione di esso, prendendo i tempi:

$ for OPT in {"",-O0,-O1,-O2,-O3,-Os}; do 
    for DEF in {BASE,FINAL}; do 
     g++ $OPT -D$DEF -o virt virt.cpp && 
     TIME="$DEF $OPT: %U" time ./virt; 
    done; 
    done   
BASE : 5.19                                           
FINAL : 4.21                                           
BASE -O0: 5.22                                          
FINAL -O0: 4.19                                          
BASE -O1: 3.55                                          
FINAL -O1: 1.53                                          
BASE -O2: 3.61                                          
FINAL -O2: 0.00                                          
BASE -O3: 3.58                                          
FINAL -O3: 0.00                                          
BASE -Os: 6.14                                          
FINAL -Os: 0.00 

Credo che solo -O2, -O3 e -Os sono inlining Final::f.

E questi test sono stati eseguiti sulla mia macchina, con l'ultimo GCC e un processore AMD Athlon (tm) 64 X2 Dual Core Processor 4000+. Immagino che potrebbe essere molto più lento su una piattaforma più economica.

Answer 1

Se il dispatch dinamico è un collo di bottiglia delle prestazioni nel programma, il modo per risolvere il problema non consiste nell'utilizzare la distribuzione dinamica (non utilizzare le funzioni virtuali).

È possibile sostituire un po 'di polimorfismo di runtime con il polimorfismo in fase di compilazione utilizzando modelli e programmazione generica anziché funzioni virtuali. Questo può o non può portare a prestazioni migliori; solo un profiler può dirti di sicuro.

Per essere chiari, tuttavia, come già sottolineato da wilhelmtell nei commenti alla domanda, è raro che il sovraccarico causato dall'invio dinamico sia abbastanza significativo da preoccuparsi. Sii assolutamente certo che si tratti delle tue prestazioni hot-spot prima di sostituire la praticità incorporata con un'implementazione personalizzata complessa.

Answer 2

Se è necessario utilizzare il polimorfismo, quindi utilizzarlo. Non c'è davvero un modo più veloce per farlo.

Tuttavia, vorrei rispondere con un'altra domanda: è questo il tuo più grande problema? Se è così, il tuo codice è già ottimale o quasi. In caso contrario, scopri qual è il problema più grande e concentrati su quello.