es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

¿Por qué el segundo programa tiene un peor rendimiento, aunque debería tener considerablemente menos misses en cache?

Considere los siguientes programas:


#include <stdio.h> #include <stdlib.h> typedef unsigned long long u64; int program_1(u64* a, u64* b) { const u64 lim = 50l * 1000l * 1000l; // Lee los arreglos u64 sum = 0; for (u64 i = 0; i < lim * 100; ++i) { sum += a[i % lim]; sum += b[i % lim]; } printf("%llu\n", sum); return 0; } int program_2(u64* a, u64* b) { const u64 lim = 50l * 1000l * 1000l; // Lee los arreglos u64 sum = 0; for (u64 i = 0; i < lim * 100; ++i) { sum += a[i % lim]; } for (u64 i = 0; i < lim * 100; ++i) { sum += b[i % lim]; } printf("%llu\n", sum); return 0; }

Ambos programas son idénticos: llenan un array con 1, luego leen cada elemento 100 veces, agregándolo a un contador. La única diferencia es que el primero fusiona el bucle sumador, mientras que el segundo realiza dos pasadas separadas. Dado que M1 tiene una caché de datos L1 de 64KB, entiendo que lo siguiente sucedería:

Programa 1

sum += a[0] // MISS DE CACHÉ. Carga a[0..8192] en L1.
sum += b[0] // MISS DE CACHÉ. Carga b[0..8192] en L1.
sum += a[1] // MISS DE CACHÉ. Carga a[0..8192] en L1.
sum += b[1] // MISS DE CACHÉ. Carga b[0..8192] en L1.
sum += a[2] // MISS DE CACHÉ. Carga a[0..8192] en L1.
sum += b[2] // MISS DE CACHÉ. Carga b[0..8192] en L1.
(...)

Programa 2

sum += a[0] // MISS DE CACHÉ. Carga a[0..8192] en L1.
sum += a[1] // HIT DE CACHÉ.
sum += a[2] // HIT DE CACHÉ.
sum += a[3] // HIT DE CACHÉ.
sum += a[4] // HIT DE CACHÉ!
...
sum += a[8192] // MISS DE CACHÉ. Carga a[8192..16384] en L1.
sum += a[8193] // HIT DE CACHÉ!
sum += a[8194] // HIT DE CACHÉ!
sum += a[8195] // HIT DE CACHÉ!
sum += a[8196] // HIT DE CACHÉ!
...
...
sum += b[0] // MISS DE CACHÉ. Carga b[0..8192] en L1.
sum += b[1] // HIT DE CACHÉ!
sum += b[2] // HIT DE CACHÉ!
sum += b[3] // HIT DE CACHÉ!
sum += b[4] // HIT DE CACHÉ!
...

Esto me llevaría a creer que el primer programa es más lento, ya que cada lectura es un fallo de caché, mientras que el segundo consiste principalmente en aciertos de caché. Sin embargo, los resultados difieren. En un Macbook Pro M1, con clang -O2, el primer programa tarda aproximadamente 2,8 segundos en completarse, mientras que el segundo tarda unos 3,8 segundos.

¿Qué está mal en mi modelo mental de cómo funciona la caché L1?</stdlib.h></stdio.h>

Tags:  , , ,

Answer

  1. Avatar for davy.ai

    Es importante destacar que el comportamiento de la caché puede ser complicado y depender de muchos factores, incluyendo el tamaño de la caché, la asociatividad y las políticas de reemplazo, así como las características específicas del programa que se está ejecutando.

    En este caso, la suposición de que cada lectura en el programa 1 es un fallo en la caché puede no ser precisa. Si bien es cierto que el bucle fusiona los accesos a a y b, algunos de estos accesos aún pueden beneficiarse de la localidad de la caché y permanecer en la caché entre iteraciones. Por otro lado, el programa 2 tiene dos bucles separados, cada uno con su propia sobrecarga para cargar datos en la caché, lo que puede estar contribuyendo a una menor velocidad de ejecución.

    Además, los detalles específicos de la organización de la caché del M1 pueden diferir de otros procesadores, y pueden verse afectados por varios factores que son difíciles de predecir sin un conocimiento extenso de la microarquitectura. Por lo tanto, es importante confiar en la perfilación y el análisis de referencia para determinar las características de rendimiento reales de un programa, en lugar de depender únicamente de modelos mentales del comportamiento de la caché.

Comments are closed.