Struttura di array e array di strutture - differenza di prestazioni

Question

Ho una classe come questa:

//Array of Structures 
class Unit 
{ 
    public: 
    float v; 
    float u; 
    //And similarly many other variables of float type, upto 10-12 of them. 
    void update() 
    { 
     v+=u; 
     v=v*i*t; 
     //And many other equations 
    } 
}; 

Creo un array di oggetti di tipo Unit. E chiama l'aggiornamento su di loro.

int NUM_UNITS = 10000; 
void ProcessUpdate() 
{ 
    Unit *units = new Unit[NUM_UNITS]; 
    for(int i = 0; i < NUM_UNITS; i++) 
    { 
    units[i].update(); 
    } 
} 

Al fine di accelerare le cose, e possibilmente autovectorize ciclo, i convertiti AoS strutturare degli array.

//Structure of Arrays: 
class Unit 
{ 
    public: 
    Unit(int NUM_UNITS) 
    { 
    v = new float[NUM_UNITS]; 
    } 
    float *v; 
    float *u; 
    //Mnay other variables 
    void update() 
    { 
    for(int i = 0; i < NUM_UNITS; i++) 
    { 
     v[i]+=u[i]; 
     //Many other equations 
    } 
    } 
}; 

Quando il ciclo non riesce ad autotetettizzare, sto ottenendo una prestazione pessima per la struttura degli array. Per 50 unità, l'aggiornamento di SoA è leggermente più veloce di AoS. Ma da 100 unità in poi, SoA è più lento di AoS. A 300 unità, SoA è quasi il doppio peggiore. A 100K unità, SoA è 4x più lento di AoS. Mentre la cache potrebbe essere un problema per SoA, non mi aspettavo che la differenza di prestazioni fosse così alta. Il profiling su cachegrind mostra un numero simile di errori per entrambi gli approcci. La dimensione di un oggetto Unit è 48 byte. La cache L1 è 256K, L2 è 1MB e L3 è 8MB. Cosa mi manca qui? È davvero un problema di cache?

Modifica: Sto utilizzando gcc 4.5.2. Le opzioni del compilatore sono -o3 -msse4 -ftree-vectorize.

Ho fatto un altro esperimento in SoA. Invece di allocare dinamicamente gli array, ho allocato "v" e "u" in fase di compilazione. Quando ci sono unità da 100 K, ciò fornisce una prestazione che è 10 volte più veloce della SoA con array allocati dinamicamente. Cosa sta succedendo qui? Perché c'è una tale differenza di prestazioni tra memoria statica e memoria allocata dinamicamente?

Answer 1

In questo caso, la struttura degli array non è cache-friendly.

È possibile utilizzare sia u sia v insieme, ma in caso di 2 array diversi non verranno caricati simultaneamente in una riga della cache e le perdite di cache avranno un costo enorme.

_mm_prefetch può essere utilizzato per rendere la rappresentazione di AoS ancora più veloce.

Answer 2

I prefetches sono fondamentali per il codice che trascorre la maggior parte del tempo di esecuzione in attesa che i dati vengano visualizzati. I moderni bus front side hanno una larghezza di banda sufficiente che dovrebbe essere sicura, a condizione che il programma non stia andando troppo avanti rispetto al suo attuale insieme di carichi.

Per vari motivi, strutture e classi possono creare numerosi problemi di prestazioni in C++ e possono richiedere più modifiche per ottenere livelli accettabili di prestazioni. Quando il codice è grande, utilizzare la programmazione orientata agli oggetti. Quando i dati sono grandi (e le prestazioni sono importanti), non farlo.

float v[N]; 
float u[N]; 
    //And similarly many other variables of float type, up to 10-12 of them. 
//Either using an inlined function or just adding this text in main() 
     v[j] += u[j]; 
     v[j] = v[j] * i[j] * t[j]; 

Answer 3

Certo, se non si ottiene vettorializzazione, non c'è molto incentivo a fare una trasformazione SOA.

Oltre all'accettazione de facto abbastanza ampia di __RESTRICT, gcc 4.9 ha adottato #pragma GCC ivdep per interrompere le dipendenze di aliasing presunte.

Per quanto riguarda l'uso del prefetch esplicito, se è utile, ovviamente è possibile che ne siano necessari altri con SoA. Il punto principale potrebbe essere quello di accelerare la risoluzione delle missioni DTLB recuperando le pagine in anticipo, in modo che l'algoritmo potrebbe diventare più affamato di cache.

Non credo che commenti intelligenti possano essere fatti su qualsiasi cosa tu chiami allocazione "tempo di compilazione" senza ulteriori dettagli, comprese le specifiche sul tuo sistema operativo. Non c'è dubbio che la tradizione di allocare ad alto livello e riutilizzare l'allocazione è importante.