Ein Angebot von

Wie sich Speicherzugriff auf die Systemleistung auswirkt

| Autor / Redakteur: Matt Kline * / Sebastian Gerstl

Die-Map einer Quadcore-CPU aus der 7. Intel-Core-Architektur (Kaby Lake). Anzumerken ist, dass ein guter Teil jedes Kerns auch L1- und L2-Cache ist.
Die-Map einer Quadcore-CPU aus der 7. Intel-Core-Architektur (Kaby Lake). Anzumerken ist, dass ein guter Teil jedes Kerns auch L1- und L2-Cache ist. (Bild: Wikichip.org)

Die effektive Leistung von Prozessoren und Speichern haben sich im Laufe der Jahre massiv verbessert - aber nicht im selben Maße. Um in einem System die Leistung bestmöglich zu optimieren, muss auch effektiv mit der Speicher- und Cache-Verwaltung umgegangen werden.

Eine der Hauptaufgaben eines Programmierers ist es, über Algorithmen nachzudenken und sie anzuwenden. Eines der hilfreichsten Werkzeuge hierfür ist die Komplexitätsanalyse. Gemessen in der "Big O"-Notation gibt die Komplexität eines Algorithmus eine ungefähre Vorstellung davon, wie schnell er bei unterschiedlichen Eingabegrößen arbeitet.

Zum Beispiel bringt sie in Erfahrung, dass das Einfügen eines Elements in die Mitte einer verknüpften Liste eine konstante Zeit-Operation (O(1)) ist, während das Einfügen in die Mitte eines Arrays in linearer Zeit (O(n)) erfolgt, da wir alle nachfolgenden Elemente verschieben müssen, um Platz zu schaffen. Eine solche Analyse ermöglicht es, fundierte Entscheidungen über die Gestaltung unserer Programme zu treffen.

Die klassische Komplexitätsanalyse geht aber meist von der Annahme aus, dass alle Speicherzugriffe gleichwertig sind. Auf moderner Hardware ist das einfach nicht wahr. In der Tat, es ist extrem falsch.

Speicherhierarchien

Am Anfang war die gesamte Hardware langsam. Aber das war in Ordnung - wirklich kluge Leute waren in der Lage, tolle Sachen damit zu machen – wie zum Beispiel mit einer 2 MHz CPU und 4 Kilobyte RAM im Apollo Guidance Computer Leute auf dem Mond landen zu lassen.

Unterdessen sagte ein Mann namens Moore voraus, dass Computerentwürfe mit einer exponentiellen Rate beschleunigen würden – und wie es der Zufall wollte, lag er damit richtig. Neue Prozessoren wurden immer schneller und schneller, ebenso wie der Speicher. Aber CPU-Fortschritte übertrafen die des Arbeitsspeichers, und das begann problematisch zu werden. Denn obwohl beide schneller als je zuvor waren, musste der Prozessor immer mehr Zyklen warten, um Daten aus dem Speicher zu holen. Und wenn der Prozessor herumsteht und nichts tut, ist das nicht gut für die Leistung des Systems.

Um das zu adressieren nahmen Hardware-Ingenieure also etwas RAM und legten es direkt auf den CPU-Chip, so dass man schneller darauf zugreifen konnte. Jetzt hatten Programmierer ein zweischichtiges System: Wenn der Prozessor etwas aus dem Speicher benötigt, würde er zuerst diesen On-Die-Cache überprüfen. Es besteht eine gute Chance, dass ein Programm den gleichen Speicher wiederholt verwendet, so dass wir über den gesamten Lauf viel Zeit sparen. Das funktionierte so gut, dass Hardware-Designer anfingen, einen Cache für den Cache und dann einen Cache für den Cache hinzuzufügen. In diesen Tagen ist es nicht ungewöhnlich, dass Desktop-CPUs Level 1, 2 und 3 Caches haben, die einen guten Teil eines CPU-Die beanspruchen.

Prefetching

Hardware-Designer hatten noch einen weiteren Trick im Ärmel: Sie haben bemerkt, dass ein Programm, das auf einen Teil des Speichers zugreift, wahrscheinlich als nächstes auf den nahegelegenen Speicher zugreifen wird. Dieses Konzept wird oft als spatial locality (Räumliche Lokalität) bezeichnet. Wenn Programmierer also wegen eines Cache-Fehlers in den Hauptspeicher gehen müssen, können sie Zeit sparen, indem sie einige benachbarte Daten holen, um diese zusammen mit dem, was der Programmierer gerade jetzt braucht, in den Cache zu legen. Dies wird als Prefetching bezeichnet.

Dieses Wissen hat eine massive Konsequenz: Die Reihenfolge, in der ein Programm auf den Speicher zugreift, hat einen Einfluss darauf, wie schnell ein Programm läuft. Der sequentielle Zugriff auf den Speicher ist schneller als jeder andere Speicherzugriff. Wie viel schneller? Machen wir ein paar Experimente.

Annahmen und Disclaimer

Sie als Leser könnten (richtigerweise) die Vorstellung bekommen, dass moderne Prozessoren extrem kompliziert sind und alle möglichen Tricks spielen, um mehr Leistung aus Ihrem Code herauszuholen. Das macht das Timing und das Benchmarking schwierig. Für die folgenden Experimente versuche ich mit den folgenden Schritten die Anzahl der unerwünschten Variablen zu minimieren.

1. Um jeden Lauf mit einem "leeren" CPU-Cache zu starten, der keine Daten zum Experiment enthält, "löschen" wir ihn, indem wir vor einem Probelauf einen unabhängigen Puffer kopieren, der so groß wie der Cache ist. Dies sollte den Cache mit den Daten des Dummy-Puffers füllen und die CPU dazu zwingen, zunächst alle unsere Experimentdaten aus dem Hauptspeicher zu holen.

2. Um die Auswirkungen anderer Prozesse und des Betriebssystems auf unsere Metriken zu minimieren, haben ich mich dazu entschlossen, die folgenden Maßnahmen zu ergreifen:

  • Zu vermeiden, während des Experiments möglichst viele andere Prozesse laufen zu lassen.
  • Keine I/Os durchzuführen (was zu einem Stillstand führen kann, während man darauf wartet, bis das entsprechende Gerät betriebsbereit ist).
  • Eine große Anzahl von Versuchen durchzuführen (in der Regel eine gute Idee in jedem Experiment).
  • Für jedes Experiment eine beträchtliche Zeit (zumindest für einen Computer) in Anspruch zu nehmen. Dabei kann man hoffentlich Unregelmäßigkeiten, die durch Unterbrechungen verursacht werden, ausgleichen.
  • Für die Messungen einen systemgestützten, hochauflösenden Taktgeber zu verwenden.

Inhalt des Artikels:

Kommentar zu diesem Artikel abgeben

Schreiben Sie uns hier Ihre Meinung ...
(nicht registrierter User)

Kommentar abschicken
copyright

Dieser Beitrag ist urheberrechtlich geschützt. Sie wollen ihn für Ihre Zwecke verwenden? Infos finden Sie unter www.mycontentfactory.de (ID: 45026999 / Software Engineering)