Scrittura lenta su matrice in C++

Question

Mi stavo chiedendo se questo comportamento è previsto in C++. Il seguente codice viene eseguito in circa 0.001 ms:

for(int l=0;l<100000;l++){ 
     int total=0; 
     for(int i = 0; i < num_elements; i++) 
     { 
      total+=i; 
     } 
    } 

Tuttavia, se i risultati sono scritti in un array, il tempo di esecuzione spara fino a 15 ms:

int *values=(int*)malloc(sizeof(int)*100000); 
     for(int l=0;l<100000;l++){ 
      int total=0; 
      for(unsigned int i = 0; i < num_elements; i++) 
      { 
       total+=i; 
      } 
      values[l]=total; 
     } 

posso apprezzare che per iscritto al l'array richiede tempo ma il tempo è proporzionato?

Saluti tutti

Answer 1

Il primo esempio può essere implementato utilizzando solo registri CPU. A questi si può accedere miliardi di volte al secondo. Il secondo esempio utilizza tanta memoria che sicuramente trabocca L1 ed eventualmente cache L2 (a seconda del modello di CPU). Sarà più lento. Eppure, 15 ms/100.000 scritture arriva a 1.5 ns per scrittura - 667 Mhz in modo efficace. Questo è non lento.

Answer 2

Sembra che il compilatore è l'ottimizzazione quel ciclo interamente nel primo caso.

L'effetto totale del ciclo è un no-op, quindi il compilatore lo rimuove.

Answer 3

Sospetto che ciò che state vedendo sia un effetto di virtual memory e probabilmente il paging. La chiamata malloc sta per allocare un blocco di memoria di dimensioni decenti che è probabilmente rappresentato da un numero di pagine virtuali. Ogni pagina è collegata separatamente alla memoria del processo.

È inoltre possibile misurare il costo della chiamata malloc in base alla durata del ciclo. In entrambi i casi, le prestazioni saranno molto sensibili alle opzioni di ottimizzazione del compilatore, alle opzioni di threading, alle versioni del compilatore, alle versioni di runtime e praticamente a qualsiasi altra cosa. Non è possibile presumere che il costo sia lineare con le dimensioni dell'allocazione. L'unica cosa che puoi fare è misurarla e capire come ottimizzare al meglio una volta che si è verificato un problema.

Answer 4

È molto semplice. Nel primo caso si hanno solo 3 variabili, che possono essere facilmente memorizzate in GPR (registri di uso generale), ma ciò non significa che sono sempre presenti, ma probabilmente si trovano nella memoria cache L1, il che significa che sono si può accedere molto velocemente.

Nel secondo caso sono presenti più di 100k variabili e sono necessari circa 400kB per memorizzarle. Questo è decisamente troppo per i registri e la memoria cache L1. Nel migliore dei casi potrebbe essere nella memoria cache L2, ma probabilmente non tutti saranno in L2. Se qualcosa non è registrato, L1, L2 (presumo che il tuo processore non abbia L3) significa che devi cercarlo nella RAM e ci vuole più tempo per muuuuuuch.