std :: list vs std :: vector iteration

Question

Se dice que iterar a través de un vector (como al leer todo su elemento) es más rápido que iterar a través de una lista, debido a la memoria caché optimizada.

¿Hay algún recurso en la web que pueda cuantificar cuánto afecta el rendimiento?

Además, ¿sería mejor utilizar una lista vinculada personalizada, a quién se asignarían elementos para que sean consecutivos en la memoria?

La idea detrás de eso es que quiero almacenar elementos en un orden determinado que no cambiará. Todavía necesito poder insertar algunos en tiempo de ejecución en el medio rápidamente, pero la mayoría de ellos seguirán siendo consecutivos, porque el orden no cambiará.

El hecho de que los elementos sean consecutivos tiene un impacto en la memoria caché, o porque todavía llamaré al list_element->next en lugar de a ++list_element, no mejora nada?

Answer 1

Las ganancias de eficiencia de la coherencia del caché debido a la representación compacta de las estructuras de datos pueden ser bastante dramáticas.En el caso de vectores comparados con listas, la representación compacta puede ser mejor no solo para leer, sino incluso para insertar (desplazar en vectores) elementos hasta el orden de los elementos 500K para alguna arquitectura particular como se demuestra en la Figura 3 de este artículo por Bjarne BS: (sitio Editorial: http://www.computer.org/portal/web/csdl/doi/10.1109/MC.2011.353)

http://www2.research.att.com/~bs/Computer-Jan12.pdf

Creo que si esto es un factor crítico para su programa, debe perfila en su arquitectura.

Answer 2

No estoy seguro si puedo explicarlo bien, pero aquí está mi punto de vista (estoy pensando en la línea de instrucción de máquina traducida a continuación :),

iterador vectorial (memoria contigua): Cuando incrementa un iterador de vectores , el valor del iterador simplemente se agrega al tamaño del objeto (conocido en tiempo de compilación) para apuntar al siguiente objeto. En la mayoría de las CPU esto es cualquier cosa de una a tres instrucciones como máximo.

iterador de la lista (lista enlazada http://www.sgi.com/tech/stl/List.html): Cuando incrementa un iterador de lista (el objeto puntiagudo), la ubicación del enlace directo se encuentra mediante la adición de un número a la base del objeto apuntado y luego cargado como el nuevo valor del iterador. Hay más de un acceso de memoria para esto y es más lento que la operación de iteración vectorial.

Answer 3

La principal diferencia entre el vector y las listas es que los elementos vectoriales se construyen posteriormente dentro de un búfer preasignado, mientras que en una lista los elementos se construyen uno por uno. Como consecuencia, se concede que los elementos en un vector ocupen un espacio de memoria contiguo, mientras que los elementos de lista (a menos que algunas situaciones específicas, como un asignador personalizado funcione de esa manera) no se concedan, y pueden ser "escasos" alrededor la memoria.

Ahora, dado que el procesador opera en un caché (que puede ser hasta 1000 veces más rápido que la RAM principal) reasigna páginas completas de la memoria principal, si los elementos son consecutivos es muy probable que quepan en la misma memoria página y, por lo tanto, se mueven todos juntos en la memoria caché cuando comienza la iteración. Mientras continúa, todo sucede en la memoria caché sin necesidad de mover datos o acceder a la memoria RAM más lenta.

Con list-s, dado que los elementos son escasos en todas partes, "ir a la siguiente" significa hacer referencia a una dirección que puede no estar en la misma página de memoria de la anterior y, por lo tanto, debe actualizarse cada vez paso de iteración, accediendo a la RAM más lenta en cada iteración.

La diferencia de rendimiento depende en gran medida del procesador y del tipo de memoria utilizada tanto para la RAM principal y la memoria caché, y en el camino de la std::allocator (y en última instancia operator new y malloc) se implementa, por lo que un número general es imposible que debe darse. (Nota: gran diferencia significa mala RAM respecto al caché, pero también puede significar una mala implementación en list-s)