Jugando con la caché

Ya todos estamos más que familiarizados con el concepto de localidad de las referencias. Y se me ocurrió tomarme unos minutos para analizar qué tanto impacto puede llegar a tener en un programa de computadora.

El ambiente de investigación "ideal" sería reiniciar en Linux en modo usuario simple, desconectando el mouse y otros periféricos que no sean necesarios para reducir la interferencia de interrupciones.

En mi caso no es así. Estoy haciendo un trabajo para la facu en OpenOffice, escuchando Dire Straits en VLC y con el firefox abierto en mi GMail. Da igual!

La idea es analizar qué ocurre si siempre estoy intentando modificar una posición de memoria que no está en la caché del procesador. Para eso se usa una gran matriz que se recorre por filas o por columnas asignandole un valor a los elementos de ésta.

Entonces decidí escribir un simple programa en C que acepta por dos valores por parametro: el tamaño de una matriz y un boolean para ver si la matriz se recorre por filas o por columnas. El codigo es el siguiente:

int msize, mdir;
int *mptr;

void initm() {
    int x, y, tam = msize * msize;

    if (mdir) {
        for (x = 0; x < tam; ++x) {
            mptr[x] = x;
        }
    } else {
        for (x = 0; x < msize; ++x) {
            for (y = 0; y < tam; y += msize) {
                mptr[x+y] = x;
            }
        }
    }
}

Fue compilado con gcc de la siguiente forma:

$ gcc -Wall -O2 -o cache.out cache.c

Y los resultados son más que alentadores:

$ time ./cache.out 15000 1

real 0m0.937s
user 0m0.184s
sys 0m0.728s

$ time ./cache.out 15000 0

real 0m7.063s
user 0m6.180s
sys 0m0.856s

Recorriendo la matriz por columas el programa es siete veces más lento que recorriendo por filas la misma matriz.

Como siempre, todos mis programas los ejecuto al menos una vez bajo valgrind. Los resultados son también muy interesantes!!

$ time valgrind -q ./cache.out 15000 1

real 0m22.026s
user 0m21.009s
sys 0m0.872s

$ time valgrind -q ./cache.out 15000 0

real 1m0.161s
user 0m58.972s
sys 0m0.880s

Así acaba mi experimento poco científico del día.