Dos programas suman la misma matriz de 10.000 × 10.000 enteros, unos
394 MB, y los dos imprimen 999.900.000.000. ./bueno la recorre con
matriz[i][j] y ./malo con matriz[j][i]: esas son las
únicas dos líneas que cambian. Prediga lo que van a decir los contadores antes de
destaparlos.
1. Dieciséis enteros por línea
El ciclo interno de cada versión, con todo lo demás idéntico:
buenosuma += matriz[i][j];
malosuma += matriz[j][i];
La línea de caché de esta máquina trae 64 bytes y un int ocupa 4.
¿Cuántos enteros caben en una línea?
Entonces, recorriendo por filas, ¿cuántas lecturas de ./bueno aciertan por cada fallo?
Los dos binarios se midieron con
valgrind --tool=callgrind --cache-sim=yes ./bueno y lo mismo con
./malo. La columna de ./bueno está completa; prediga la otra
antes de destaparla.
Contador
./bueno
./malo
Las instrucciones y los accesos a datos
coinciden hasta los últimos dígitos: el mismo trabajo, la misma cantidad de sumas. Lo
que se dispara es el fallo de lectura, y con él el tiempo. Los fallos de instrucciones
quedan en 2.044 en los dos binarios, prueba de que el código no es el problema.
2. Cuántas veces peor
Compare los dos contadores de fallos de
lectura de la tabla: 112.622.262 en ./malo contra 6.366.206 en
./bueno.
¿Cuántas veces más fallos de lectura tiene ./malo?
La L3 de esta máquina tiene 32 MB y el
arreglo son 400.000.000 bytes: doce veces y media la caché completa, así que una línea
traída para un elemento ya fue desalojada cuando el recorrido por columnas vuelve a esa
fila. De los 118.909.812 fallos de L1 de ./malo, 104.365.640 bajan hasta
memoria.
3. Los fallos de escritura coinciden
D1mw da 6.287.550 en los dos binarios, el
mismo número hasta el último dígito. ¿Por qué?
4. Una tasa de 6,3 % suena baja
El resumen de ./malo cierra con
un D1 miss rate de 6,3 %. Alguien concluye que la caché está trabajando
bien. ¿Qué le falta a esa lectura?
5. Qué función es la culpable
callgrind_annotate reparte los contadores de
./malo entre las funciones del programa. La última columna es la parte que
cada una se lleva de los 112.622.262 fallos de lectura:
Función
Instrucciones
Fallos de lectura
Parte de los fallos
¿Qué se hace con esa tabla?
6. Diez veces más lento
Bajo Valgrind el programa corre hasta diez
veces más lento, y la herramienta no lee los contadores del procesador: simula una caché
de dos niveles. ¿Para qué sirve entonces?
La simulación da el mismo número en cada corrida porque no depende de
la carga de la máquina. Ese es el intercambio: se pierde el tiempo real y se gana una
cuenta de accesos y fallos que se puede comparar entre dos versiones del programa.