Gestión de memoria (VI)

La importancia de la localidad

La mayoría de nuestros algoritmos y aplicaciones satisfacen una o ambas de las siguientes propiedades [1]:

• Localidad espacial: Una vez se referencia una determinada dirección en memoria, es altamente probable que en breve se referencie una dirección contigua o próxima a ella.

• Localidad temporal: Una vez se referencia una determinada dirección en memoria, es altamente probable que ésta sea referenciada nuevamente en un futuro próximo.

En base a ello, una computadora puede hacer uso de una jerarquía de memorias caché con el fin de reducir el tiempo de acceso a los datos residentes en memoria y/o para almacenar instrucciones de uso frecuente. 

Con carácter general, la caché de nivel k almacena copias de datos y/o instrucciones contenidas en el nivel inmediatamente inferior k + 1. La caché de nivel superior k es de extensión más reducida, pero de acceso más rápido, que el nivel inferior k + 1, con el fin de resolver la solicitud de datos por parte de la CPU con mayor celeridad. A modo de ejemplo, la latencia de la memoria caché L1 es típicamente de un ciclo, mientras que la del nivel L2 es de diez ciclos. Comparemos estos valores con los propios de la memoria principal, del orden de cien ciclos [2].

El coste económico de la memoria caché suele aumentar conforme ascendemos en la jerarquía de memoria. Así, los niveles de caché L1 y L2 suelen implementarse como memorias estáticas de acceso aleatorio (SRAM), que requieren seis transistores por cada celdilla (bit) de memoria, en contraste con el único transistor por bit requerido por la memoria dinámica principal (DRAM).

La memoria contenida en el nivel inferior k + 1 se lee y se copia en el nivel inmediatamente superior k en bloques de tamaño fijo (típicamente, 64 bytes en los niveles L1 y L2). Así, cuando la CPU requiera el uso de un objeto localizado en el nivel inferior k + 1, éste se busca primeramente en el nivel superior k. De hallarse en éste, la solicitud puede resolverse directamente y de forma más rápida desde el nivel k (se dice entonces que se ha producido un cache hit). En caso contrario (cache miss), el bloque que contenga al objeto en el nivel k + 1 deberá copiarse enteramente en el nivel k.

Obviamente, cuanto mayor sea la localidad de nuestra aplicación, más eficiente será ésta, al reducirse el número de copias de bloques que debamos realizar desde un nivel al inmediatamente superior. Es a este respecto por lo que en el lenguaje C++ se recomienda utilizar la plantilla de clase estándar std::vector<> como contenedor secuencial por defecto, al almacenar sus elementos en direcciones contiguas de memoria y resultar, por ello, cache-friendly [3]. En la imagen inferior, se indica el esquema típico de distribución de datos en memoria según se emplee un vector (izquierda) o una lista (derecha). Observemos cómo el vector resulta especialmente conveniente dado el modo de funcionamiento de la memoria caché. Por contra, los datos en una lista pueden sufrir una dispersión tal en memoria que una simple iteración a su través provoque múltiples cache misses.

---

Referencias bibliográficas:

1. Bryant R. E. and O'Hallaron D. R., Computer Systems: A Programmer's Perspective. Second edition. Addison-Wesley, 2010.
2. Meyers S. - code::dive Conference 2014 - CPU caches and why you care - https://youtu.be/WDIkqP4JbkE (el minito 19:00 es particularmente esclarecedor).
3. Stroustrup B. - Are lists evil? - https://isocpp.org/blog/2014/06/stroustrup-lists