È possibile memorizzare nella cache una ricerca di funzioni virtuali in C++?

Question

Dire che ho una chiamata di funzione virtuale foo() su un puntatore astratto di classe base, mypointer-> foo(). Quando la mia app si avvia, in base al contenuto di un file, sceglie di istanziare una particolare classe concreta e assegna mypointer a quell'istanza. Per il resto della vita dell'app, mypointer sarà sempre puntare agli oggetti di quel tipo concreto. Non ho modo di sapere cosa sia questo tipo concreto (può essere istanziato da una fabbrica in una libreria caricata dinamicamente). So solo che il tipo rimarrà lo stesso dopo la prima volta che viene eseguita un'istanza del tipo concreto. Il puntatore potrebbe non puntare sempre allo stesso oggetto, ma l'oggetto sarà sempre dello stesso tipo concreto. Si noti che il tipo è determinato tecnicamente in "runtime" perché è basato sul contenuto di un file, ma che dopo "avvio" (il file è caricato) il tipo è fisso.

Tuttavia, in C++ pago il costo di ricerca della funzione virtuale ogni volta che viene chiamato foo per l'intera durata dell'app. Il compilatore non può ottimizzare il look up perché non c'è modo di sapere che il tipo di calcestruzzo non varierà in fase di esecuzione (anche se è stato il compilatore più incredibile di sempre, non può speculare sul comportamento del carico dinamico biblioteche). In un linguaggio JIT compilato come Java o .NET, il JIT può rilevare che lo stesso tipo viene utilizzato più volte e lo fa inline cacheing. Sono fondamentalmente alla ricerca di un modo per farlo manualmente per puntatori specifici in C++.

C'è qualche modo in C++ per memorizzare questa ricerca nella cache? Mi rendo conto che le soluzioni potrebbero essere piuttosto schifose. Sono disposto ad accettare gli hack specifici di ABI/compilatore se è possibile scrivere test di configurazione che scoprano gli aspetti rilevanti dell'ABI/compilatore in modo che sia "praticamente portatile" anche se non veramente portatile.

Aggiornamento: Per gli oppositori: se non valeva la pena ottimizzare, allora dubito che le moderne JIT lo farebbero. Pensi che gli ingegneri di Sun e MS stiano sprecando il loro tempo nell'implementazione dell'archiviazione in linea e non l'abbiano messo a punto per garantire un miglioramento?

Answer 1

Quindi supponendo che si tratta di una questione fondamentale che si vuole risolvere (per evitare discussioni premature di ottimizzazione), e ignorando la piattaforma e aggiustamenti specifici compilatore, si può fare una delle due cose, alle estremità opposte della complessità:

1. Fornire una funzione come parte della DLL che internamente chiama direttamente la funzione membro destra. Paghi il costo di un salto indiretto, ma almeno non paghi il costo di una ricerca vtable. Il tuo chilometraggio può variare, ma su alcune piattaforme, è possibile ottimizzare la chiamata di funzione indiretta.
2. Ristruttura l'applicazione in modo tale che invece di chiamare una funzione membro per istanza, si chiami una singola funzione che accetta una raccolta di istanze. Mike Acton ha un meraviglioso post (con una particolare piattaforma e tipo di applicazione piegato) sul perché e come dovresti farlo.

Answer 2

Ci sono due costi per una chiamata di funzione virtuale: la ricerca vtable e la chiamata di funzione.

La ricerca di vtable è già gestita dall'hardware. Le moderne CPU (supponendo che non si stia lavorando su una CPU embedded molto semplice) prevedono l'indirizzo della funzione virtuale nel predittore del ramo e lo eseguono in modo speculativo in parallelo con la ricerca dell'array. Il fatto che la ricerca vtable avvenga in parallelo con l'esecuzione speculativa della funzione significa che, quando eseguite in un ciclo nelle situazioni che descrivi, le chiamate alle funzioni virtuali hanno un overhead vicino allo zero rispetto alle chiamate di funzione dirette non inline.

