Warum ist die Cache-Lokalität für die Array-Leistung wichtig?

70

Im folgenden Blog gibt es eine Aussage über den Vorteil von Arrays gegenüber verknüpften Listen:

Arrays haben eine bessere Cache-Lokalität, was einen ziemlich großen Unterschied in der Leistung bewirken kann.

Was bedeutet das? Ich verstehe nicht, wie die Cache-Lokalität einen enormen Leistungsvorteil bieten kann.

arrays language-agnostic linked-list Vaibhav Mishra
quelle
3
Wenn Sie verstehen, wie der Cache funktioniert, werden Sie auch verstehen, dass 1) "Lokalität der Referenz" eine gute Sache ist und 2) der Zugriff auf Daten von Arrays normalerweise eher eine gute "Lokalität" aufweist als der Zugriff auf dieselben Daten aus einer Liste .
Pauls4
1
Eine bemerkenswerte Sache ist, dass eine einfach verknüpfte Liste in Kombination mit einem zusammenhängenden Allokator ein enormer Vorteil sein kann, vor allem, weil das Übertragen von Elementen von einem Container in einen anderen nur eine Zeigerlogik beinhaltet. Wenn Sie sich das Speicherlayout dieser Elemente ansehen, ist es jedoch zusammenhängend und sieht aus wie ein Array mit nur Links zum nächsten Element im Array. Daher ist es immer noch cachefreundlich (zumindest bis die Liste vollständig neu organisiert ist).

Antworten:

107

Siehe meine Antwort zur räumlichen und zeitlichen Lokalität .

Insbesondere sind Arrays zusammenhängende Speicherblöcke, so dass große Teile davon beim ersten Zugriff in den Cache geladen werden. Dies macht es vergleichsweise schnell, auf zukünftige Elemente des Arrays zuzugreifen. Verknüpfte Listen hingegen befinden sich nicht unbedingt in zusammenhängenden Speicherblöcken und können zu mehr Cache-Fehlern führen, was die Zugriffszeit erhöht.

Berücksichtigen Sie die folgenden möglichen Speicherlayouts für ein Array dataund eine verknüpfte Liste l_datagroßer Strukturen

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

Wenn wir dieses Array durchlaufen ffff 0000möchten, müssen wir für den ersten Zugriff auf zum Speichern in den Speicher gehen (ein sehr langsamer Vorgang in CPU-Zyklen). Nach dem ersten Zugriff befindet sich der Rest des Arrays jedoch im Cache, und nachfolgende Zugriffe sind viel schneller. Bei der verknüpften Liste ffff 1000müssten wir für den ersten Zugriff auf auch in den Speicher gehen. Leider wird der Prozessor den Speicher, der diesen Speicherort direkt umgibt, zwischenspeichern, etwa bis zu ffff 2000. Wie Sie sehen können, erfasst dies keines der anderen Elemente der Liste, was bedeutet, dass wir beim Zugriff l_data->nexterneut in den Speicher wechseln müssen.

brc
quelle
6
Beachten Sie, dass die Lokalität verknüpfter Listen durch Verwendung eines Speicherpools verbessert werden kann. Sie haben jedoch immer noch das Problem, dass "nächste" Zeiger zusätzlichen Platz beanspruchen.
Reis
1
@paddy macht einen guten Punkt, weil häufig so verknüpfte Listen implementiert werden
brc
Jetzt habe ich verstanden, was "Cache-Fehler in verknüpfter Liste" bedeutet.
AKS
Ist die Referenzlokalität verknüpfter Listen räumlich oder zeitlich oder beides oder keine?
Shubham
11

Wenn Sie ein Array verwenden, greifen Sie normalerweise auf Elemente zu, die sich in der Nähe befinden. Dies gilt insbesondere für den sequentiellen Zugriff auf ein Array.

Wenn Sie auf den Speicher zugreifen, werden Teile davon auf verschiedenen Ebenen zwischengespeichert. Die Cache-Lokalität bezieht sich auf die Wahrscheinlichkeit, dass sich aufeinanderfolgende Operationen im Cache befinden und somit schneller sind. In einem Array maximieren Sie die Wahrscheinlichkeit, dass sich der sequentielle Elementzugriff im Cache befindet.

Bei Listen gibt es beispielsweise im Gegenbeispiel keine Garantie dafür, dass Elemente, die nacheinander in der Liste erscheinen, tatsächlich nahe beieinander im Speicher angeordnet sind. Dies bedeutet weniger Cache-Treffer und eine verminderte Leistung.

Paddy
quelle
Dies hängt jedoch stark vom Prozessor und der Speicherarchitektur ab. CPUs, die beispielsweise für die objektorientierte Programmierung ausgelegt sind, interessieren sich normalerweise nicht für die Lokalität, einfach weil Sie durch die Definition von "objektorientiert" die Lokalität ohnehin nicht garantieren können.
Jörg W Mittag
@ JörgWMittag Wollen Sie damit sagen, dass in OOP-Sprachen geschriebene Programme die Caches nicht effektiv nutzen, oder dass in diesem Fall mehr Cache-Fehler auftreten als in einer prozeduralen Sprache geschriebene Programme?
Saurabh Patil