Speicherhierarchie und Leistung

Warum wird das Durchlaufen der obigen verketteten Liste tendenziell deutlich langsamer als das Lesen eines Arrays mit gleich vielen Elementen?

struct node { int val; struct node *next; };
for (p = head; p != NULL; p = p->next)
    sum += p->val;
  1. AWeil die Adresse des nächsten Elements erst bekannt ist, wenn das aktuelle gelesen wurde, und Misses nacheinander einzeln auftreten
  2. BWeil Elemente verketteter Listen grundsätzlich nie in den Cache gelangen
  3. CWeil bei Verarbeitungen mit Zeigern die Sprungvorhersage der CPU stets fehlschlägt
Antwort und Erläuterung anzeigen

Antwort: A. Weil die Adresse des nächsten Elements erst bekannt ist, wenn das aktuelle gelesen wurde, und Misses nacheinander einzeln auftreten

Bei einer verketteten Liste ist die Adresse des nächsten Elements erst bekannt, nachdem p->next gelesen wurde. Liegen die Elemente verstreut im Speicher, tritt bei jedem Zugriff ein Miss auf, und da die nächste Adresse unbekannt ist, lassen sich mehrere Misses nicht überlappen; die Wartezeit auf den Hauptspeicher addiert sich pro Element vollständig auf. Bei einem Array ist die nächste Adresse berechenbar, und Prefetch sowie Überlappung von Misses wirken. Auch Elemente verketteter Listen gelangen in den Cache, und der Schleifensprung ist gut vorhersagbar und schlägt nicht stets fehl.

Dieses Thema üben Zur Themenseite

Weitere Fragen zu Speicherhierarchie und Leistung

  1. Pro Miss wird eine 64-Byte-Zeile gelesen, die Wartezeit auf den Hauptspeicher beträgt 100 ns; kann nur ein Miss gleichzeitig bearbeitet werden, bleibt die Lesebandbreite bei etwa 0,64 GB/s. Wie hoch wird die Bandbreite ungefähr, wenn 10 Misses gleichzeitig bearbeitet werden können (andere Einschränkungen seien nicht vorhanden)?
  2. Was ist der Hauptvorteil von Stores, die den Cache umgehen (Non-Temporal Stores), wenn große Datenmengen geschrieben werden, die danach vorerst nicht wieder gelesen werden?
  3. Wie hoch ist die Miss-Rate, wenn die Trefferrate des Caches 95 % beträgt?
  4. Welches Verfahren sendet beim Laden einer Miss-Zeile aus dem Hauptspeicher zuerst das von der CPU benötigte Wort und den Rest später?
  5. Warum wird es tendenziell schneller, die beiden obigen Schleifen zu einer zusammenzufassen (Loop Fusion), wenn N groß ist?

Vergleiche zu diesem Thema