¿Por qué la ubicación del caché es importante para el rendimiento de la matriz?

En el siguiente blog hay una statement sobre la ventaja de las matrices sobre las listas enlazadas:

Las matrices tienen una mejor localidad de caché que puede hacer una gran diferencia en el rendimiento.

Qué significa eso? No entiendo cómo la localidad de caché puede proporcionar un gran beneficio de rendimiento.

Ver mi respuesta sobre localidad espacial y temporal .

En particular, las matrices son bloques de memoria contiguos, por lo que grandes trozos de ellos se cargarán en la memoria caché al primer acceso. Esto hace que sea relativamente rápido acceder a los elementos futuros de la matriz. Por otro lado, las listas vinculadas no se encuentran necesariamente en bloques contiguos de memoria, y podrían generar más errores de caché, lo que aumenta el tiempo que lleva acceder a ellos.

Considere los siguientes posibles diseños de memoria para una matriz de data y una lista vinculada l_data de estructuras grandes

 Address Contents | Address Contents ffff 0000 data[0] | ffff 1000 l_data ffff 0040 data[1] | .... ffff 0080 data[2] | ffff 3460 l_data->next ffff 00c0 data[3] | .... ffff 0100 data[4] | ffff 8dc0 l_data->next->next | ffff 8e00 l_data->next->next->next | .... | ffff 8f00 l_data->next->next->next->next 

Si quisiéramos recorrer este conjunto, el primer acceso a ffff 0000 requeriría que vayamos a la memoria para recuperar (una operación muy lenta en ciclos de CPU). Sin embargo, después del primer acceso, el rest de la matriz estaría en la memoria caché, y los accesos posteriores serían mucho más rápidos. Con la lista enlazada, el primer acceso a ffff 1000 también requeriría que vayamos a la memoria. Desafortunadamente, el procesador guardará en caché la memoria que rodea esta ubicación, por ejemplo, hasta ffff 2000 . Como puede ver, esto en realidad no captura ninguno de los otros elementos de la lista, lo que significa que cuando vayamos a acceder a l_data->next , nuevamente tendremos que ir a la memoria.

Normalmente, al usar una matriz, accede a elementos que están cerca uno del otro. Esto es especialmente cierto cuando se accede a una matriz de forma secuencial.

Cuando accede a la memoria, una parte de ella se almacena en caché en varios niveles. La localidad de caché se refiere a la probabilidad de que las operaciones sucesivas estén en la caché y, por lo tanto, sean más rápidas. En una matriz, maximiza las posibilidades de acceso secuencial a elementos en la caché.

Con las listas, por contraejemplo, no hay garantía de que los elementos que aparecen secuencialmente en la lista estén realmente dispuestos cerca unos de otros en la memoria. Esto significa menos éxitos de caché y rendimiento degradado.