Im folgenden blog gibt es eine Aussage über den Vorteil von Arrays über verkettete Listen:Warum spielt die Cache-Lokalität für die Array-Leistung eine Rolle?
Arrays besser Cache Ort haben, die einen ziemlich großen Unterschied in der Leistung zu machen.
Was bedeutet das? Ich verstehe nicht, wie Cache Locality einen enormen Leistungsvorteil bieten kann.
Siehe meine Antwort about spatial and temporal locality.
Insbesondere Arrays sind zusammenhängende Speicherblöcke, so dass große Teile davon beim ersten Zugriff in den Cache geladen werden. Dies ermöglicht einen vergleichsweise schnellen Zugriff auf zukünftige Elemente des Arrays. Verknüpfte Listen andererseits befinden sich nicht notwendigerweise in zusammenhängenden Speicherblöcken und könnten zu mehr Cache-Misses führen, was die Zeit erhöht, die für den Zugriff auf sie benötigt wird.
Betrachten Sie das folgende mögliche Speicherlayout für ein Array data und verkettete Liste l_data großen structs
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 eine Schleife durch dieses Array, der erste Zugriff auf ffff 0000 erfordern würde uns in den Speichern zu gehen, wollten abrufen (ein sehr langsamer Vorgang in CPU-Zyklen). Nach dem ersten Zugriff wäre der Rest des Arrays jedoch im Cache, und nachfolgende Zugriffe wären viel schneller. Mit der verknüpften Liste würde der erste Zugriff auf ffff 1000 auch erfordern, dass wir in den Speicher gehen. Unglücklicherweise speichert der Prozessor den Speicher, der diesen Ort direkt umgibt, bis zu ffff 2000. Wie Sie sehen können, erfasst dies tatsächlich keine der anderen Elemente der Liste, was bedeutet, dass wir, wenn wir auf zugreifen, erneut in den Speicher gehen müssen.
Beachten Sie, dass die Lokalität verknüpfter Listen durch die Verwendung eines Speicherpools verbessert werden kann. Aber Sie haben immer noch das Problem, dass "nächste" Zeiger zusätzlichen Platz benötigen. – paddy
@paddy macht einen guten Punkt, weil häufig so verknüpfte Listen implementiert werden – brc
Jetzt habe ich was "Cache vermisst in Linked List" bedeutet. – AKS
Wenn Sie ein Array verwenden, greifen Sie normalerweise auf Objekte zu, die nahe beieinander liegen. Dies gilt insbesondere für den sequentiellen Zugriff auf ein Array.
Wenn Sie auf Speicher zugreifen, werden Teile davon auf verschiedenen Ebenen zwischengespeichert. Die Cache-Position bezieht sich auf die Wahrscheinlichkeit, dass sich nachfolgende Operationen im Cache befinden und somit schneller sind. In einem Array maximieren Sie die Wahrscheinlichkeit, dass sequentieller Zugriff auf Elemente im Cache erfolgt.
Bei Listen, bei Gegenbeispiel, gibt es keine Garantie, dass Elemente, die nacheinander in der Liste erscheinen, tatsächlich im Speicher nebeneinander angeordnet sind. Dies bedeutet weniger Cachetreffer und verringerte die Leistung.
Dies hängt jedoch sehr vom Prozessor und der Speicherarchitektur ab. CPUs, die beispielsweise für die objektorientierte Programmierung ausgelegt sind, interessieren sich in der Regel nicht für die Lokalität, einfach weil die Lokalität durch die * Definition * von "objektorientiert" ohnehin nicht garantiert werden kann. –
Wenn Sie verstehen, wie [Cache] (http://en.wikipedia.org/wiki/Locality_of_reference) funktioniert, dann werden Sie auch verstehen 1) "Ort der Referenz" ist eine gute Sache, und 2) Zugriff auf Daten von Arrays ist in der Regel eher eine gute "Lokalität" als der Zugriff auf dieselben Daten aus einer Liste. – paulsm4
Bemerkenswert ist, dass, obwohl dies zutrifft, eine einfach verknüpfte Liste in Kombination mit einem zusammenhängenden Zuordner ein enormer Vorteil sein kann, vor allem weil die Übertragung von Elementen von einem Container zu einem anderen nur die Zeigerlogik betrifft. Wenn Sie sich das Speicherlayout ansehen, ist es jedoch zusammenhängend und sieht aus wie ein Array mit nur Verknüpfungen zum nächsten Element im Array, und daher ist es immer noch Cache-freundlich (zumindest bis die Liste vollständig reorganisiert ist). –