Perché gli elementi di un'enorme struttura allocata dinamicamente sono molto più lenti di una piccola matrice allocata dinamicamente in C ++?

Hai alcune ottime risposte sull'argomento qui

Generalmente, la tua struttura è probabilmente troppo grande per la cache della CPU, quindi probabilmente parti di essa finiscono nella cache L2 o nella memoria RAM, che è significativamente più lenta della cache L1, quindi problemi di prestazioni. Potresti provare a fare un po 'di profilazione e scoprire esattamente cosa sta succedendo. Se lo fai, mi piacerebbe molto leggere i risultati.

Se ti stai sforzando per ottenere prestazioni, chiediti perché hai bisogno di una struttura con due array di quelle dimensioni? Potresti ottenere prestazioni simili se avessi solo puntatori int e quindi allocare gli array in modo dinamico come necessario? Potresti semplicemente perdere la struttura e gestire i membri in modo indipendente? So che l'ultimo approccio è molto brutto, ma quando la performance è l'ultima richiesta, devono essere fatti dei sacrifici nella leggibilità del codice.

Come accennato nei commenti, è impossibile dirlo con certezza, senza vedere cosa produce il compilatore e vedere come il sistema operativo gestisce l'allocazione della memoria. Ma possiamo prendere qualche ipotesi educata. Nei sistemi operativi moderni, quando si assegna memoria, è possibile che sia riservato ma non ancora cablato. In altre parole, il sistema operativo controlla se c'è spazio sufficiente nello spazio di indirizzamento virtuale per soddisfare la richiesta, ma se lo è, lo farà basta prenotare l'intervallo. In realtà non prenderà alcuna azione per rendere la memoria disponibile per l'uso. Aspetta fino a quando non tenti di toccare un byte della memoria prima di collegare effettivamente quella memoria alla memoria reale. Quando tocchi un byte della memoria, il sistema operativo cercherà di vedere se c'è una memoria fisica disponibile per contenere quel blocco di memoria virtuale. In tal caso, contrassegna quel blocco come in uso e il tuo codice inizierà a utilizzarlo. Ci vuole tempo per fare quel controllo e contrassegnare il blocco per l'uso.

Nel caso dell'allocazione più piccola, potrebbero esserci solo poche decine di blocchi di memoria virtuale che devono essere portati nella memoria fisica per l'uso. Ma per l'allocazione più ampia, mentre attraversi il blocco per passi più ampi, questi controlli e segni vengono eseguiti più frequentemente e ciò rallenta la scrittura.

Guardando la tua struttura, un modo per aggirarlo sarebbe non creare una struttura così grande. Se quei 2 array potessero essere solo puntatori assegnati quando necessario, la struttura sarebbe molto più piccola e non soffrirebbe così gravemente di questo problema. (Anche se sarebbe ancora peggio della matrice del caso int s.)

Come altri hanno già detto, la principale differenza di prestazioni è probabilmente dovuta ai diversi profili di pagina di memoria. Per l'array int , probabilmente stai mappando circa 100 pagine di memoria virtuale su fisico mentre l'array struct sta mappando circa 100.000. Sto assumendo 4k pagine e 32 bit int s ma i numeri sembrano gelificare con quello che stai vedendo.

La tua seconda domanda è: cosa fai a riguardo? Come spesso accade con queste cose, la risposta è che dipende.

Ora, se ti aspetti che l'iterazione sul campo n sia un'operazione comune, allora sei fortunato. Il modo in cui hai strutturato i tuoi dati è ciò che è noto come Array of Structs (AoS). Come suggerisce il nome, hai creato una serie di strutture. Esiste un'alternativa che viene utilizzata in applicazioni che elaborano array regolari di grandi dimensioni come il tuo e che, astutamente, si chiama Struct of Arrays (SoA).

Quindi, per il tuo esempio, cambieresti il codice come segue:

#define NT 100000

typedef struct {
    float ind_1[4096][NT];
    float ind_2[4096][NT];
    int n[NT];
 } ind_vec_SoA;

 ind_vec_SoA *my_array_soa = new ind_vec_SoA;

 for(int i = 0; i<100; i++){ // This loop is fast now (hopefully)!
    my_array_soa.n[i] = 1; 
 }

Con questo approccio, è probabile che si ottenga la località di memoria simile alla matrice int in quanto l'array int n[NT] è probabile che venga allocato in modo contiguo. Se elabori i campi n , avrà delle buone caratteristiche di prestazione. Se, tuttavia, elaborate più campi in una struttura alla volta, le caratteristiche delle prestazioni saranno molto peggiori rispetto al progetto originale.

Vale anche la pena sottolineare che non è bello quanto l'incapsulamento (almeno non in C ++), ma è un paradigma abbastanza comune nei giochi e nelle applicazioni HPC. Nella misura in cui le lingue progettate per questi campi, ad es. jai e chapel gestiscono questa trasformazione più direttamente.

I campi "n" in my_array_1 non sono successivi in memoria e quindi sono mappati su diversi blocchi della cache di memoria.

Invece gli elementi my_array_2 condividono gli stessi blocchi di cache.

Risposta breve: località cache.
I processori utilizzano una piccola memoria veloce (cache denominata) per memorizzare i valori con cui lavorano. Se il valore non è nella cache, cercano RAM che è molto, molto lento. Di solito i processori cercano di prevedere i carichi di cache in anticipo per mitigare un po 'la perdita di tempo. Ad esempio, se si itera su semplice int a[1000000000] , sarà veloce perché è facile prevedere futuri errori di cache. Ma dal momento che ogni elemento in my_array_1 è effettivamente la dimensione della cache L1, è possibile che la cache potenziale manchi ogni iterazione del ciclo for. Per non parlare del fatto che la cache L2 di solito è di circa 256kb che è size_of(ind_vec)*8 . quindi, dopo le prime 8 iterazioni, hai una frequenza di perdita della cache del 100%.

