ottimizzazione di accesso ai membri in C++

Question

che sto funzionando in un comportamento ottimizzazione incoerente con differenti compilatori per il codice seguente:

class tester 
{ 
public: 
    tester(int* arr_, int sz_) 
     : arr(arr_), sz(sz_) 
    {} 

    int doadd() 
    { 
     sm = 0; 
     for (int n = 0; n < 1000; ++n) 
     { 
      for (int i = 0; i < sz; ++i) 
      { 
       sm += arr[i]; 
      } 
     } 
     return sm; 
    } 
protected: 
    int* arr; 
    int sz; 
    int sm; 
}; 

La funzione doadd simula qualche accesso intensivo ai membri (ignorare i overflow in aggiunta per questa domanda). Rispetto al codice simile implementato come una funzione:

int arradd(int* arr, int sz) 
{ 
    int sm = 0; 
    for (int n = 0; n < 1000; ++n) 
    { 
     for (int i = 0; i < sz; ++i) 
     { 
      sm += arr[i]; 
     } 
    } 
    return sm; 
} 

Il metodo doadd corre circa 1,5 volte più lento rispetto alla funzionearradd quando compilato in modalità di rilascio con Visual C++ 2008. Quando modifico il metodo doadd essere il seguente (aliasing tutti i membri con i locali):

int doadd() 
{ 
    int mysm = 0; 
    int* myarr = arr; 
    int mysz = sz; 
    for (int n = 0; n < 1000; ++n) 
    { 
     for (int i = 0; i < mysz; ++i) 
     { 
      mysm += myarr[i]; 
     } 
    } 
    sm = mysm; 
    return sm; 
} 

I runtime diventano più o meno gli stessi. Ho ragione nel concludere che questa è una ottimizzazione mancante dal compilatore Visual C++? g++ sembra farlo meglio ed eseguire sia la funzione membro che la funzione normale alla stessa velocità durante la compilazione con -O2 o -O3.

---

L'analisi comparativa è fatto invocando la funzione doadd membro e arradd su alcuni sufficientemente grande matrice (alcuni milioni di numeri interi di dimensione).

---

EDIT: Alcuni test a grana fine mostra che il colpevole principale è il membro sm. Sostituire tutti gli altri con le versioni locali rende ancora il runtime lungo, ma una volta che ho sostituito sm da mysm il runtime diventa uguale alla versione della funzione.

---

Risoluzione

deluso con le risposte (mi dispiace), ho Shaked fuori la mia pigrizia e colomba nelle liste di smontaggio di questo codice. Il mio answer below riassume i risultati. In breve: non ha nulla a che fare con l'aliasing, ha a che fare con lo srotolamento del ciclo e con alcune strane euristiche MSVC si applica quando si decide quale ciclo eseguire.

Answer 1

Ho smontato il codice con MSVC per capire meglio cosa sta succedendo. Risulta che l'aliasing non era affatto un problema e nemmeno una sorta di sicurezza paranoica.

Qui è la parte interessante della funzione arradd disassambled:

