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.

Der Basisfall

Hinweis: Die Code-Schnipsel hier wurden aus Gründen der Kürze etwas bearbeitet. Die vollständige Quelle für die Experimente finden Sie auf Github.

Für jedes der Experimente erstellen wir eine Liste von Ganzzahlen, die viel größer als der Cache sind, damit wir sehen können, wie sich Cache-Misses auf die Performance auswirken. Mein Prozessor ist ein Intel Core i7 4790k mit 8MByte Cache, also verwende ich 80 MByte Integer. Wir wollen zunächst diese Ganzzahlen mit einigen zufälligen Werten initialisieren (hier im Bereich von 1-10), den Cache leeren, die Uhr starten und dann willkürlich an den Daten arbeiten. Hier werden die Quadrate aller Werte in der Liste gemittelt.

int doWork(const vector<int>& data)
{
    unsigned long sum = 0;

    for (int d : data)
        sum += d * d;

    return (int)(sum / data.size());
}

Wir werden aufzeichnen, wie lange dieser Lauf gedauert hat. Sobald wir alle unsere Läufe beendet haben, werden wir diese Testzeiten im Durchschnitt berechnen.

for (unsigned int i = 0; i < iterations; ++i)
{
    populateDataSet(data, rng);
    clearCache();

    const auto runStart = clk::now();
    const int result = doWork(data);
    const auto runTime = clk::now() - runStart;
    runSum += runTime;
    // Wir schreiben das Ergebnis aus, um sicherzustellen, dass
    // der Compiler die Arbeit nicht als toter Speicher eliminiert,
    // und um uns etwas zum Anschauen zu geben.

    cout << "Run " << i + 1 << ": " << result << "\r";
    cout.flush();
}

Das einzige, was wir für jedes Experiment ändern werden, ist die Art und Weise, wie auf die Daten zugegriffen wird. Für unser erstes Experiment greifen wir direkt auf die Daten zu, in sequentieller Reihenfolge. Unser Wissen über Prefetching sagt uns, dass dies unser schnellster Fall sein sollte. Ich bekomme hier:

$ g++ -Wall -Wextra -std=c++14 -O2 -o base base.cpp
$ ./base
Run 1000: 38
Laufzeit insgesamt 300,632 Sekunden (inklusive bookkeeping und cache clearing)
1000 Durchläufe dauerte insgesamt 10,444 Sekunden,
Durchschnittlich 10,444 Millisekunden pro Durchlauf

Das ist also ein Basisfall von etwa 10,4 Millisekunden bis zu unserem Integer von 80 MByte an Ganzzahlen.

Fall 2: Jetzt mit Indirektion

Leider ist es in einigen Sprachen nicht möglich, Werte direkt in einem zusammenhängenden Array zu speichern (zumindest nicht für benutzerdefinierte Typen). Stattdessen verwenden sie Referenzen, so dass unser Array zu einem Array von Zeigern wird. Im besten Fall werden die tatsächlichen Daten, auf die sie zeigen, in sequentieller Reihenfolge zugeordnet, so dass unser einziger Performance-Hit die Indirektion ist. Um dies zu simulieren, lassen Sie uns auf einem Array von Zeigern auf die Daten operieren, anstatt direkt auf die Daten zu operieren.

int doWork(const vector<int*>& data)
{
    unsigned long sum = 0;

    for (int* d : data)
        sum += *d * *d;

    return (int)(sum / data.size());
}
// vor unseren Tests,
auto pointers = vector<int*>(data.size());
for (size_t i = 0; i < data.size(); ++i)
    pointers[i] = &data[i];
}

Versuchen wir's damit:

$ g++ -Wall -Wextra -std=c++14 -O2 -o indirection indirection.cpp
$ ./indirection
Run 1000: 38
Laufzeit insgesamt 304,947 Sekunden (inklusive bookkeeping und cache clearing)
1000 Durchläufe dauerte insgesamt 12,860 Sekunden,
Durchschnittlich 12,860 Millisekunden pro Durchlauf

