In C ++ perché e in che modo le funzioni virtuali sono più lente?

34

Qualcuno può spiegare in dettaglio come funziona esattamente la tabella virtuale e quali puntatori sono associati quando vengono chiamate le funzioni virtuali.

Se sono effettivamente più lenti, puoi mostrare il tempo che la funzione virtuale impiega per eseguire è più dei normali metodi di classe? È facile perdere la cognizione di come / cosa sta accadendo senza vedere del codice.

    
posta MdT 22.03.2013 - 23:41
fonte

4 risposte

50

I metodi virtuali sono comunemente implementati tramite le cosiddette tabelle dei metodi virtuali (vtable in breve), in cui sono memorizzati i puntatori di funzione. Questo aggiunge indiretta alla chiamata reale (devi recuperare l'indirizzo della funzione per chiamare dal vtable, quindi chiamarlo - invece di chiamarlo proprio davanti a te). Certo, questo richiede un po 'di tempo e un po' di codice.

Tuttavia, non è necessariamente la causa principale della lentezza. Il vero problema è che il compilatore (in genere / di solito) non può sapere quale funzione verrà chiamata. Quindi non può indicarlo o eseguire altre ottimizzazioni del genere. Questo da solo potrebbe aggiungere una dozzina di istruzioni inutili (preparare registri, chiamare, quindi ripristinare lo stato in seguito) e potrebbe inibire altre ottimizzazioni apparentemente non correlate. Inoltre, se branchi come matti chiamando molte implementazioni differenti, subisci gli stessi colpi che subiresti per ramificarti come un matto con altri mezzi: il predittore di cache e di ramo non ti aiuterà, i rami impiegheranno più tempo di un perfettamente prevedibile ramo.

Grande ma : questi risultati delle prestazioni sono in genere troppo piccoli per la materia. Vale la pena considerare se si desidera creare un codice ad alte prestazioni e considerare l'aggiunta di una funzione virtuale che verrebbe chiamata a frequenza allarmante. Tuttavia, anche tieni presente che sostituire le chiamate di funzioni virtuali con altri mezzi di ramificazione ( if .. else , switch , puntatori di funzione, ecc.) Non risolverà il problema fondamentale - potrebbe beh, è più lento Il problema (se esiste) non è funzioni virtuali ma (non necessario) indiretto.

Modifica: la differenza nelle istruzioni di chiamata è descritta in altre risposte. Fondamentalmente, il codice per una chiamata statica ("normale") è:

  • Copia alcuni registri in pila, per consentire alla funzione chiamata di utilizzare quei registri.
  • Copia gli argomenti in posizioni predefinite, in modo che la funzione chiamata possa trovarli indipendentemente da dove viene chiamata.
  • Inserisci l'indirizzo di ritorno.
  • Ramo / salta al codice della funzione, che è un indirizzo in fase di compilazione e quindi codificato nel file binario dal compilatore / linker.
  • Ottieni il valore di ritorno da una posizione predefinita e ripristina i registri che vogliamo utilizzare.

Una chiamata virtuale fa esattamente la stessa cosa, tranne che l'indirizzo della funzione non è noto al momento della compilazione. Invece, un paio di istruzioni ...

  • Ottieni il puntatore vtable, che punta a una serie di puntatori di funzione (indirizzi di funzione), uno per ogni funzione virtuale, dall'oggetto.
  • Ottieni l'indirizzo di funzione corretto dal vtable in un registro (l'indice in cui è archiviato l'indirizzo corretto della funzione viene deciso in fase di compilazione).
  • Vai all'indirizzo in quel registro, piuttosto che saltare a un indirizzo codificato.

Come per i rami: un ramo è tutto ciò che salta a un'altra istruzione invece di lasciare che l'istruzione successiva venga eseguita. Questo include if , switch , parti di vari cicli, chiamate di funzione, ecc. Ea volte il compilatore implementa cose che non sembrano diramarsi in un modo che ha effettivamente bisogno di un ramo sotto il cofano. Vedi Perché l'elaborazione di un array ordinato è più veloce di un array non ordinato? per il motivo per cui questo potrebbe essere lento, ciò che le CPU fanno per contrastare questo rallentamento, e come questo non è un toccasana.

    
risposta data 23.03.2013 - 00:06
fonte
21

Ecco alcuni codici effettivi disassemblati da una chiamata di funzione virtuale e una chiamata non virtuale, rispettivamente:

mov    -0x8(%rbp),%rax
mov    (%rax),%rax
mov    (%rax),%rax
callq  *%rax

callq  0x4007aa

Puoi vedere che la chiamata virtuale richiede tre istruzioni aggiuntive per cercare l'indirizzo corretto, mentre l'indirizzo della chiamata non virtuale può essere compilato.

Tuttavia, si noti che il più delle volte il tempo di ricerca extra può essere considerato trascurabile. In situazioni in cui il tempo di ricerca sarebbe significativo, come in un ciclo, il valore può solitamente essere memorizzato nella cache eseguendo le prime tre istruzioni prima del ciclo.

L'altra situazione in cui il tempo di ricerca diventa significativo è se si dispone di una raccolta di oggetti e si sta eseguendo il ciclo chiamando una funzione virtuale su ciascuno di essi. Tuttavia, in questo caso, avrai bisogno di alcuni mezzi per selezionare quale funzione chiamare in ogni caso, e la ricerca di una tabella virtuale è un mezzo valido come qualsiasi. Infatti, poiché il codice di ricerca vtable è così ampiamente utilizzato, è strongmente ottimizzato, quindi provare a risolverlo manualmente ha buone probabilità di ottenere prestazioni peggiori .

    
risposta data 23.03.2013 - 01:16
fonte
17

Più lento di ciò che ?

Le funzioni virtuali risolvono un problema che non può essere risolto con chiamate di funzione dirette. In generale, puoi solo confrontare due programmi che calcolano la stessa cosa. "Questo ray tracer è più veloce di quel compilatore" non ha senso, e questo principio generalizza anche a piccole cose come le singole funzioni o i costrutti del linguaggio di programmazione.

Se non usi una funzione virtuale per passare dinamicamente a un pezzo di codice basato su un dato, come un tipo di oggetto, allora dovrai usare qualcos'altro, come un'istruzione switch per realizzare lo stesso cosa. Questo qualcos'altro ha i suoi costi generali, oltre a implicazioni sull'organizzazione del programma che ne influenzano la manutenibilità e le prestazioni globali.

Si noti che in C ++, le chiamate a funzioni virtuali non sono sempre dinamiche. Quando vengono effettuate chiamate su un oggetto di cui è noto il tipo esatto (poiché l'oggetto non è un puntatore o un riferimento o perché il suo tipo può essere inferito in modo statico), le chiamate sono solo normali chiamate di funzioni membro. Ciò non significa solo che non vi è un overhead di spedizione, ma anche che queste chiamate possono essere allineate allo stesso modo delle normali chiamate.

In altre parole, il compilatore C ++ può funzionare quando le funzioni virtuali non richiedono la distribuzione virtuale, quindi di solito non c'è motivo di preoccuparsi delle loro prestazioni rispetto alle funzioni non virtuali.

Novità: Inoltre, non dobbiamo dimenticare le librerie condivise. Se stai usando una classe che si trova in una libreria condivisa, la chiamata a una funzione membro ordinaria non sarà semplicemente una bella sequenza di istruzioni come callq 0x4007aa . Deve passare attraverso alcuni cerchi, come fare riferimento a una "tabella di collegamento del programma" o ad una struttura di questo tipo. Pertanto, l'indiretta della libreria condivisa potrebbe in qualche modo (se non completamente) livellare la differenza di costo tra una chiamata virtuale (veramente indiretta) e una chiamata diretta. Quindi ragionare sui compromessi delle funzioni virtuali deve tenere conto di come è stato costruito il programma: se la classe dell'oggetto di destinazione è collegata in modo monolitico al programma che sta effettuando la chiamata.

    
risposta data 23.03.2013 - 01:29
fonte
12

perché una chiamata virtuale è equivalente a

res_t (*foo)(arg_t);
foo = (obj->vtable[foo_offset]);
foo(obj,args)

dove con una funzione non virtuale il compilatore può piegare costantemente la prima riga, questa è una dereferenza un'aggiunta e una chiamata dinamica trasformata in una semplice chiamata statica

anche questo consente di allineare la funzione (con tutte le conseguenti conseguenze di ottimizzazione)

    
risposta data 23.03.2013 - 00:06
fonte

Leggi altre domande sui tag