Warum ist es so langsam Iterieren über eine große std :: list?

Question

Als Titel schon sagt, hatte ich Probleme mit einem Programm von mir wo ich eine std :: Liste als Stapel und auch alle Elemente der Liste iterieren. Das Programm wurde viel zu lange dauern würde, wenn die Listen sehr groß geworden.

Hat jemand eine gute Erklärung dafür? Ist es ein Stapel / Cache-Verhalten?

(Gelöst ist das Problem, das durch die Listen zu ändern std :: vector und std :: deque (eine erstaunliche Datenstruktur von der Art und Weise) und alles ging plötzlich so viel schneller)

EDIT: Ich bin kein Narr und ich auf keine Elemente in der Mitte der Listen. Das einzige, was ich mit den Listen tat, war, Elemente am Ende / Anfang zu entfernen / hinzufügen und durch alle Elemente der Liste iterieren. Und ich immer Iteratoren verwendet, um die Liste zu iterieren.

Answer 1

Listen haben schrecklich (nicht vorhandene) Cache-Lokalität. Jeder Knoten ist eine neue Speicherzuweisung, und sein kann überall . So alle Mal, wenn Sie einen Zeiger von einem Knoten zum nächsten folgen, springen Sie zu einem neuen, nicht verwandten, im Speicher. Und ja, das tut weh Leistung ziemlich viel. Ein Cache-Miss kann zwei Größenordnungen langsamer als ein Cache-Hit. In einem Vektor oder deque, so ziemlich jeder Zugriff wird ein Cache-Hit. Ein Vektor ist ein einziger zusammenhängender Speicherblock, so dass über Iterieren ist so schnell wie Sie bekommen werden. Ein deque ist mehrere kleinere Speicherblöcke, so stellt es die gelegentliche Cache-Miss, aber sie werden immer noch selten, und Iteration wird immer noch sehr schnell sein, wie Sie sind meist Cache-Hits zu bekommen.

Es wird eine Liste fast alle Cache-Misses sein. Und Leistung wird saugen.

In der Praxis wird eine verkettete Liste ist so gut wie nie die richtige Wahl von einer Performance-Sicht.

Bearbeiten : Als Kommentar darauf hingewiesen, ist ein weiteres Problem mit Listen Datenabhängigkeiten. Eine moderne CPU mag Operationen zu überlappen. Aber es kann nicht tun, wenn der nächste Befehl hängt vom Ergebnis dieses.

Wenn Sie über einen Vektor sind laufen, ist das kein Problem. Sie können die nächste Adresse berechnen on the fly zu lesen, ohne jemals im Speicher zu überprüfen zu haben. Wenn Sie an der Adresse x gerade lesen, dann das nächste Element wird an der Adresse x + sizeof(T) angeordnet sein, wo T der Elementtyp ist. So gibt es keine Abhängigkeiten gibt, und die CPU kann das nächste Element starten Laden oder den nach ihm, sofort, während immer noch ein früheres Element verarbeitet. Auf diese Weise werden die Daten für uns bereit sein, wenn wir es brauchen, und dies hilft, die Kosten weiter zu dem Maske Daten im RAM zugreifen.

In einer Liste, wir brauchen einen Zeiger vom Knoten i folgen i+1 den Knoten und bis i+1 geladen ist, wir wissen nicht einmal, wo für i+2 zu suchen. Wir haben eine Datenabhängigkeit, so dass die CPU gezwungen wird, Knoten einer nach dem anderen zu lesen, und es kann nicht gestartet werden zukünftige Knoten vor der Zeit zu lesen, weil sie noch nicht wissen, wo sie sind.

Wenn eine Liste nicht alles Cache-Misses gewesen wäre, wäre dies kein großes Problem gewesen, aber da wir eine Menge von Cache-Misses bekommen, sind diese Verzögerungen teuer.

Answer 2

Es ist aufgrund der großen Mengen von Cache-Misses erhalten Sie, wenn Sie eine Liste mit. Mit einem Vektor werden die umgebenden Elemente in den Prozessoren Cache gespeichert.

Answer 3

Haben Sie einen Blick auf die folgenden Stackoverflow Thread .

Answer 4

Es ist ein Cache-Problem: alle Daten im Vektor werden in einem zusammenhängenden Klumpen gespeichert, und jedes Listenelement wird separat zugeordnet und passieren können in ganz einem zufälligen Ort der Erinnerung gespeichert werden, was dazu führt, mehr Cache-Misses. Aber ich wette, dass Sie eines der Themen in den anderen Antworten beschrieben begegnen.

Answer 5

Die einfache Antwort ist über einen Vektor, weil Iterieren nicht gar laufen, es ist nur auf der Basis eines Arrays und die Elemente nacheinander zu lesen.

Ich sehe dies markiert ist C ++, nicht C, aber da sie die gleiche Sache unter der Decke zu tun ist es erwähnenswert, dass Sie Elemente am Anfang und Ende eines Arrays hinzufügen, können es beliebig groß durch die Zuweisung und realloc () ing und memmove () ing zwischen zwei Begleiter-Arrays, ob und wann Sie aus dem Zimmer laufen. Sehr schnell.

Der Trick Elemente am Anfang eines Arrays Zugabe ist der logische Anfang des Arrays zu Vorspannung durch den Zeiger in das Array zu Beginn Vorschieben und Sichern es dann auf, wenn Elemente an der Vorderseite hinzugefügt wird. (Auch die Art und Weise ein Stapel implementiert)

In genau der gleichen Weise kann C hergestellt werden, um negative Indizes zu unterstützen.

C ++ tut all dies für Sie mit dem Vektor STL-Klasse, aber immer noch daran zu erinnern, was unter der Decke vor sich geht.

Answer 6

[Edit: Ich stehe korrigiert. std :: Liste nicht über Operator []. Es tut uns Leid.]

Es ist schwer, aus Ihrer Beschreibung zu sagen, aber ich vermute, dass Sie die Einzelteile zufällig zuzugreifen versuchen, (das heißt, durch den Index):

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

Statt die Iteratoren verwenden:

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

Sowohl „vector“ & „Deque“ ist gut mit wahlfreiem Zugriff, so wird entweder durchführt angemessen für diese Typen --- O (1) in beiden Fällen. Aber „Liste“ ist zufällig Zugriff nicht gut. Zugreifen auf die Liste von Index würde O (n ^ 2) Zeit, im Vergleich zu O (1), wenn Iteratoren verwendet wird.