Una soluzione rapida consiste nell'allocare dinamicamente gli array mobili in ind_vec:

typedef struct {
  float* ind_1 = new float[4096];
  float* ind_2 = new float[4096];
  int n;
} ind_v

In questo modo si programma solo carichi ~ 12 byte alla volta, che è molto più gestibile.

Bene, ovviamente il primo ciclo è più lento. Senza nemmeno approfondire gli errori di pagina e le pagine del sistema operativo in memoria all'accesso, il passo del ciclo è lungo 8200 byte (supponendo 32 bit di padding) per passare da un campo di dati n al successivo.

In genere la macchina recupera tutti i dati dei campi circostanti in ind_vec quando si caricano pagine (ad esempio 4k pagine) in righe di cache (ad esempio 64 byte) in un registro (ad esempio 64 bit), solo per accedere al campo n (ad esempio 4 byte) e quindi sprecare l'intero tempo di paging in 4 kilobyte di memoria e spostarsi verso il basso della gerarchia con 64 linee di cache di byte fino a un registro generale solo per elaborare 4 dei 64 byte di dati in la linea della cache e 4 dei 4 kilobyte di dati nella pagina. In pratica stai facendo perdere tempo alla macchina spostando la memoria non rilevante per il tuo loop (accedendo solo a 4/8200 byte del tuo ind_vec struct ogni iterazione) lungo la gerarchia. Questo cancellerà la località spaziale.

Nel frattempo con il secondo ciclo, si accede generalmente a tutti i dati caricati in una pagina e in una linea della cache prima dello sfratto. Il secondo ciclo attraversa una serie di interi molto densi in cui non si sta causando perdite di tempo per l'hardware e il sistema operativo che spostano la memoria verso il basso nella gerarchia solo per elaborare una minima frazione di esso prima dello sfratto.

Gerarchia di memoria

L'hardware ha una gerarchia di memoria che va dal più piccolo (registro) al più grande (disco seguito da DRAM) e allo stesso modo dal più veloce al più lento (il più piccolo è il più veloce, il più grande è il più lento).

Per evitare di accedere alla memoria grande ma lenta troppo spesso, le macchine caricano in memoria da regioni lente in blocchi contigui (es: 4 kilobyte per una pagina, 64 byte per una linea cache). Afferra la memoria dai tipi lenti di memoria a mano a mano, per così dire. Lo fa ogni volta che si richiede di fare qualsiasi cosa con uno specifico indirizzo di memoria se la memoria intorno all'indirizzo non è già cercata o già in una linea di cache. Per ottenere il massimo beneficio con questo processo, si desidera scrivere il codice in un modo tale che quando hardware e sistema operativo stanno acquisendo dati dalla memoria lenta in blocchi contigui di grandi dimensioni (a mano a mano) e spostandosi verso il basso nella gerarchia di memoria, non si è sprecare quel costoso processo semplicemente accedendo a pochi byte di quei blocchi prima di tentare di accedere a molta memoria altrove da un indirizzo distante totalmente diverso (che è ciò che fa il primo loop).

M & M Analogy

Ilcodicechehaioriginariamenteconilprimociclostafacendopassarel'hardwareattraversoicerchisolopersprecarelamaggiorpartedellosforzo.ÈcomeusareuncucchiaiogiganteperscavareinunaciotoladiM&MssoloperpoiscegliereemangiaresoloilM&MsverdeepoilanciareilrimanenteM&Maparte.ÈmoltoinefficienteinvecedimangiaretuttiicoloridiM&MsinunacucchiaiataallavoltaoavereunaciotolacheconsistesolodiM&Msverde,quellicheinrealtàsimangeranno,inmododapotermangiareintericucchiaidiM&verde;Mssubito.

NelfrattempoilsecondocicloècomemangiaredaunaciotoladisoloM&Msverde.Conquelsecondociclo,puoimangiareinterecucchiaiatediM&Msverdecontemporaneamentedatochestaiaccedendoatuttiidatinell'arrayenonsaltaretroppesezioniconunepicopassoda8kilobyte.

Scissionecampicaldi/freddi

Q2)Isthereanyworkaroundhere?

Larispostapiùdirettaalproblemaconcettualeneltuocasodiesempioèladivisionedelcampocaldo/freddo.Noncaricareunabarcadidatichenonsiaccedeapercorsicriticinellastessastrutturaoclassedeidatiacuisiaccedefrequentemente.Memorizzalosullatoinparallelo,inquestomodo:

structind_vec_cold{//Coldfieldsnotaccessedfrequently.floatind_1[4096];floatind_2[4096];};structind_vec_hot{//Hotfieldsaccessedfrequently.intn;};structind_vec{ind_vec(intn):hot(n),cold(n){}vector<ind_vec_hot>hot;vector<ind_vec_hot>cold;};ind_vecdata(NT);for(inti=0;i<100;i++){//Notslowanymore!data.hot[i].n=1;}

Usando l'analogia di M & M sopra, questo approccio di divisione del campo caldo / freddo raggiunge efficacemente l'effetto di avere una ciotola di solo M & Ms verde così che ora possiamo consumarli rapidamente con il cucchiaio. Usiamo una ciotola diversa per memorizzare gli altri colori M & M. Precedentemente hai avuto una mescolanza di M & Ms e stavi costringendo la macchina ad afferrare M & Ms dal cucchiaio solo per scegliere i pochi M & Ms verdi in quel cucchiaio e poi gettare il resto da parte.