Escritura lenta en una matriz en C++

Question

Me preguntaba si este es el comportamiento esperado en C++. El código siguiente funciona a alrededor de 0,001 ms:

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

Sin embargo, si los resultados se escriben en una matriz, el tiempo de ejecución se dispara 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; 
     } 

puedo apreciar que la escritura a la la matriz lleva tiempo pero ¿es proporcional el tiempo?

todos aplauden

Answer 1

El primer ejemplo se puede implementar utilizando solo registros de la CPU. Se puede acceder a esos miles de millones de veces por segundo. El segundo ejemplo usa tanta memoria que ciertamente desborda L1 y posiblemente L2 caché (dependiendo del modelo de CPU). Eso será más lento. Aún así, 15 ms/100.000 escrituras salen a 1.5 ns por escritura - 667 Mhz efectivamente. Eso es no lento.

Answer 2

Parece que el compilador es la optimización de ese bucle a cabo en su totalidad en el primer caso.

El efecto total del ciclo no es operativo, por lo que el compilador simplemente lo elimina.

Answer 3

Sospecho que lo que está viendo es un efecto de virtual memory y posiblemente de paginación. La llamada malloc va a asignar un trozo de memoria de tamaño decente que probablemente esté representado por un número de páginas virtuales. Cada página está vinculada a la memoria de proceso por separado.

También puede estar midiendo el costo de llamar al malloc dependiendo de cómo haya sincronizado el ciclo. En cualquier caso, el rendimiento va a ser muy sensible a las opciones de optimización del compilador, las opciones de subprocesamiento, las versiones de compilación, las versiones de tiempo de ejecución y casi cualquier otra cosa. No puede suponer con seguridad que el costo es lineal con el tamaño de la asignación. Lo único que puede hacer es medirlo y averiguar cómo optimizar mejor una vez que se ha demostrado que es un problema.

Answer 4

Es muy simple. En el primer caso Tiene solo 3 variables, que pueden almacenarse fácilmente en GPR (registros de propósito general), pero eso no significa que estén ahí todo el tiempo, pero probablemente estén en la memoria caché L1, lo que significa que se puede acceder muy rápido.

En el segundo caso Tiene más de 100k variables, y necesita aproximadamente 400kB para almacenarlas. Eso es sin duda demasiado para los registros y la memoria caché L1. En el mejor de los casos, podría estar en la memoria caché L2, pero probablemente no todos estarán en L2. Si algo no está registrado, L1, L2 (supongo que su procesador no tiene L3) significa que necesita buscarlo en la memoria RAM y le lleva mucho más tiempo.