Einleitung
Der CPU-Cache hat einen großen Einfluss auf die Performanz einer Applikation. Dies wird sehr ausführlich in dem Dokument “What Every Programmer Should Know About Memory" erörtert, das einen tiefen Blick in die Innereien einer modernen CPU gibt.Alle Informationen sind sprachunabhängig und gelten für alle Programmiersprachen, nur sind die meisten Beispiele in C/ C++ geschrieben und nicht 1:1 auf Java übertragbar. In diesem Artikel will ich näher untersuchen, in welchen Fällen man von dem CPU-Cache in Java profitieren kann. Nach vorherrschender Meinung sollte man nicht versuchen, die Applikation explizit dafür zu optimieren. Aber warum nicht? Wo ist die Grenze?
Java versteckt eine Menge Informationen über Low-Level-Operationen vor dem Entwickler, der sich daher um vieles nicht mehr kümmern muss. Das macht Java zu einer einfach zu lernenden Sprache, bei der der Entwickler sich nicht schon von Beginn an um den Lebenszyklus der Objekte kümmern oder mit Pointern herumschlagen muss. Anderseits können unter der Haube Laufzeitoptimierungen durchgeführt werden, die mit einer kompilierten Sprache wie C++ nicht möglich sind. Anderererseits können gerade diese alle Optimierungsversuche zunichtemachen.
Eine kleine Warnung vorab: Bevor man sich mit CPU-Caches auseinandersetzt, sollte man Algorithmen und deren Komplexität verstanden haben. Performanzprobleme gehen sehr viel häufiger auf falsch ausgewählte Algorithmen zurück als auf den CPU-Cache.
Bevor ich zu den Performanztests komme, noch ein paar Hintergrundinformationen:
Speicher
In Java hat man keine Kontrolle, wo auf dem Heap ein Speicherblock alloziert wird. Man kann davon ausgehen, dass ein Array oder ein Objekt als ein Speicherblock alloziert wird. Einen gewissen Einfluss kann man über die Kommandozeilenparameter wie -XX:+UseTLAB, -XX:+UseLargePages, ... nehmen. Welche Auswirkungen diese auf die Performanz haben und wann sie sich lohnen, wäre ebenfalls ein interessantes Thema, das an dieser Stelle zu weit führt .Garbage Collector
Der Garbage Collector (GC) ist sicherlich das wichtigste Feature in Java. Er vereinfacht die Speicherverwaltung massiv, so dass Applikationen ohne Speicherlöcher selbst von Anfänger geschrieben werden können. Dass jeder die Laufzeit beeinflussende speicherrelevante Aspekt eines Objekts bekannt ist, macht die Analyse außerdem sehr viel einfacher als z. B. in C++. Aktuell existieren mehrere verschieden GC mit einer Vielzahl von Optionen, durch die verschiedenste Anforderungen erfüllt werden können. Aber der GC räumt nicht nur Objekte auf, sondern hat noch mehr Funktionen, die Optimierungen erschweren.Einfache Tests
Wir starten mit ein paar einfachen Speicherzugriffstests und gehen dann zu einer einfachen Routine, die einen Bewegungsvektor zu einer Koordinate addiert. Der erste Test ist eine Schleife und hat den ersten Fehler. Hier habe ich aus Gewohnheit Long statt long verwendet. Wie sehr die Performanz davon beeinträchtigt wird, wird am folgenden Beispiel ersichtlich. Wenn Geschwindigkeit benötigt wird, sollte man in Berechnungen oder bei veränderbaren Daten immer primitive Datentypen verwenden.long sum = 0L;
for(int i = 0; i < size; i++) {
sum++;
}
>> Zeit: 0.013913 sLong sum = 0L;
for(int i = 0; i < size; i++) {
sum++;
}
>> Zeit 2.162704 sEs gibt eine ganze Reihe von Webseiten, die sich mit Performanz beschäftigen und auch Frameworks, die Performanztests vereinfachen.
Array-Zugriff
Der erste Test ist ein einfacher Zugriff auf Arrays unterschiedlicher Größen. Die Größe des Arrays wird bei jedem Durchlauf verdoppelt, während die Anzahl der Zugriffe immer gleich bleibt (in meinen Beispiel 100.000.000 mal). Der zweite Test greift nicht sequenziell zu, sondern verwendet ein Zufallsmuster, das in einem zweiten Array mit gleicher Größe abgelegt wird.public static Long testOffsetArrayAccess(int maxAccess, int size,
float[] array) {
float sum = 0;
int andSize = size - 1;
for (int i = 0; i < maxAccess; i++) {
int pos = i & andSize;
sum += array[pos];
}
return (long) sum;
}
public static Long testRandArrayAccess(int maxAccess, int size,
float[] array, int[] rand) {
float sum = 0;
int andSize = size - 1;
for (int i = 0; i < maxAccess; i++) {
int pos = rand[i & andSize];
sum += array[pos];
}
return (long) sum;
}
Die gemessenen Zeiten sind im folgenden Graphen dargestellt.
Der Graph offenbart einige interessante Details:
- Die minimale Zeit für einen Zugriff ist in diesem Beispiel 0,9ns.
- Ein ähnlicher Test in C ergab die gleiche Zugriffszeit von rund 0,9ns, was aber auch nicht überraschend ist, da der Just-In-Time (JIT) sehr ähnlichen Code wie der C-Compiler erzeugt. Java müsste eigentlich etwas langsamer sein, da es noch die Array-Grenzen überprüft, aber die Dauer des Speicherzugriffs scheint dies zu überdecken.
- Die Zugriffszeit für den seriellen Zugriff bleibt über die gesamte Testreihe dieselbe. Während der Prozessor die Daten addiert, werden im Hintergrund schon die nächsten Speicherzellen in den Cache geladen (Prefetching).
- Der Zugriff auf das zweite Array mit den Zufallszahlen hat bei kleinen Größen keine Auswirkung auf die Gesamtdauer.
- Der zufällige Zugriff bricht bei meinem Prozessor dann bei ungefähr 256KB und 1MB jeweils ein, was den L1/L2-Cachegrößen entspricht. Die grünen Linien stellen die Cachegrenzen dar.
Nebenbemerkung: Der gleiche Test wurde auch in C durchgeführt wobei der vom gcc erzeugte Code dreimal so schnell wie in Java war. Bei dieser ersten Version wurde beim Zugriff auf das Array in Java und C % (modulo) statt & (and) verwendet. Modulo wird in Java in ein idiv umgewandelt, während der gcc eine optimierte Version ohne Division benutzt.
Wie in C/C++ kann auch in Java der Einfluss des CPU Caches bei Arrays gezeigt werden. Was passiert aber, wenn Objekte verwendet werden?
Objekte
Dieser Teil widmet sich ganz den Objekten. Hier wird zu einer 3D-Position ein Bewegungsvektor addiert und wieder zurückgespeichert. Es werden also insgesamt sechs float-Variablen gelesen und davon drei float-Variablen überschrieben. Die Objekte werden in zwei ArrayLists gespeichert. Leider bietet Java keine Objektarrays wie C++ (std::vector<T>) sondern nur Arrays von primitiven Typen. Die ArrayList speichert immerhin die Zeiger in einem Array und entspricht damit einem std::vector<T *>. Während eines Testlaufs werden keine Objekte erzeugt oder zerstört.simple
Der erste Test ist:public static Long testSerialECSAccess(int maxAccess, int size,
ArrayList<Position> positions,
ArrayList<Movement> movements) {
int andSize = size - 1;
for (int i = 0; i < maxAccess; i++) {
int pos = i & andSize;
Position position = positions.get(pos);
Movement movement = movements.get(pos);
position.x += movement.x;
position.y += movement.y;
position.z += movement.z;
}
return 0L;
}
Das Ergebnis ist im Graphen als “simple” gekennzeichnet.
Wieder ändert sich die Arraygröße, die Anzahl der Zugriffe hingegen bleibt gleich. Wie im Graphen zu sehen ist , steigt die Gesamtzeit nach 65.000 Elementen an. Dies entspricht rund 3,6 MB an Speicher, der nächste Schritt ist schon über die 6-MB-Grenze des L3-Caches. Die Größe eines Elements setzt sich aus 2 Objekten (Position, Movement) mit jeweils 24 Bytes und zwei ArrayList-Zeigern auf die Objekte mit jeweils 4 Bytes (Compressed Oops) zusammen, was 56 Bytes ergibt.
Es wäre zwar blauäugig anzunehmen, dass die Daten alle sequenziell angeordnet im Speicher liegen, aber dass es zu einem leichten Anstieg wie bei einem zufälligen Zugriff kommt, ist zunächst einmal erstaunlich. Die Daten wurden ja alle seriell erzeugt, werden in der gleichen Reihenfolge abgefragt und es gibt keine parallel laufende Threads.
Mit einer kleinen Methode kann man sich die Speicheradressen der Objekte ausgeben lassen. Der folgende Code erzeugt 10.000 Objektpaare:
ArrayList<Position> positions = new ArrayList<>(10000);
ArrayList<Movement> movements = new ArrayList<>(10000);
for (int i = 0; i < 10000; i++) {
positions.add(new Position());
movements.add(new Movement());
}
Die Objekte sind am Ende der Schleife folgendermaßen im Speicher angeordnet (P = Position, M = Movement, Zahl ist der Index im Array):P0 M0 P1 M1 P2 M2 P3 M3 P4 M4 P5 M5 P6 M6 P7 M7 P8 M8 P9 ...
Also ganz so, wie es zu erwarten war. Bei 100.000 Paaren jedoch ist das Ergebnis überraschend. Die Anordnung ist jetzt wie folgt:
M80600-M80200 P16400-P16000 M80200-M78000 ...
Bei explizitem Aufruf des GC (System.gc()) erhält man immer dieses Anordnung. Was ist also passiert?
Es ist ein Fehler im Testsetup. Die VM hat nach einigen Testrunden beschlossen, den Speicher aufzuräumen. Stellt man ein, dass die VM jedes Mal die GC-Aufrufe ausgibt, wird deutlich, dass die Initialisierung der größeren Arrays doch nicht so reibungslos abläuft. Interessant ist, dass der GC die Objekte nach Typ gruppiert. Er scheint eine gewisse Ordnungsliebe zu haben. Aber diese leichte Unordnung führt dazu, dass das Prefetching ab und zu fehlschlägt. Die wichtige Lektion ist, dass in Java Objekte im Speicher verschoben werden können. Wenn zwei Objekte nacheinander alloziert werden und initial im gleichen Speicherbereich landen, können sie trotzdem irgendwann an völlig unterschiedlichen Speicherstellen enden. Aber es wird noch verrückter, deshalb schauen wir uns die nächsten Graphen an ...
random
Der Test zu dem "random"-Graph funktioniert genauso wie der "simple" Test, nur dass bei der Initialisierung die Objekte an zufälligen Stellen im Array eingefügt werden. Diesmal wurde vermieden, dass der GC die Objekte anfasst, indem schon beim Start genug Speicher zur Verfügung stand und ein expliziter GC-Aufruf den Speicher vor der Initialisierung aufräumt. Danach erhält man dasselbe Verhalten wie beim zufälligen Zugriff auf das float-Array, die Performanz bricht schnell und heftig ein. Aber was passiert, wenn ein GC-Aufruf nach der Initialisierung aufgerufen wird?
Nanu - es ist schneller? Woher weiß Java, dass wir das Array linear abarbeiten? Wenn man jetzt wieder die Adressen der Objekte ausgibt, stellt man fest, dass sie auf einmal nach dem Array-Index sortiert sind. Es muss daran liegen, wie Java seine young/old-generation-Speicherbereiche organisiert. Laut Oracle bewegt der GC Objekte von young nach old, indem er von Objekten ausgeht, die bereits im Old-Speicherbereich sind. Anscheinend befindet sich das Array schon im old-Bereich (weil es zuerst alloziert wurde), danach iteriert der GC über alle Array-Elemente (die in Java Zeiger auf weitere Objekte sind), verschiebt diese gefundenen Objekte in den old-Bereich und sortiert sie damit implizit (und gruppiert sie nach dem Typ). Kann man sich darauf verlassen oder den Vorgang vielleicht geschickt provozieren? Natürlich nicht, allein schon die Unterschiede zwischen den Java-VM würden das erschweren.
array backend
Wie kann man jetzt trotzdem optimieren, ohne auf obskure Tricks zurückzugreifen? Java NIO, alles in ein Objekt oder komplett anders? Im ersten Teil war der Zugriff auf ein float-Array ziemlich schnell und skalierte gut. Warum also nicht eine Facade zu ein paar float-Arrays? Damit hätten wir immer noch die Objektorientierung und hoffentlich den schnellen Zugriff.public class PositionA {
private final PosArrays arrays; // structure with 3 arrays
private final int pos;
PositionA(PosArrays arrays, int pos) { ... }
public float getX() { return arrays.xp[pos]; }
public float getY() { return arrays.yp[pos]; }
public float getZ() { return arrays.zp[pos]; }
public void setX(final float x) { arrays.xp[pos] = x; }
public void setY(final float y) { arrays.yp[pos] = y; }
public void setZ(final float z) { arrays.zp[pos] = z; }
}
In diesem Fall speichern wir alle float-Arrays im Objekt PosArrays. Die Position- und Movement-Klasse bekommen je eine Referenz zu den Arrays, sowie zu der Position in Arrays (vergleichbar mit einer ID).
Der Graph "array backend" zeigt das Ergebnis: fast dieselbe Laufzeit über den ganzen Test. Eine minimale Verschlechterung der Performanz ist zwar auch hier zu beobachten, doch diese ist gegenüber der schlechten Gesamtperformanz zu vernachlässigen. Der Grund für die schlechte Gesamtperformanz ist, dass die Speicherbereiche der einzelnen Komponenten an völlig unterschiedlichen Stellen liegen. Davor konnte mit etwas Glück ein Position-und-Movement-Objekt in einer Cacheline Platz finden, jetzt aber müssen acht Arrays (ArrayList<PositionA>, ArrayList<MovementA>, sowie die sechs Koordinatenkomponenten) und zwei Facade-Objekte vom Speicher/Cache zur CPU transferiert werden, bevor die eigentliche Operation stattfinden kann.
direct arrays
Also weg mit den Verwaltungsstrukturen und nur die Koordinaten-Arrays verwenden? Der Graph "direct arrays" führt die Operationen direkt auf den float-Arrays durch und voilà, der Test hat dieselbe Performanz wie unser erster Ansatz ("simple") und übertrifft diesen bei großen Arrays. Die Objektorientierung ist zwar jetzt weg, aber wir haben wohl die ideale Lösung gefunden. Oder?random arrays
Was passiert, wenn wieder zufällig auf die Arrays zugegriffen wird? Es geht drunter und drüber. Schon bei kleinen Arraygrößen verschlechtert sich die Performanz und bricht dann massiv ein, wie im Graphen "random arrays" zu sehen ist. Statt ein oder zwei cache miss es bei den Objekten erhalten wir auf einmal maximal sechs davon. Das bringt den Prefetch-Algorithmus der CPU komplett aus dem Tritt. Die Datenlokalität spielt hier eine sehr große Rolle, und in diesem Fall ist die Verwendung von Objekten erst einmal die beste Lösung.Im nächsten Teil wird es um parallele Threads und Speicherzugriffe gehen.
