C++ / memoria cache

Bienvenidos sean a este post, hoy veremos uno de los tipos de memoria.

La idea de «cachear» informacion es muy comun en informatica. Tomemos como ejemplo un navegador web, las imagenes de una pagina se cachean, en este caso se almacenan en el disco rigido, para evitar que se vuelvan a solicitar al servidor en caso de que se vuelva a visitar la pagina. Esto mejora mucho la performance de la carga de la pagina. Esto mismo aplica a los programas cuando informacion que se reutiliza continuamente, en lugar de obtener la de origen se vuelve a usar la almacenada. E inclusive esto se puede aplicar a una simple funcion. Veamos el siguiente ejemplo:

long factoreo(long n) {
  if (n <= 1) { return 1; }
  return n * factoreo(n - 1);
}

Esta es una funcion simple de factoreo donde si el valor ingresado es menor o igual a uno devuelve ese valor. De lo contrario devuelve el resultado de la recursion de la funcion. Nada distinto a que no hayamos visto en otros posts. Tomemos como ejemplo los siguientes llamados:

factoreo(6);
factoreo(5);

La primera devuelve el factoreo del valor de 5, luego el de 4, y asi sucesivamente. En el siguiente llamado pasa lo mismo pero lo hace desde el numero 4. Pero como podemos mejorar esto? Cambiemos el codigo anterior de la siguiente manera:

std::unordered_map<long, long> cache;

long factoreo(long n) {
  if (n <= 1) return 1;
  if (cache.contains(n)) return cache[n];
  cache[n] = n * factoreo(n - 1);
  return cache[n];
}

El primer cambio que haremos sera declarar una nueva variable llamada cache de tipo map. Este almacena valores a una clave y para recuperarlos usamos esa clave. La clave sera el valor que pasamos como argumento a la funcion y el valor de la operacion lo asociaremos a este. El primer cambio interesante, es el agregado de un condicional. Este evalua si cache contiene la clave del valor pasado. En caso de ser verdadero, devolvemos el valor asocciado. Ahora en lugar de devolver el resultado del factoreo, lo almacenamos en una clave de cache. Para luego devolver la posicion actual del cache, haciendo la recursion anterior. Hagamos los siguientes llamados:

factoreo(5);
factoreo(6);

Esto hara todo el factoreo de cinco y lo almacenara en el cache. El siguiente factoreo calculara el primero pero los siguientes factoreos al existir en el cache procedera a usarlos en lugar de calcularlos, mejorando notablemente la performance. Este mismo concepto existe en el CPU, con un dispositivo llamado cache. Haciendo exactamente lo mismo, almacena los datos accedidos recientemente para que el acceso posterior sea mas rapido. Vamos a suponer otro ejemplo practico, en este caso tenemos un vector con 1000 valores. Y con el siguiente codigo podemos mostrarlos:

for (auto it: vec) {
  std::cout << it;
}

Para mostrar cada valor, el CPU primero lo copia de la memoria al registro rax, para luego llamar al operador << y mostrarlo en pantalla. En cada iteracion del bucle, el CPU copia el siguiente elemento del vector al registro rax y llama a la funcion para mostrar el valor. Por cada operacion de copia, el CPU debe ubicar la direccion del elemento en el bus de direcciones y establecer el bus de control a un modo lectura. El controlador de la DRAM accede a la informacion mediante la direccion recibida por el bus de direcciones y lo copia al bus de datos, y enviando la informacion al CPU. Y con esto, el CPU direcciona el valor al registro rax y luego ejecutar lo necesario para mostrar el valor. Pero esto se puede optimizar, y para ello el CPU copia el vector completo dentro del cache y accede a los elementos del vector desde este. Omitiendo todo lo que describimos anteriormente desde la DRAM.

El cache que posee el CPU usualmente se lo denomina como cache level 1 (L1). Como se daran cuenta este reside en el CPU y es de un tamaño muy chico. Pero otros dispositivos tambien poseen memoria cache. Cuando son externas al CPU se las denomina como cache level 2 (L2). En el caso de la memoria DRAM tambien posee una, pero esta se diferencia por su estructura fisica y patrones de acceso de datos. Esta se denomina como SRAM (Ram Estatica por sus siglas en ingles) la cual es mas rapida que la DRAM pero tambien mas cara. Existen mas niveles de cache y estos serviran a sus niveles inferiores. Tomemos el caso de L2 sera el cache para L1. Por lo tanto, si el CPU tiene una perdida de cache en L1, pasa a solicitarla a L2 y asi sucesivamente.

En resumen, hoy hemos visto a la memoria cache, que es, para que se penso, cual es su funcion principal, asi como algunas particularidades de ella. Espero les haya resultado de utilidad sigueme en tumblr, Twitter o Facebook para recibir una notificacion cada vez que subo un nuevo post en este blog, nos vemos en el proximo post.