Efficienza di accesso in lettura / scrittura della memoria

Question

Efficienza di accesso in lettura / scrittura della memoria

#1 da (2 voti)

1

Ho ascoltato informazioni contrastanti da fonti diverse e non sono sicuro di quale credere. Come tale, posterò ciò che capisco e chiedo correzioni. Diciamo che voglio usare una matrice 2D. Ci sono tre modi in cui posso farlo (almeno che io sappia).

1 :

int i;
char **matrix;
matrix = malloc(50 * sizeof(char *));
for(i = 0; i < 50; i++)
    matrix[i] = malloc(50);

2 :

int i;
int rowSize = 50;
int pointerSize = 50 * sizeof(char *);
int dataSize = 50 * 50;
char **matrix;
matrix = malloc(dataSize + pointerSize);
char *pData = matrix + pointerSize - rowSize;
for(i = 0; i < 50; i++) {
    pData += rowSize;
    matrix[i] = pData;
}

3 :

//instead of accessing matrix[i][j] here, we would access matrix[i * 50 + j]
char *matrix = malloc(50 * 50);

In termini di utilizzo della memoria, la mia comprensione è che 3 è il più efficiente, 2 è il prossimo, e 1 è il meno efficiente, per i motivi seguenti:

3 : c'è solo un puntatore e un'allocazione e, quindi, un sovraccarico minimo.

2 : Ancora una volta, c'è solo un'allocazione, ma ora ci sono 51 puntatori. Ciò significa che c'è 50 * sizeof(char *) di overhead in più.

1 : ci sono 51 allocazioni e 51 puntatori, che causano il maggior overhead di tutte le opzioni.

In termini di prestazioni, ancora una volta mi rendo conto che 3 è il più efficiente, 2 è il prossimo, e 1 è il meno efficiente . Motivi:

3 : è necessario un solo accesso alla memoria. Dovremo fare una moltiplicazione e un'aggiunta rispetto a due aggiunte (come nel caso di un puntatore a un puntatore), ma l'accesso alla memoria è abbastanza lento da non avere importanza.

2 : abbiamo bisogno di due accessi alla memoria; una volta per ottenere un char * , quindi l'appropriato char . Qui vengono eseguite solo due aggiunte (una volta per ottenere il puntatore char * corretto dalla posizione di memoria originale e una volta per ottenere la variabile char corretta da dove char * punta a), quindi la moltiplicazione (che è più lenta di aggiunta) non è richiesto. Tuttavia, su CPU moderne, la moltiplicazione è più veloce dell'accesso alla memoria, quindi questo punto è mootico.

1 : gli stessi problemi di 2 , ma ora la memoria non è contigua. Ciò causa errori di cache e ricerche extra di tabelle di pagina, rendendolo il meno efficiente del lotto.

Prima di tutto: è corretto? Secondo: c'è un'opzione 4 che mi manca che sarebbe ancora più efficiente?

c optimization

posta wolfPack88 13.06.2014 - 15:32

fonte

1 risposta

Leggi altre domande sui tag c optimization

Lingue e loro licenze? Perché DataContractJsonSerializer non include generici come JavaScriptSerializer?

score 2 · Accepted Answer

Suppongo che intendi l'ambiente HPC come indicato nel commento. Immagino tu intenda anche che la matrice sia grande. Come regole generali

Nella maggior parte dei casi è possibile preallocare i dati all'inizio comunque il costo del sovraccarico è minimo - perché preoccuparsi del tempo di ms quando il programma è in esecuzione per giorni / ore comunque continuando a scorrere su questo array?
Nella maggior parte dei casi viene allocata una grande quantità di dati - l'overhead di malloc per tali dati è minimo - perché preoccuparsi di alcuni kB di overhead quando si gestiscono GB di dati
Nella maggior parte dei casi i programmatori non funzionano correttamente. Quindi la regola è quella di fare il punto di riferimento il più possibile per ottenere i tempi reali e le spese generali (anche se ci sono alcuni documenti sulla modellazione dei sistemi HPC che potreste voler leggere - i modelli sono estremamente utili e possono essere relativamente semplici per problemi legati alla memoria)

Riguardo l'esempio specificato, dipende in gran parte da come accedi ai dati. In molti casi si desidera co-progettare la struttura dei dati per un algoritmo specifico e per una piattaforma specifica. Nella maggior parte dei casi si desidera sfruttare la gerarchia di memoria (dal più lento al più veloce: rete, disco, memoria principale, cache, registri) il più possibile, il che significa che si desidera utilizzare la località spaziale e temporale. Non entrare nei dettagli significa che vuoi:

Accedi ai dati vicini ai dati che hai già visitato (località spaziale)
Riutilizzare i dati già consultati (località temporale)

Dipende dal tuo algoritmo - potresti ad esempio utilizzare curva di riempimento dello spazio se esegui cellar automata o stencil operazioni simili (ad esempio curva Z ). I dettagli esatti dipendono dalla piattaforma (associatività della cache, rilevamento automatico dello streaming ecc.).

Lo sfruttamento corretto può avere una drammatica accelerazione solo quando ottimizzato in modo semplice. Per esempio la moltiplicazione della matrice semplicemente riordinare i loop può dare l'accelerazione di diversi ordini di grandezza (prova a riordinare i loop tu stesso, domanda bonus - se cambi una dimensione in modo da non allinearti con la linea della cache cosa succede?):

const size_t size = 4096;
double (*a)[size] = malloc(sizeof(double [size]));
double (*b)[size] = malloc(sizeof(double [size]));
double (*c)[size] = malloc(sizeof(double [size]));
for (int i = 0; i < size; i++) {
    for (int j = 0; j < size; j++) {
        c[i][j] = 0;
        for (int k = 0; k < size; k++) {
            c[i][j] += a[i][k] * b[k][j];
        }
    }
}

Quindi puoi impiegare ulteriormente tecniche come tiling del loop ecc. Si noti inoltre che quando si parallelizza il codice necessario per evitare cose come false condivisioni vale a dire che due thread che accedono ai dati sulla stessa linea della cache causeranno il loro invio avanti e indietro tra processori, che è lento (per l'architettura Core i3 / i5 / i7, almeno i più recenti, declassa l'accesso alla memoria alla velocità della cache L3 IIRC).

Per una struttura più complessa allora raddoppia anche tu devi considerare la struttura AOS vs SOA. Il primo è un array di strutture C / C ++ 'normale' ed è utile se si può sfruttare la localizzazione della cache: quando si accede al primo elemento, è probabile che anche il resto si trovi nella cache. Il secondo mantiene ogni campo della struttura in un array separato - mentre ha un costo di localizzazione della cache peggiore migliora la vettorizzazione / SPMD mentre il caricamento del singolo campo avviene in un singolo passaggio e migliora lo streaming.

La buona notizia è che in alcuni casi, come le operazioni lineari, esistono librerie / API ben note, come BLAS.

La linea di fondo è che probabilmente la variante dell'opzione 3 è il modo migliore. A seconda delle operazioni, è possibile caricare i dati sulla linea della cache completa o ordinare i dati in modo intelligente. Tuttavia probabilmente potresti voler usare semplicemente la libreria BLAS dal tuo fornitore HPC se tutto ciò che fai sono le operazioni lineari.

L'operazione di tipo 2 dell'opzione è probabilmente utilizzata principalmente quando si dispone di accesso non strutturato.