¿Por qué es tan lenta la iteración sobre una gran lista de std ::?

Question

Como sugiere el título, tuve problemas con un programa mío en el que usé std :: list como una pila y también para recorrer en iteración todos los elementos de la lista. El programa llevaba demasiado tiempo cuando las listas se hicieron muy grandes.

¿Alguien tiene una buena explicación para esto? ¿Es un comportamiento de pila / caché?

(Resolvió el problema cambiando las listas a std :: vector y std :: deque (por cierto, una estructura de datos asombrosa) y de repente todo fue mucho más rápido)

EDITAR: No soy un tonto y no accedo a elementos en medio de las listas. Lo único que hice con las listas fue eliminar / agregar elementos al final / al principio e iterar a través de todos los elementos de la lista. Y siempre usé iteradores para iterar sobre la lista.

Answer 1

Las listas tienen una localidad de caché terrible (inexistente). Cada nodo es una nueva asignación de memoria, y puede estar en cualquier lugar . Entonces, cada , cada vez que sigue un puntero de un nodo al siguiente, salta a un lugar nuevo, no relacionado, en la memoria. Y sí, eso duele un poco el rendimiento. Una falla de caché puede ser dos órdenes de magnitudes más lenta que un golpe de caché. En un vector o deque, casi todos los accesos serán un hit de caché. Un vector es un solo bloque de memoria contiguo, por lo que iterar sobre eso es tan rápido como lo vas a obtener. Un deque es varios bloques de memoria más pequeños, por lo que presenta la falta ocasional de caché, pero aún así será raro, y la iteración seguirá siendo muy rápida, ya que en su mayoría se obtienen coincidencias de caché.

Una lista será casi todas las fallas de caché. Y el rendimiento apestará.

En la práctica, una lista enlazada casi nunca es la elección correcta desde el punto de vista del rendimiento.

Editar : Como señala un comentario, otro problema con las listas son las dependencias de datos. A una CPU moderna le gusta superponer operaciones. Pero no puede hacerlo si la siguiente instrucción depende del resultado de esta.

Si estás iterando sobre un vector, eso no es problema. Puede calcular la siguiente dirección para leer sobre la marcha, sin tener que consultar la memoria. Si está leyendo en la dirección x ahora, el siguiente elemento se ubicará en la dirección x + sizeof (T) donde T es el tipo de elemento. Por lo tanto, no hay dependencias allí, y la CPU puede comenzar a cargar el siguiente elemento, o el siguiente, inmediatamente, mientras se procesa un elemento anterior. De esa manera, los datos estarán listos para nosotros cuando los necesitemos, y esto ayuda a ocultar el costo de acceso a los datos en la RAM.

En una lista, debemos seguir un puntero desde el nodo i al nodo i + 1 , y hasta que i + 1 haya sido cargados, ni siquiera sabemos dónde buscar i + 2 . Tenemos una dependencia de datos, por lo que la CPU se ve obligada a leer los nodos de uno en uno, y no puede comenzar a leer los nodos futuros con anticipación, porque aún no sabe dónde están.

Si una lista no hubiera tenido todos los errores de caché, esto no habría sido un gran problema, pero dado que estamos obteniendo muchos errores de caché, estos retrasos son costosos.

Answer 2

Se debe a la gran cantidad de errores de caché que obtienes al utilizar una lista. Con un vector, los elementos circundantes se almacenan en el caché de los procesadores.

Answer 3

Eche un vistazo a la siguiente thread de flowoverflow .

Answer 4

Allí hay un problema de caché: todos los datos en vector se almacenan en una porción contigua, y cada elemento de la lista se asigna por separado y puede suceder que se almacene en un lugar bastante aleatorio de la memoria, lo que lleva A más fallos de caché. Sin embargo, apuesto a que te encuentras con uno de los problemas descritos en las otras respuestas.

Answer 5

La respuesta simple es porque iterar sobre un vector no es iterar en absoluto, simplemente comienza en la base de una matriz y lee los elementos uno tras otro.

Veo que esto está marcado como C ++, no C, pero dado que hacen lo mismo debajo de las cubiertas, vale la pena señalar que puedes agregar elementos al principio y al final de una matriz al asignarla de forma arbitrariamente grande, y realloc () ing y memmove () entre 2 matrices complementarias siempre y cuando se quede sin espacio. Muy rápido.

El truco para agregar elementos al comienzo de una matriz es sesgar el inicio lógico de la matriz al hacer avanzar el puntero hacia la matriz al inicio, y luego hacer una copia de seguridad al agregar elementos en la parte frontal. (también la forma en que se implementa una pila)

De la misma manera, se puede hacer que C sea compatible con subíndices negativos.

C ++ hace todo esto por ti con la clase vectorial STL, pero aún así vale la pena recordar lo que está pasando debajo de las cubiertas.

Answer 6

[Editar: Estoy corregido. std :: list no tiene operador []. Lo siento.]

Es difícil decirlo por su descripción, pero sospecho que intentaba acceder a los elementos de forma aleatoria (es decir, por índice):

for(int i = 0; i < mylist.size(); ++i) { ... mylist[i] ... }

En lugar de usar los iteradores:

for(list::iterator i = mylist.begin(); i != mylist.end(); ++i) { ... (*i) ... }

Ambos " vector " &erio; " deque " son buenos para el acceso aleatorio, por lo que cualquiera de ellos tendrá un rendimiento adecuado para esos tipos --- O (1) en ambos casos Pero " lista " no es bueno en el acceso aleatorio El acceso a la lista por índice tomaría O (n ^ 2) tiempo, en lugar de O (1) cuando se usan iteradores.