En la siguiente blog no es una declaración acerca de la ventaja de las matrices sobre listas enlazadas:¿Por qué la ubicación del caché es importante para el rendimiento de la matriz?
matrices tienen una mejor localidad caché que puede hacer una diferencia bastante grande en el rendimiento.
¿Qué significa eso? No entiendo cómo la localidad de caché puede proporcionar un gran beneficio de rendimiento.
Ver mi respuesta about spatial and temporal locality.
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 diseños de memoria posibles para una serie data y lista enlazada l_data de grandes estructuras
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 colocar a través de esta matriz, el primer acceso a ffff 0000 esa manera, requerirían para ir a la memoria de recuperar (una operación muy lenta en ciclos de CPU). Sin embargo, después del primer acceso, el resto 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 al 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 no captura realmente ninguno de los otros elementos de la lista, lo que significa que cuando accedamos al l_data->next, nuevamente tendremos que ir a la memoria.
Tenga en cuenta que la localidad de las listas vinculadas se puede mejorar mediante el uso de un grupo de memoria. Pero todavía tienes el problema de que los punteros 'siguientes' ocupan más espacio. – paddy
@paddy hace un buen punto porque con frecuencia es así como se implementan las listas vinculadas – brc
Ahora obtengo lo que significa "falta de caché en la lista vinculada". – AKS
Normalmente, al utilizar una matriz, accede a los elementos que están cerca unos de otros. Esto es especialmente cierto cuando se accede a una matriz de forma secuencial.
Al acceder a la memoria, se almacenan en caché varios fragmentos en varios niveles. La localidad de memoria se refiere a la probabilidad de que las operaciones sucesivas estén en la memoria 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.
Sin embargo, esto depende en gran medida del procesador y de la arquitectura de la memoria. Las CPU que están diseñadas para la programación orientada a objetos, por ejemplo, generalmente no se preocupan por la localidad, simplemente porque por la * definición * de "orientado a objetos" no se puede garantizar la ubicación de todos modos. –
Si comprende cómo funciona [cache] (http://en.wikipedia.org/wiki/Locality_of_reference), también comprenderá 1) "Localidad de referencia" es una buena cosa, y 2) acceder a los datos de las matrices suele ser más probable que tenga una buena "localidad" que acceder a los mismos datos de una lista. – paulsm4
Una cosa que vale la pena señalar es que, si bien esto es cierto, una lista vinculada individualmente combinada con un asignador contiguo puede ser un activo enorme, principalmente porque la transferencia de elementos de un contenedor a otro solo implica la lógica del puntero. Sin embargo, si nos fijamos en el diseño de la memoria de estos, es contigua y se ve como una matriz con solo enlaces al siguiente elemento de la matriz, por lo que sigue siendo compatible con la memoria caché (al menos hasta que la lista se reorganice por completo). –