Wir stellen fest, dass die Performance nur etwas langsamer ist, da ein Teil unseres Cachespeicherplatzes von den Pointern belegt wird.

Fall 3: Nicht-durchgängige Allokationen

Unsere Annahme aus Fall 2, dass getrennte Zuweisungen in zusammenhängende Speicherplätze gelegt werden, ist schlecht. Möglicherweise wird benachbarter Speicher durch andere Zuweisungen aus unserem Programm belegt. Außerdem werden einige Allokatoren aus Sicherheitsgründen absichtlich Speicher an Pseudozufallsorten zuweisen. Das führt dazu, dass der Zugriff außerhalb der Grenzen einen Seitenfehler erzeugt, anstatt Dinge stillschweigend zu brechen.

Um dies zu simulieren, werden wir unsere Prozesse aus Fall 2 wiederholen, aber die Pointer zwischen den einzelnen Läufen mischen.

// Vor jedem Durchlauf
shuffle(begin(pointers), end(pointers), rng);

Dies wird der schlimmste Fall sein. Denn all die nicht zusammenhängenden Zugänge führen dazu, dass Prefetching fast völlig wirkungslos ist.

$ g++ -Wall -Wextra -std=c++14 -O2 -o random random.cpp
$ ./random
Run 1000: 38
Laufzeit insgesamt 1194,71 Sekunden (inklusive bookkeeping und cache clearing)
1000 Durchläufe dauerte insgesamt 164,585 Sekunden,
Durchschnittlich 164,585 Millisekunden pro Durchlauf

Allein dadurch, dass wir die gleiche Arbeit in einer anderen Reihenfolge machen, sind wir bereits eine Größenordnung langsamer.

Wahrscheinlich ist es tatsächlich noch schlimmer

Diese Experimente sind ziemlich vereinfachte Annäherungen an den Speicherzugriff in "echten" Programmen, was noch schlimmer sein könnte. Wenn Sie an Daten arbeiten, die größer oder komplexer als eine magere Ganzzahl sind, wird jedes Element weiter voneinander entfernt sein. So kann die Speicherarchitektur nicht so viele Elemente auf einmal vorab abrufen. Und Datenstrukturen außer Arrays neigen dazu, mehr Indirektion zu verwenden, da sie weniger cachefreundlich außerhalb des Gates sind.

Schlussfolgerungen

Die wichtigste Lektion die wir hier gelernt haben ist, dass die Art und Weise, wie Sie Ihren Speicher arrangieren und darauf zugreifen, enorme Auswirkungen auf die Performance hat. Praktischer ausgedrückt:

1. Sie erhalten massive, "freie" Leistungssteigerungen, indem Sie Daten, die zusammen verwendet werden, dicht beieinander im Speicher ablegen. Betrachten Sie Entitäten in einigen hypothetischen Spiel-Engine:

class GameEntity {
    AIComponent ai;
    PhysicsComponent physics;
    RenderComponent render;
};

// Anderswo...
vector entities;

// Anderswo...
// (wahnsinnig übervereinfacht) main game loop
for (auto& ge : entities) {
    ge.ai.update();
    ge.physics.update();
    ge.render.draw();
}

Wenn die Berechnungen für AI-Komponenten auf andere AI-Komponenten zugreifen, die Physikkomponenten auf andere Physikkomponenten zugreifen, und so weiter, können wir die Dinge beschleunigen, indem wir diese jeweiligen Komponenten im Speicher einander näher bringen:

class GameEntity {
AIComponent* ai;
PhysicsComponent* physics;
RenderComponent* render;
};

// Anderswo...
vector entities;
vector aiComponents;
vector physicsComponents;
vector renderComponents;