In realtà l'ho provato in passato, anche se nel linguaggio di programmazione D, non in C++.Quando l'inlining è stato disabilitato nelle impostazioni del compilatore e ho chiamato la stessa funzione in un loop diverse milioni di volte, i tempi erano tra loro a prescindere se la funzione era virtuale o meno.

Il secondo e più importante costo delle funzioni virtuali è che impediscono la funzione di allineamento della maggior parte dei casi. Questo è ancora più importante di quanto sembri perché l'inlining è un'ottimizzazione che può abilitare diverse altre ottimizzazioni come il folding costante in alcuni casi. Non c'è modo di inline una funzione senza ricompilare il codice. Le JIT riescono a risolverlo perché stanno continuamente ricompilando il codice durante l'esecuzione della tua applicazione.

Answer 3

Ho visto situazioni in cui evitare una chiamata di funzione virtuale è vantaggioso. Questo non mi sembra uno di quei casi perché stai usando la funzione in modo polimorfico. Stai solo cercando un indirizzo indiretto in più, non un grande successo, e uno che potrebbe essere parzialmente ottimizzato in alcune situazioni. Se è davvero importante, è possibile ristrutturare il codice in modo che le scelte dipendenti dal tipo, come le chiamate alle funzioni virtuali, vengano eseguite un numero inferiore di volte, trascinate all'esterno dei cicli.

Se si ritiene che valga la pena dargli un colpo, è possibile impostare un puntatore a funzione separata su una funzione non virtuale specifica della classe. I potrebbe (ma probabilmente non lo farebbe) considerare di farlo in questo modo.

class MyConcrete : public MyBase 
{ 
public: 
    static void foo_nonvirtual(MyBase* obj); 
    virtual void foo() 
    { foo_nonvirtual(this); } 
}; 

void (*f_ptr)(MyBase* obj) = &MyConcrete::foo_nonvirtual; 
// Call f_ptr instead of obj->foo() in your code. 
// Still not as good a solution as restructuring the algorithm. 

Oltre rendendo l'algoritmo stesso un po 'più saggi, sospetto qualsiasi tentativo di ottimizzare manualmente la chiamata di funzione virtuale causerà più problemi di quanti ne risolva.

Answer 4

Tutte le risposte si riferiscono allo scenario più semplice, in cui la chiamata a un metodo virtuale richiede solo l'ottenimento dell'indirizzo del metodo effettivo da chiamare. Nel caso generale, quando entrano in gioco eredità multiple e virtuali, chiamare un metodo virtuale richiede lo spostamento del puntatore this.

Il meccanismo di invio del metodo può essere implementato in più di un modo, ma è comune scoprire che la voce nella tabella virtuale non è il metodo effettivo da chiamare, ma piuttosto un codice intermedio "trampolino" inserito dal compilatore che trasferisce il puntatore this prima di chiamare il metodo effettivo.

Quando la spedizione è la più semplice, basta un reindirizzamento del puntatore in più, quindi cercare di ottimizzarlo non ha senso. Quando il problema è più complesso, qualsiasi soluzione sarà dipendente dal compilatore e hacker. Inoltre, non sai nemmeno in quale scenario sei: se gli oggetti sono caricati da DLL, non sai realmente se l'istanza restituita appartiene ad una semplice gerarchia di ereditarietà lineare o ad uno scenario più complesso.

Answer 5

Perché la chiamata virtuale è costosa? Perché semplicemente non si conosce la destinazione del ramo finché il codice non viene eseguito in runtime. Persino le CPU moderne gestiscono perfettamente la chiamata virtuale e le chiamate indirette. Non si può semplicemente dire che non costa nulla perché abbiamo solo una CPU più veloce. No non lo è.

1. Come possiamo farlo velocemente?

