← Volver a los ejercicios

Dos programas que hacen la misma cuenta

Dos versiones suman la misma matriz de 10.000 × 10.000 enteros y escriben el mismo resultado. Una tarda casi el doble que la otra. Prediga la diferencia y las instrucciones por ciclo antes de destapar los contadores, y decida qué la explica.

1. Lo único que cambia

Por filas (./bueno)
1for (int i = 0; i < n; i++)
2 for (int j = 0; j < n; j++)
3 suma += matriz[i][j];
Por columnas (./malo)
1for (int i = 0; i < n; i++)
2 for (int j = 0; j < n; j++)
3 suma += matriz[j][i];

Los dos imprimen 999900000000. La matriz se reserva igual, se llena igual y se recorre el mismo número de veces.

El de filas tarda 0,43538 s y el de columnas 0,79385 s. ¿Cuántas veces más tarda el de columnas?

2. Instrucciones por ciclo

El procesador ejecutó 3.504.983.954 instrucciones en 1.177.787.894 ciclos para el de filas, y 3.504.984.293 en 2.796.626.915 para el de columnas. El cociente dice cuánto trabajo sale de cada ciclo de reloj.

Por filas:

Por columnas:

3. Mismas instrucciones, el doble de ciclos

Las dos cuentas de instrucciones se diferencian en 339 de tres mil quinientos millones. Los ciclos, en cambio, se duplican. ¿Qué lo explica?

Una línea de caché trae 64 bytes, que son dieciséis enteros seguidos. Por filas, esos dieciséis se usan uno tras otro; por columnas se usa uno y el siguiente acceso cae 40.000 bytes más allá, en otra línea.

4. Por qué no basta con leer el código

Las dos versiones se diferencian en el orden de dos índices. Puestas una al lado de la otra, nada señala cuál cuesta el doble.

5. Qué herramienta responde «dónde»

Las herramientas de la sesión se reparten en cuatro familias.

FamiliaEn PythonEn C++ y LinuxCómo trabaja
Temporizadorestime, timeitchronomiden tiempo transcurrido
DeterministascProfilecallgrindinstrumentan y registran cada evento
Estadísticospyinstrumentperfmuestrean cada tantos milisegundos
Monitores del sistema—top, htop, psobservan el proceso desde afuera

Para saber en qué función y en qué línea se va el tiempo, ¿a cuál familia se acude?

El resto de la sesión recorre las cuatro familias sobre estos mismos dos programas: primero el proceso visto desde afuera, después la caché simulada con Valgrind y al final los contadores del procesador con perf.