Auf das Element in einem Knoten in einer aufgerollten verketteten Liste wird sehr schnell zugegriffen .
Auf die Bytes in einer zwischengespeicherten Zeile wird sehr schnell zugegriffen.
Wir können die Analogie hier sehen, die abgerollten verketteten Listen sind dort, um die Einzelteile in ununterbrochenen Bereich des Gedächtnisses so zu verdichten, damit sie mehr cachefreundlich sind.
Um zu sehen, warum ein Knoten größer als eine Cache-Zeile ein Problem sein kann, betrachten Sie eine Architektur mit einem Cache (von beliebiger Assoziativität) mit nur einer Zeile der Größe S.
Betrachten Sie auch eine abgerollte Liste mit Knotengröße 2S.
Schließlich läßt das Cache-Misses des Algorithmus
For each node N
Let avg = ArithmeticMean(N.items)
For i = 0 To N.numerOfItems - 1
N.items[i] = avg
, dass der Wert der einzelnen Elemente gesetzt analysieren (eine vollständige Knoten annehmen) in einem Knoten auf das arithmetische Mittel des Knotens.
Um den Mittelwert zu berechnen, müssen alle Elemente summiert werden, wobei der Zugriff auf das erste Element eine Cache-Last (+1) auslöst. Innerhalb der ersten Hälfte werden die Elemente aus der gerade geladenen Cache-Zeile gelesen.
Sobald auf das erste Element in der zweiten Hälfte zugegriffen wird, ist eine weitere Cache-Ladung erforderlich, und die alte Zeile wird geleert (+2). Bis zum Ende des Knotens erfüllen diese zweiten Lasten alle zukünftigen Zugriffe.
Sobald wir den Mittelwert haben, wird die erste Hälfte erneut mit einer nachfolgenden Cache-Last (+3) aufgerufen, wodurch die Zeile mit der zweiten Hälfte gelöscht wird, die später (+4) erneut geladen wird.
Der Algorithmus löst 4 Cache-Lasten für Knoten aus. Wenn wir die Größe des Knotens S machen und die Analyse wiederholen, werden wir sehen, dass nur eine Cache-Auslastung erforderlich ist.
Wenn Sie den Knoten kleiner als die Cache-Zeilen machen, können auch einige Knoten die gleiche Zeile teilen, was aber im Allgemeinen nicht schadet. Dies wird jedoch mehr Zeilen im Vergleich zur Gesamtzahl der Elemente in der Liste verwenden, da jeder an seiner eigenen Adresse ist und sie nicht notwendigerweise nahe beieinander sind. In der Grenze, wenn S = 1 wir haben eine normale verkettete Liste.
Bisher haben alle nicht so alten Intel-CPU 64 Bytes Cache-Zeile.
Das kann sich aber sehr gut ändern.
Um Ihre CPU-Cache-Informationen zu sehen, können Sie auf diese Frage verweisen: finding L2 cache size in Linux .
Es läuft auf sudo dmidecode -t cache zu verwenden.
Dank der Tatsache, dass eine Anordnung, die Elemente zu speichern, verwendet wird, einen Direktzugriffs ermöglicht.
Für alle Cache-Ebenen infact.