Hai già una profonda comprensione del problema. Ma, l'unica cosa che posso dire è che se la chiamata alla funzione virtuale è facile da prevedere, è possibile eseguire l'ottimizzazione a livello di software. Ma, se non lo è (cioè, non hai davvero idea di quale sarebbe l'obiettivo della funzione virtuale), allora non penso che ci sia una buona soluzione per ora. Anche per la CPU, è difficile prevedere in questo caso estremo.

In realtà, i compilatori come PGO di Visual C++ (ottimizzazione guidata di Profiling) hanno l'ottimizzazione speculazione di chiamata virtuale (Link). Se il risultato della definizione del profilo è in grado di enumerare hot target di funzioni virtuali, viene convertito in chiamata diretta che può essere sottolineata. Si chiama anche devirtualization. Può anche essere trovato in alcuni ottimizzatori dinamici Java.

2. Per coloro che dicono quello che non è necessario

Se stai usando linguaggi di script, C# e preoccupazione per l'efficienza di codifica, sì, è inutile. Tuttavia, chiunque sia desideroso di salvare un singolo ciclo per ottenere prestazioni migliori, il ramo indiretto è ancora un problema importante. Anche le ultime CPU non sono buone per gestire le chiamate virtuali. Un buon esempio potrebbe essere una macchina virtuale o un interprete, che di solito hanno un interruttore molto grande. Le sue prestazioni sono praticamente correlate alla corretta previsione del ramo indiretto. Quindi, non puoi semplicemente dire che è troppo basso o non necessario. Ci sono centinaia di persone che stanno cercando di migliorare le prestazioni in basso. Ecco perché si può semplicemente ignorare tali dettagli :)

3. Alcuni di computer fatti architettonici noiosi relativi a funzioni virtuali

dsimcha ha scritto una buona risposta per come CPU in grado di gestire in modo efficace chiamata virtuale. Ma non è esattamente corretto. Innanzitutto, tutte le CPU moderne hanno un predittore di branche, che predice letteralmente i risultati di un ramo per aumentare il throughput della pipeline (o, più parallelismo nel livello di istruzione, o ILP. Posso anche dire che le prestazioni della CPU a thread singolo dipendono esclusivamente da quanto può estrarre ILP da un singolo thread.La predizione del ramo è il fattore più critico per ottenere un ILP superiore).

Nella previsione ramo, ci sono due previsioni: (1) direzione (cioè, il ramo è preso o non preso? Risposta binaria), e (2) ramo bersaglio (cioè, dove andrò? Non è binario risposta). In base alla previsione, CPU speculativamente esegue il codice. Se la speculazione non è corretta, i rollback della CPU si riavvieranno dal ramo previsto erroneamente. Questo è completamente nascosto dalla vista del programmatore. Quindi, non sai veramente cosa sta succedendo all'interno della CPU a meno che tu non stia profilando con VTune, il che dà dei tassi di errata interpretazione delle filiali.

In generale, la previsione della direzione delle diramazioni è estremamente accurata (95% +), ma è ancora difficile prevedere gli obiettivi delle diramazioni, in particolare le chiamate virtuali e le case di scambio (ad esempio, la tabella di salto). La chiamata virtuale è diramazione indiretta che richiede un maggiore carico di memoria e anche la CPU richiede la previsione del target di diramazione. CPU moderne come Intel Nehalem e AMD Phenom hanno una tabella di destinazione indiretta specializzata.

Tuttavia, non penso che la ricerca di vtable incoraggi un sacco di spese generali. Sì, richiede un maggior carico di memoria che può far perdere la cache. Ma, una volta che vtable è caricato nella cache, allora è quasi un hit nella cache. Se sei interessato anche a quel costo, puoi inserire prefetching code per caricare vtable in anticipo. Ma la vera difficoltà della chiamata di funzioni virtuali è che la CPU non può fare un ottimo lavoro per predire l'obiettivo della chiamata virtuale, il che può causare frequenti perdite di gasdotto a causa di una predizione errata del target.

Answer 6

È possibile utilizzare un puntatore del metodo?

L'obiettivo è che il compilatore carica il puntatore con la posizione del metodo o della funzione risolti. Questo accadrebbe una volta. Dopo l'assegnazione, il codice accederà al metodo in modo più diretto.

So che un puntatore a un oggetto e l'accesso al metodo tramite il punto dell'oggetto invoca il polimorfismo di runtime . Tuttavia, dovrebbe esserci un modo per caricare un puntatore del metodo su un metodo risolto, evitando il polimorfismo e chiamando direttamente la funzione.

Ho controllato la wiki della comunità per introdurre ulteriori discussioni.

Answer 7

Non è possibile utilizzare un puntatore del metodo poiché i puntatori alle funzioni membro non sono considerati tipi di ritorno covarianti. Vedere l'esempio di seguito:

#include <iostream> 

struct base; 
struct der; 

typedef void(base::*pt2base)(); 
typedef void(der::*pt2der)(); 

struct base { 
    virtual pt2base method() = 0; 
    virtual void testmethod() = 0; 
    virtual ~base() {} 
}; 

struct der : base { 
    void testmethod() { 
     std::cout << "Hello from der" << std::endl; 
    } 
    pt2der method() { **// this is invalid because pt2der isn't a covariant of pt2base** 
     return &der::testmethod; 
    } 
}; 

L'altra opzione sarebbe quella di avere il metodo dichiarato pt2base method() ma poi il ritorno sarebbe valida perché der :: TestMethod non è di tipo pt2base.

Anche se si avesse un metodo che ha ricevuto un ptr o un riferimento al tipo di base, si dovrebbe eseguire il cast dinamico sul tipo derivato in quel metodo per fare qualcosa di particolarmente polimorfo che riattiva il costo che stiamo provando salvare.

Answer 8

Quindi, ciò che fondamentalmente si vuole fare è convertire il polimorfismo runtime in polimorfismo del tempo di compilazione. Ora hai ancora bisogno di costruire la tua app in modo che possa gestire più "casi", ma una volta deciso quale caso è applicabile a un'esecuzione, è tutto per la durata.

Ecco un modello del caso runtime polimorfismo:

struct Base { 
    virtual void doit(int&)=0; 
}; 

struct Foo : public Base { 
    virtual void doit(int& n) {--n;} 
}; 

struct Bar : public Base { 
    virtual void doit(int& n) {++n;} 
}; 

void work(Base* it,int& n) { 
    for (unsigned int i=0;i<4000000000u;i++) it->doit(n); 
} 

int main(int argc,char**) { 
    int n=0; 

    if (argc>1) 
    work(new Foo,n); 
    else 
    work(new Bar,n); 

    return n; 
} 

Questo richiede ~ 14s per eseguire sul mio Core2, compilato con gcc 4.3.2 (32 bit Debian), -O3 opzione.

Supponiamo ora di sostituire la versione "lavoro" con una versione su modelli (su modelli dal tipo di cemento che sta per essere al lavoro su):

template <typename T> void work(T* it,int& n) { 
    for (unsigned int i=0;i<4000000000u;i++) it->T::doit(n); 
} 

main in realtà non hanno bisogno di essere aggiornato, ma nota che le 2 chiamate a work attivano ora le istanze e le chiamate a due funzioni diverse e specifiche del tipo (vedere la funzione polimorfica precedente).

Hey presto corre in 0.001s. Non un brutto fattore di accelerazione per un cambio di 2 linee! Tuttavia, si noti che la massiccia accelerazione è interamente dovuta al compilatore, una volta eliminata la possibilità del polimorfismo di runtime nella funzione work, semplicemente ottimizzando il ciclo e compilando il risultato direttamente nel codice. Ma questo in realtà rende un punto importante: nella mia esperienza i principali vantaggi derivanti dall'utilizzo di questo tipo di trucco derivano dalle migliorie di ottimizzazione e ottimizzazione che consentono al compilatore quando viene generata una funzione meno polimorfica e più specifica, non dal semplice rimozione di riferimento indiretto (che è davvero molto economico).

Ma io davvero non consiglio di fare cose del genere a meno che il profiling non indichi assolutamente che il polimorfismo del runtime sta davvero colpendo la tua performance. Ti morderà anche non appena qualcuno sottoclasse Foo o Bar e cerchi di passarlo in una funzione effettivamente destinata alla sua base.

Potresti trovare interessante anche this related question.

Answer 9

ho fatto una domanda molto simile di recente, e ha ottenuto la risposta che è possibile come estensione GCC, ma non portabile:

C++: Pointer to monomorphic version of virtual member function?

In particolare, ho anche provato con Clang e doesn' t supporta questa estensione (anche se supporta molte altre estensioni GCC).