2016-07-12 2 views
5

Quale dei 2 è più veloce (C++)?Confronto dell'accesso alla memoria

for(i=0; i<n; i++) 
{ 
    sum_a = sum_a + a[i]; 
    sum_b = sum_b + b[i]; 
} 

O

for(i=0; i<n; i++) 
{ 
    sum_a = sum_a + a[i]; 
} 
for(i=0; i<n; i++) 
{ 
    sum_b = sum_b + b[i]; 
} 

io sono un principiante in modo da non so se questo ha un senso, ma nella prima versione, serie 'a' si accede, quindi 'b', che potrebbe portare a molti switch di memoria, poiché gli array 'a' e 'b' si trovano in differenti posizioni di memoria. Ma nella seconda versione, si accede dapprima all'intero array 'a', quindi all'intero array 'b', che consente di accedere a posizioni di memoria continue anziché alternare i due array.

Questo fa alcuna differenza tra il tempo di esecuzione delle due versioni (anche molto trascurabile)?

+0

Puoi testarlo e scoprirlo. Semplice matematica ti dirà che hai il doppio del numero di iterazioni nel secondo esempio. – NathanOliver

+0

Ma lui ha un punto riguardo gli hit/miss della cache. – ABuckau

+1

Non penso che ci sia una risposta corretta a causa di diverse architetture – MaciekGrynda

risposta

4

Non penso che ci sia una risposta corretta a questa domanda. In generale, la seconda versione ha più iterazioni (il sovraccarico di esecuzione della CPU), ma un accesso peggiore alla memoria (sovraccarico di accesso alla memoria). Ora immagina di eseguire questo codice su PC che ha un clock lento, ma una cache follemente buona. L'overhead della memoria viene ridotto, ma poiché l'orologio è lento, lo stesso ciclo due volte rende l'esecuzione molto più lunga. In altre parole: orologio veloce, ma memoria scadente: l'esecuzione di due loop non è un problema, quindi è meglio ottimizzare per l'accesso alla memoria.

Ecco esempio fresco su come è possibile profilo la vostra applicazione: Link

3

Quale dei due è più veloce (C++)?

O. Dipende

  • L'attuazione di operator+ e operator[] (nel caso siano sovraccaricati)
  • Posizione delle matrici in memoria (adiacente o meno)
  • Dimensione delle matrici
  • Dimensione della CPU memorizza nella cache
  • Associativity di cache
  • velocità
  • cache in relazione alla velocità della memoria
  • Eventualmente altri fattori

Come Revolver_Ocelot menziona nella loro osservazione in a comment, alcuni compilatori possono persino trasformare il ciclo scritto nell'altro modulo.

Questo fa alcuna differenza tra il tempo di esecuzione delle due versioni (anche molto trascurabile)?

Può fare la differenza. La differenza può essere significativa o trascurabile.

L'analisi è valida. L'accesso alla memoria è in genere molto più lento della cache e saltare in due posizioni di memoria può causare il caching della cache in alcune situazioni. Ti consiglio di utilizzare l'approccio separato per impostazione predefinita e di combinare solo i loop se lo hai misurato per essere più veloce nella CPU di destinazione.

Come MSalters points out thrashing non dovrebbe essere un problema con i processori desktop moderni (moderni come in ~ x86).

+0

La cache con due array è impedita da una cache associativa a due vie (o migliore). È solo un problema con la cache mappata diretta. L'accesso a due posizioni di memoria fisicamente distinte allo stesso tempo può addirittura raddoppiare la larghezza di banda della memoria, a seconda dell'architettura di memoria. – MSalters

+0

@MSalters OK, non dovrebbe essere poi così male. Ma potresti ancora montare solo due array di dimensioni N/2, rispetto a un singolo array di dimensioni N nella cache, non è vero? Forse il mio ragionamento è spento. Lo ammetto, faccio la maggior parte della mia ottimizzazione a un livello più alto di questo. – user2079303

+0

@ user2079303 il pre-filtro della memoria ti dirà facilmente che stai accedendo alla memoria in questo modo lineare. Il pre-fetcher non è veloce come la cache, ma è molto più veloce dell'attesa dell'intero intervallo di tempo per l'accesso alla memoria. – SirGuy

Problemi correlati