Java Performanz und der CPU Cache

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. Für Java-Entwickler sind diesbezügliche Optimierungen des eigenen Programmcodes allerdings nur selten zielführend.

Alle Informationen in diesem Artikel sind im Prinzip sprachunabhängig und gelten für alle Programmiersprachen. Die meisten Beispiele sind allerdings in C/C++ geschrieben und nicht 1:1 auf Java übertragbar. In diesem Artikel gehen wir der Frage nach, in welchen Fällen Java Programme von dem CPU-Cache profitieren können. 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. Durch die Virtual Machine können unter der Haube Laufzeitoptimierungen durchgeführt werden, die mit einer kompilierten Sprache wie C++ nicht möglich sind. Gerade diese können allerdings alle Optimierungsversuche zunichte machen.

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 bzw. implementierte Algorithmen zurück als auf einen nicht genutzten 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 aber 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 aber 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ängern 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 verschiedene 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 explizite 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.

Object cs. Primitive Type

 1    long sum = 0L;
 2    for(int i = 0; i < size; i++) {
 3        sum++;
 4    }
 5
 6    >> Zeit: 0.013913 s
 7
 8    Long sum = 0L;
 9    for(int i = 0; i < size; i++) {
10        sum++;
11    }
12
13    >> Zeit 2.162704 s

Es gibt eine ganze Reihe von Webseiten, die sich mit Performanz beschäftigen und auch Frameworks, die Performanztests vereinfachen.

Array-Zugriffe

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 meinem Beispiel 100.000.000). Der zweite Test greift nicht sequenziell zu, sondern verwendet ein Zufallsmuster, das in einem zweiten Array mit gleicher Größe abgelegt wird.

Array Access

 1    public static Long testOffsetArrayAccess(int maxAccess, int size,
 2                                             float[] array) {
 3        float sum = 0;
 4        int andSize = size - 1;
 5        for (int i = 0; i < maxAccess; i++) {
 6            int pos = i & andSize;
 7            sum += array[pos];
 8        }
 9        return (long) sum;
10    }
11
12    public static Long testRandArrayAccess(int maxAccess, int size,
13                                        float[] array, int[] rand) {
14        float sum = 0;
15        int andSize = size - 1;
16        for (int i = 0; i < maxAccess; i++) {
17            int pos = rand[i & andSize];
18            sum += array[pos];
19        }
20        return (long) sum;
21    }

Die gemessenen Zeiten sind in folgendem Graphen dargestellt.

Der Graph offenbart einige interessante Details:

• Die minimale Zeit für einen Zugriff ist in diesem Beispiel 0,9 ns.
• Ein ähnlicher Test in C ergab die gleiche Zugriffszeit von etwa 0,9 ns, 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 exakt den L1/L2-Cache-Größen entspricht. Die grünen Linien stellen die Cache-Grenzen dar.

Nebenbemerkung: Der gleiche Test wurde auch in C durchgeführt wobei der vom GCC erzeugte Code dreimal so schnell ist, wie der Java Code. 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 erzeugt.

Wie in C/C++ kann auch in Java der Einfluss des CPU-Caches bei Arrays gezeigt werden. Was passiert aber, wenn Objekte verwendet werden?

Objekt-Zugriffe

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 Objekt-Arrays 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 des Testlaufs werden keine Objekte erzeugt oder zerstört.

Der erste Test ist recht einfach:

Object Access

 1    public static Long testSerialECSAccess(int maxAccess, int size,
 2                                         ArrayList<Position> positions,
 3                                           ArrayList<Movement> movements) {
 4        int andSize = size - 1;
 5        for (int i = 0; i < maxAccess; i++) {
 6            int pos = i & andSize;
 7            Position position = positions.get(pos);
 8            Movement movement = movements.get(pos);
 9            position.x += movement.x;
10            position.y += movement.y;
11            position.z += movement.z;
12        }
13        return 0L;
14    }

Das Ergebnis ist im Graphen als “simple” gekennzeichnet.

Wieder ändert sich die Array-Größ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 der 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:

Memory Adresses

1    ArrayList<Position> positions = new ArrayList<>(10000);
2    ArrayList<Movement> movements = new ArrayList<>(10000);
3    for (int i = 0; i < 10000; i++) {
4        positions.add(new Position());
5        movements.add(new Movement());
6    }

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 Gargabe Collectors (GC) per System.gc() erhält man immer diese Anordnung. Was ist also passiert?

Es ist ein Fehler im Test Setup. Die Virtual Machine 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 also 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…

Zufällige Zugriffe

Dieser Test funktioniert im Prinzip wie der vorherige, 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 der GC 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 die gefundenen Objekte in den Old-Bereich und sortiert sie damit implizit (und gruppiert sie zusätzlich nach dem Typ). Kann man sich darauf verlassen oder den Vorgang vielleicht geschickt provozieren? Natürlich nicht, allein schon die Unterschiede zwischen den verschiedenen Java-VMs würden das erschweren.

Primitive Array Backend

Wie kann man jetzt trotzdem optimieren, ohne auf obskure Tricks zurückzugreifen, die Wissen über VM-interne Vorgänge erfordern? 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.

 1    public class PositionA {
 2        private final PosArrays arrays; // structure with 3 arrays
 3        private final int pos;
 4        PositionA(PosArrays arrays, int pos) { ... }
 5        public float getX() { return arrays.xp[pos]; }
 6        public float getY() { return arrays.yp[pos]; }
 7        public float getZ() { return arrays.zp[pos]; }
 8        public void setX(final float x) { arrays.xp[pos] = x; }
 9        public void setY(final float y) { arrays.yp[pos] = y; }
10        public void setZ(final float z) { arrays.zp[pos] = z; }
11    }

In diesem Fall speichern wir alle float-Arrays im Objekt PosArrays. Die Position- und Movement-Klassen bekommen je eine Referenz zu den Arrays, sowie zu der Position in den 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. Zuvor 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 sogar! Die Objektorientierung ist jetzt zwar 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 Array-Größen verschlechtert sich die Performanz und bricht dann massiv ein, wie im Graphen “random arrays” zu sehen ist. Statt ein oder zwei Cache Misses 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.