for (int n = 0; n < 10; ++n) 
    { 
     for (int i = 0; i < sz; ++i) 
013C101C mov   ecx,ebp 
013C101E mov   ebx,29B9270h 
     { 
      sm += arr[i]; 
013C1023 add   eax,dword ptr [ecx-8] 
013C1026 add   edx,dword ptr [ecx-4] 
013C1029 add   esi,dword ptr [ecx] 
013C102B add   edi,dword ptr [ecx+4] 
013C102E add   ecx,10h 
013C1031 sub   ebx,1 
013C1034 jne   arradd+23h (13C1023h) 
013C1036 add   edi,esi 
013C1038 add   edi,edx 
013C103A add   eax,edi 
013C103C sub   dword ptr [esp+10h],1 
013C1041 jne   arradd+16h (13C1016h) 
013C1043 pop   edi 
013C1044 pop   esi 
013C1045 pop   ebp 
013C1046 pop   ebx 

ecx punti alla matrice, e si può vedere che l'anello interno sia srotolato x4 qui - notare le quattro consecutivi add istruzioni seguenti indirizzi e ecx avanzato di 16 byte (4 parole) alla volta all'interno del ciclo.

Per la versione non ottimizzata della funzione di membro, doadd:

int tester::doadd() 
{ 
    sm = 0; 
    for (int n = 0; n < 10; ++n) 
    { 
     for (int i = 0; i < sz; ++i) 
     { 
      sm += arr[i]; 
     } 
    } 
    return sm; 
} 

Lo smontaggio è (è più difficile da trovare in quanto il compilatore inline in main):

int tr_result = tr.doadd(); 
013C114A xor   edi,edi 
013C114C lea   ecx,[edi+0Ah] 
013C114F nop    
013C1150 xor   eax,eax 
013C1152 add   edi,dword ptr [esi+eax*4] 
013C1155 inc   eax 
013C1156 cmp   eax,0A6E49C0h 
013C115B jl   main+102h (13C1152h) 
013C115D sub   ecx,1 
013C1160 jne   main+100h (13C1150h) 

Nota 2 cose:

• La somma è memorizzata in un registro - edi. Quindi, non c'è l'aliasing "attenzione" scattata qui. Il valore di sm non viene riletto continuamente.edi è inizializzato solo una volta e quindi utilizzato come temporaneo. Non si vede il suo ritorno dal momento che il compilatore lo ha ottimizzato e utilizzato edi direttamente come valore di ritorno del codice inserito.
• Il ciclo non viene srotolato. Perché? Nessuna buona ragione

Infine, ecco una versione "ottimizzata" della funzione membro, con mysm mantenendo la somma locale manualmente:

int tester::doadd_opt() 
{ 
    sm = 0; 
    int mysm = 0; 
    for (int n = 0; n < 10; ++n) 
    { 
     for (int i = 0; i < sz; ++i) 
     { 
      mysm += arr[i]; 
     } 
    } 
    sm = mysm; 
    return sm; 
} 

The (di nuovo, inline) smontaggio è:

int tr_result_opt = tr_opt.doadd_opt(); 
013C11F6 xor   edi,edi 
013C11F8 lea   ebp,[edi+0Ah] 
013C11FB jmp   main+1B0h (13C1200h) 
013C11FD lea   ecx,[ecx] 
013C1200 xor   ecx,ecx 
013C1202 xor   edx,edx 
013C1204 xor   eax,eax 
013C1206 add   ecx,dword ptr [esi+eax*4] 
013C1209 add   edx,dword ptr [esi+eax*4+4] 
013C120D add   eax,2 
013C1210 cmp   eax,0A6E49BFh 
013C1215 jl   main+1B6h (13C1206h) 
013C1217 cmp   eax,0A6E49C0h 
013C121C jge   main+1D1h (13C1221h) 
013C121E add   edi,dword ptr [esi+eax*4] 
013C1221 add   ecx,edx 
013C1223 add   edi,ecx 
013C1225 sub   ebp,1 
013C1228 jne   main+1B0h (13C1200h) 

Il loop qui è srotolato, ma solo x2.

Questo spiega abbastanza bene le mie osservazioni sulla differenza di velocità. Per un array 175e6, la funzione esegue ~ 1,2 secondi, il membro non ottimizzato ~ 1,5 secondi e il membro ottimizzato ~ 1,3 secondi. (Nota che questo potrebbe differire per te, su un altro computer ho avuto runtime più ravvicinati per tutte e 3 le versioni).

E a proposito di gcc? Una volta compilato, tutte e 3 le versioni funzionavano a ~ 1.5 sec. Sospettando la mancanza di srotolamento ho visto lo smontaggio dello gcc e infatti: gcc non srotola nessuna delle versioni.

Answer 2

Può essere un problema di aliasing - il compilatore non può sapere che l'istanza variabile sm non sarà mai puntato da arr, quindi deve trattare sm come se fosse effettivamente volatile, e salvarlo su ogni iterazione. Potresti rendere sm un tipo diverso per verificare questa ipotesi. O semplicemente utilizzare una somma locale temporanea (che verrà memorizzata nella cache in un registro) e assegnarla a sm alla fine.

Answer 3

Come ha scritto Paul, probabilmente è perché il membro sm viene aggiornato ogni volta nella memoria "reale", mentre il riepilogo locale nella funzione può essere accumulato nella variabile di registro (dopo l'ottimizzazione del compilatore).

Answer 4

È possibile ottenere problemi simili passando gli argomenti del puntatore. Se ti piace sporcarti le mani, potresti trovare utile la parola chiave restrict in futuro.

http://developers.sun.com/solaris/articles/cc_restrict.html

Answer 5

Questo non è proprio lo stesso codice a tutti. Se metti le variabili sm, arr e sz all'interno della classe invece di rendere locale il tema, il compilatore non può (facilmente) indovinare che alcune altre classi non erediteranno dalla classe test e vorranno accedere a questi membri, facendo qualcosa del tipo ` arr = &sm; doadd() ;. D'ora in poi, l'accesso a queste variabili non può essere ottimizzato come possono quando sono locali per funzionare.

Alla fine il motivo è fondamentalmente quello indicato da Paolo, sm viene aggiornato nella memoria reale quando si utilizza un membro della classe, può essere memorizzato in un registro quando in una funzione. Le letture della memoria da aggiungere non dovrebbero cambiare molto il tempo risultante, poiché la memomry deve essere letta comunque per ottenere il valore.

In questo caso, se il test non viene esportato in un altro modulo e non viene sottoposto ad alias anche indirettamente a qualcosa esportato, e se non vi è aliasing come sopra. Il compilatore potrebbe ottimizzare le scritture intermedie in sm ... alcuni compilatori come gcc sembrano ottimizzare in modo abbastanza aggressivo per rilevare casi sopra (sarebbe anche se la classe di test venisse esportata). Ma queste sono ipotesi davvero difficili. Esistono ancora ottimizzazioni molto più semplici che non sono ancora state eseguite dai compilatori (come l'inlining attraverso diverse unità di compilazione).

Answer 6

MSVC è corretto, in quanto è l'unico che, visto il codice che abbiamo visto, è garantito che funzioni correttamente. GCC impiega ottimizzazioni che probabilmente sono sicure in questa specifica istanza, ma che possono essere verificate solo vedendo più del programma.

Poiché sm non è una variabile locale, MSVC sembra presupporre che potrebbe essere alias arr. Questa è un'ipotesi abbastanza ragionevole: poiché arr è protetto, una classe derivata potrebbe impostarlo in modo che punti a sm, quindi arrpotrebbe alias sm.

GCC vede che in realtà non è alias arr, e quindi non scrive sm in memoria fino a dopo il ciclo, che è molto più veloce.

È possibile istanziare la classe in modo che arr punti a sm, che MSVC gestirà, ma GCC non lo farebbe.

Supponendo che sz > 1, l'ottimizzazione GCC sia consentita in generale.

Poiché la funzione scorre sopra arr, trattandolo come un array di elementi sz, chiamando la funzione con sz > 1 produrrebbe un comportamento indefinito o meno arr alias sm, e così GCC può tranquillamente supporre che Non alias . Ma se sz == 1, o se il compilatore non può essere sicuro di quello che potrebbe essere il valore s' sz, allora si corre il rischio che szpotrebbe essere 1, e così arr e sm potrebbe alias perfettamente legale, e il codice di GCC si romperebbe.

Quindi, molto probabilmente, GCC riesce semplicemente a farla franca integrando il tutto e vedendo che in questo caso, non sono alias.

Answer 7

La chiave è probabilmente che doadd è scritto in questo modo se si effettua il membro accede esplicito con this:

int doadd() 
{ 
    this->sm = 0; 

    for (int n = 0; n < 1000; ++n) 
    { 
     for (int i = 0; i < this->sz; ++i) 
     { 
      this->sm += this->arr[i]; 
     } 
    } 

    return this->sm; 
} 

qui sta il problema: tutti i membri della classe sono accessibili tramite il puntatore this, mentre arradd ha tutto variabili in pila. Per velocizzarlo, hai scoperto che spostando tutti i membri nello stack come variabili locali, la velocità corrisponde a arradd. Quindi questo indica che l'induzione diretta di this è responsabile della perdita di prestazioni.

Perché potrebbe essere? A quanto ho capito, lo this di solito è memorizzato in un registro quindi non penso che alla fine sia più lento dell'accesso allo stack (che è anche un offset nel puntatore dello stack). Come altre risposte sottolineano, è probabilmente il problema di aliasing che genera codice meno ottimale: il compilatore non può stabilire se uno qualsiasi degli indirizzi di memoria si sovrappone. L'aggiornamento sm potrebbe anche in teoria modificare il contenuto di arr, quindi decide di scrivere il valore di sm nella memoria principale ogni volta invece di rintracciarlo in un registro. Quando le variabili sono in pila, il compilatore può assumere che sono tutti in indirizzi di memoria diversi. Il compilatore non vede il programma con la stessa chiarezza con cui lo si fa: può dire cosa c'è nello stack (perché lo hai dichiarato in quel modo), ma tutto il resto sono solo indirizzi di memoria arbitrari che potrebbero essere qualsiasi cosa, ovunque, sovrapponendosi a qualsiasi altro puntatore.

Non mi sorprende l'ottimizzazione nella tua domanda (utilizzando le variabili locali) non è fatto - non solo il compilatore dimostrare la memoria di arr non si sovrappone nulla puntata da this, ma anche che non aggiorna le variabili membro fino alla fine della funzione sono equivalenti all'aggiornamento non ottimizzato della versione in tutta la funzione. Questo può essere molto più complicato da determinare di quanto tu immagini, specialmente se prendi in considerazione la concorrenza.