// Anderswo...
// (wahnsinnig übervereinfacht) main game loops
for (auto& a : aiComponents) { a.update(); }
for (auto& p : physicsComponents) { p.update(); }
for (auto& r : renderComponents) { r.draw(); }

Eine solche kleine Änderung kann enorme Leistungsvorteile mit sich bringen. Das soll nicht heißen, dass man versuchen sollte, alles in ein Array zu schieben, wenn die Situation eine andere Datenstruktur erfordert. Statt dessen sollte man nach Möglichkeiten wie der hier gezeigten Ausschau halten.

2. Berücksichtigen Sie bei der Auswahl eines Algorithmus oder einer Datenstruktur dessen Speicherzugriffsmuster. Mehr Programmieraufwand, der letztlich weniger Cache-Fehler verursacht, kann schneller sein. Die Komplexitätsanalyse ist nur ein grober Anhaltspunkt für die Performance.

Kommen wir noch einmal auf unsere ursprüngliche Diskussion zurück, in der wir verknüpfte Listen mit Arrays vergleichen. Auf dem Papier sollte das Entfernen aus der Mitte eines Arrays viel länger dauern als das Entfernen aus der Mitte einer verknüpften Liste. Aber wenn Sie zuerst die Liste durchlaufen müssen, um das Element zu finden, skaliert eine Traversierung und Entfernung aus einem Array tatsächlich viel besser als eine Traversierung und Entfernung aus einer verknüpften Liste aufgrund der Cache-Freundlichkeit eines Arrays.

Der Speicher zählt. Alle ernsthaften Optimierungsbemühungen für Ihre Anwendung müssen ihn berücksichtigen. Nur wenn der Prozessor nicht auf Cache-Fehler wartet, kann auch die entsprechend höhere Leistung effizient genutzt werden.

Hardwarenahe Softwareentwicklung

Hardwarenahe Softwareentwicklung

08.12.17 - Ein Thema wie hardwarenahe Programmierung in einer Hochsprache sollte es eigentlich gar nicht geben, denn Hochsprache impliziert Hardwareunabhängigkeit – und nicht ein spezifisches Eingehen auf die Eigenheiten selbiger. lesen

Hard- und Softwareaspekte für optimierte Embedded Systeme

Leistung und Zuverlässigkeit

Hard- und Softwareaspekte für optimierte Embedded Systeme

06.02.17 - So lässt sich durch die Wahl der richtigen, ECC-geeigneten Prozessoren und Speicher die Systemsicherheit im Embedded-Bereich deutlich steigern. lesen

Hard- und Softwareaspekte für optimierte Embedded Systeme - Teil 2

Stabilität und Zuverlässigkeit

Hard- und Softwareaspekte für optimierte Embedded Systeme - Teil 2

06.03.17 - Im ersten Teil dieses Beitrags befassten wir uns mit einem Vergleich unterschiedlicher CPU-Plattformen und zeigten, wie gute bzw. schlechte Programmierung deren Performance beeinflussen kann. Im zweiten Teil beleuchten wir näher, welche Auswirkungen die Wahl der Speicherarchitektur auf die Leistung und Zuverlässigkeit eines Embedded Systems hat. lesen

* Der Autor: Matt Kline ist Software Engineer für Fluke Networks und Betreiber des Software-Entwicklungs-Blogs bitbashing.io. Der Beitrag "Time Between The Lines: how memory access affects performance" wurde lizensiert nach einer Creative Commons Attribution-ShareAlike 4.0 International License. (CC BY-SA 4.0). Übersetzung Sebastian Gerstl.

Kommentar zu diesem Artikel abgeben

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

Zur Wahrung unserer Interessen speichern wir zusätzlich zu den o.g. Informationen die IP-Adresse. Dies dient ausschließlich dem Zweck, dass Sie als Urheber des Kommentars identifiziert werden können. Rechtliche Grundlage ist die Wahrung berechtigter Interessen gem. Art 6 Abs 1 lit. f) DSGVO.
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)