Java vs. RUST: Ein Performancevergleich

Wie löst man am einfachsten einen Flame-War aus? Man nehme zwei Sprachen und vergleiche sie auf Basis einer Eigenschaft. Ich habe mehr als 20 Jahre meines Berufslebens mit Java verbracht, jetzt schaue ich mir Rust an und dachte mir: Warum nicht mal die Performance vergleichen? Rust soll ja so schnell wie C sein, wobei ich auch schon gelesen habe, dass der Just in Time Compiler von Java so gut wie der C-Compiler ist. Sind sie also alle drei gleich schnell? In diesem Blog-Post lasse ich C aus und vergleiche nur Java und Rust.

Warum mache ich das überhaupt und lerne nach langer Zeit eine neue Sprache? An der Universität habe ich C genutzt. Für die Entwicklung von Betriebssystemen war das einfach die Sprache der Wahl. Auch in den Jahren danach habe ich C immer noch für die beste Sprache für diese Aufgabe gehalten. Mit dem Aufkommen von Rust bin ich mit dieser Aussage vorsichtig geworden: Ich kenne die Nachteile von C aus eigener Erfahrung nur zu gut. Arrays ohne Bereichskontrolle und manuelle Speicherverwaltung (teilweise mit Referenz-Zählern) lassen einen die militärischen Dienstgrade des Linux-Kernels kennerlenen: "Kernel panic", "Major failure" und "General protection fault".

Die Vorstellung, Business-Anwendungen mit C zu schreiben, löst bei mir nur Gruselgefühle aus. Da kommt es meistens nicht auf die letzte Nanosekunde im eigenen Code an, eher darauf, dass man sinnvoll mit der Datenbank, Frameworks oder REST-Schnittstellen umgeht. Da habe ich Java lange Zeit für eine sehr gute Wahl gehalten: Strickte Memory-Checks, Garbage Collection und eine Unzahl von verfügbaren Bibliotheken machen einem das Leben dort einfach.

Daher galt lange Zeit für mich: C für Betriebssysteme oder Microcontroller, Java für Business Anwendungen. Und dann kommt Rust um die Ecke: Die Sicherheit von Java kombiniert mit Eigenschaften, die eine Performance ähnlich wie in C versprechen. Damit erscheint Rust auch für low-level-Programmierung geeignet. Diese Argumente führen dazu, dass Rust inzwischen auch im Linux-Kernel einzieht.

Da man Benchmarks (wie Statistiken) nur glauben kann, wenn man sie selbst gefälscht hat, habe ich mich hingesetzt und ein kleines (sehr altes) Java-Programm von mir in Rust neu implementiert.

Bei Benchmarks muss man beachten, was man wirklich misst. Was ist ein guter Vergleich? Man könnte beispielsweise ein ERP-System zu Vergleichszwecken doppelt implementieren (Java + Rust) und dann die beiden Versionen vergleichen. Ist ziemlich teuer und liefert Zahlen. Aber welche? Am Ende vergleicht man hier vermutlich eher die Implementierungen der verwendeten Bibliotheken als die der Sprache an sich. Ist das falsch? Wenn es um den Vergleich der Ökosysteme und nicht nur des Sprachkerns geht sicher nicht. Man könnte dann auch vergleichen, wie viel Zeit die Teams jeweils für die Implementierung benötigen. Das Ergebnis ist natürlich nur valide, wenn die Teams in ihrem jeweiligen Ökosystem gleich gut sind. Die notwendigen Ressourcen habe ich nicht, so habe ich es bei einem einfachen Vergleich belassen, der nur den Sprachkern und kleine Teile der Standardbibliothek nutzt.

Ich habe mich nach Benchmarks umgeschaut, eine Liste von kleinen, algorithmischen Benchmarks findet man zum Beispiel auf der Seite Programming Language and compiler Benchmarks. Warum hat mich das nicht zufrieden gestellt? Bei einigen Benchmarks ist der Java und Rust Code strukturell deutlich unterschiedlich, so dass mir die Vergleichbarkeit fehlt. Außerdem fehlt mir die Analyse, warum die eine oder andere Variante schneller ist. Ein anderer Benchmark - Java vs Rust: How faster is machine code compared to byte code for JWT sign & verify? - vergleicht aus meiner Sicht nur die verwendeten Bibliotheken.

Die Aufgabe

Die für den Vergleich genutzte Aufgabe und das zugehörige Java-Programm habe ich vor Jahren in einem Blog-Post beschrieben: Fork/Join und andere Optimierungen von Algorithmen. Damals habe ich verschiedene Parallelisierungsstrategien verglichen, in diesem Blog-Post vergleiche ich nur sequentielle Varianten. Umgebung war jeweils mein Laptop unter Windows.

Was ist die Aufgabe? Es geht darum, die Anzahl der möglichen Lösungen für eine dreieckige Solitär, auch Toblerone-Puzzle genannt, zu ermitteln. Das Brett hat die Kantenlänge n, in der dritten Reihe von oben befindet sich in der Mitte ein freies Feld, alle anderen Felder sind mit Steinen belegt. Ein Stein darf über einen anderen Stein springen, der dann entfernt wird. Das Spiel ist gelöst, wenn nur noch ein Stein - egal wo - übrig ist.

Hier eine Startkonfiguration für ein Spielfeld der Größe fünf:

      x 
     x x
    x o x
   x x x x
  x x x x x

Die Anzahl der Steine auf dem Spielfeld steigt quadratisch mit der Kantenlänge, der Berechnungsaufwand exponentiell mit der Anzahl der Steine. Kombiniert ergibt das O(2 hoch (n*n)). Für die Größe der ersten Spielfelder ergibt sich:

Kantenlänge	Anzahl Felder
5	15
6	21
7	28
8	36
9	45

Spielfelder mit einer Kantenlänge kleiner oder gleich sieben lassen sich in einer 32 Bit Ganzzahl speichern, anschließend benötigt man eine 64 Bit Zahl, um das Feld zu speichern. Man kann übrigens beweisen, dass sich jede dritte Spielfeldgröße nicht lösen lässt: 4, 7, 10, 13 und so weiter. Einen Beweis dazu habe ich am Ende meines alten Blog-Posts aufgeschrieben.

Der Kern des Algorithmus besteht aus einer Tiefensuche mit Cache, damit gleiche Stellungen nicht mehrfach ausgewertet werden. Hier die Java-Version:

1long countSolutions(long[] cache, Board start) {
2    int asInt = start.asInteger();
3    if (cache[asInt] != -1) {
4        return cache[asInt];
5    } else if (start.isSolution()) {
6        cache[asInt] = 1;
7        return 1;
8    } else {
9        long count = 0;
10        List<Board> nextBoards = start.nextBoards();
11        for (Board board : nextBoards) {
12            count += countSolutions(cache, board);
13        }
14        cache[asInt] = count;
15        return count;
16    }
17}

Bei Board handelt es sich um ein Interface, hinter dem - je nach Feldgröße - ein int oder long verbirgt. Diese konkrete Methode countSolutions() funktioniert allerdings nur mit Feldern bis Kantenlänge sieben, da das Feld in seiner Bit-Darstellung direkt als Array-Index für den Cache verwendet wird. Für größere Spielfelder benötigt man eine andere Cache-Implementierung. Die Größe des Caches beträgt für n=7übrigens zwei Gigabyte. Für den alten Blog-Artikel hatte ich auch versucht, die Anzahl der Lösungen für Kantenlänge acht zu ermitteln. Spoiler: Es ist mir nicht gelungen.

Die Werte im Array stehen für die Anzahl der Lösungen der zugehörigen Stellung, -1 für "noch nicht untersucht". Also kann jeder Wert ungleich -1 direkt ohne weitere Berechnung zurückgegeben werden. Handelt es sich um eine "gelöste Stellung" (nur noch ein Stein auf dem Feld), gibt die Methode 1 zurück. Ansonsten beginnt die Arbeit: Liste der Nachfolgefelder erzeugen, die mit einem Zug erreichbar sind, für alle die Anzahl von Lösungen (rekursiv) ermitteln, addieren, im Cache eintragen und zurückgeben. Wer den Code der restlichen Methoden sehen möchte, kann im Github-Repository nachschauen. Dort befinden sich verschiedene Java- und Rust-Varianten in einem Repository. Sowohl für Java als auch für Rust existiert eine Funktion, mit der sich die Anzahl der gesetzten Bits in einer Ganzzahl zählen lässt. Vermutlich basieren sie auf dem gleichen Assemblerbefehl, selbst muss man keine Bitfummelei dazu implementieren.

In Rust sieht der Kern des Algorithmus sehr ähnlich aus:

1fn count_solutions(mut cache: &mut[i64], board: Box<dyn Board>) -> i64 {
2    let index = board.as_usize();
3    if cache[index] != -1 {
4        cache[index]
5    } else if board.is_solution() {
6        cache[index] = 1;
7        1
8    } else {
9        let mut count: i64 = 0;
10        let next_boards = board.next_boards();
11        for board in next_boards {
12            count += count_solutions(cache, board)
13        }
14        cache[index] = count;
15        count
16    }
17}

Der Cache besteht hier aus einem Vec, an die Methode wird eine mutable Slice-Sicht daraus übergeben. Die Lösung entspricht einem Array in Java. Das Spielfeld, in Java durch ein Interface repräsentiert, ist hier ein Trait mit zwei Implementierungen: Für kleine Felder 32 Bit, für größere 64 Bit. An die Stelle der ArrayList mit den Folgestellungen tritt hier ein Vec, auch hier kaum Unterschiede zwischen den beiden Sprachen.

Performance

Welche Laufzeit ergibt sich für die beiden Implementierungen, wenn man ein Spiel mit Kantenlänge sieben spielt? Das Ergebnis überrascht auf den ersten Blick:

• Java 21, 20 s
• Rust, debug version: 111 s
• Rust, release version: 36 s

In Java habe ich den Code sicherheitshalber in einer Schleife zwei mal laufen lassen, damit der JIT sich warmlaufen kann. Die Unterschiede sind aber marginal, die JIT-Zeiten für die wenigen, kleinen Methoden fallen offensichtlich kaum ins Gewicht. Bei Rust muss man natürlich darauf achten, die Release-Version mit eingeschaltetem Optimizer zu nutzen. Die spannende Frage: Warum ist Rust trotz Optimizer langsamer als Java? Der Grund liegt im Trait und den Möglichkeiten eines JIT Compilers versus eines ahead of time Compilers: Der Rust Optimizer kann sich nur auf statische Informationen stützen, die zur Compile-Zeit vorliegen. Der Java JIT Compiler sieht jedoch die aktuell vorliegenden Daten: Er kann auf das kleine Feld (mit 32 Bit) optimieren und muss beim Methodenaufruf keinen dynamischen Dispatch durchführen. Da bis zur Kantenlänge sieben sowieso nur das Feld mit 32 Bit notwendig ist, habe ich eine zweite Version des Rust Codes geschrieben, direkt mit einer struct, ohne Trait. Die Signatur der Funktion ändert sich dadurch, der Rumpf bleibt syntaktisch gleich (wird aber natürlich zu anderem Assemblercode übersetzt):

1fn count_solutions(cache: &mut[i64], board: SmallBoard) -> i64 {

• Rust, debug version: 81 s
• Rust, release version: 17 s

Mit dieser Version ist Rust schneller als Java, ca 15 %. Keine Größenordnung, aber immerhin. Was lernen wir daraus?

1. Rust rühmt sich für die vielen zero cost abstractions, die zwar dem Compiler Arbeit machen, dafür zur Laufzeit keine Kosten erzeugen. Der Aufruf von trait associated functions gehört nicht dazu: Hier muss ein dynamischer Dispatch erfolgen, der einen Lookup im Speicher erforderlich macht. Ich vermute, dass dadurch auch die Sprungvorhersage von modernen Prozessoren ausgehebelt wird.
2. Der JIT Compiler von Java erzeugt sehr effizienten Code, bei Berücksichtigung von Laufzeitinformationen manchmal sogar schnelleren Code als der Rust-Compiler.
3. ArrayList in Java und Vec sind zwar ähnlich, aber nicht gleich: Java speichert in dem dahinterliegenden Array nur Referenzen, Rust die Objekte selbst. Java hat dadurch beim Skalieren Vorteile (nur Referenzen kopieren, keine Inhalte), Rust beim Zugriff: Die Indirektion über die die Referenz entfällt.

Was ich nicht gemessen habe sind die Startup-Zeiten der beiden Versionen. Bei dieser Größe sind sie für beide zu vernachlässigen. Wer mit großen Java-Anwendungen mit vielen Bibliotheken arbeitet, weiß aber, dass der Start relevant Zeit benötigt. Egal ob fat jar oder einzelne jars: Es muss viel Bytecode geladen und dann durch den JIT verarbeitet werden. Überschläglich gemessen habe ich den Ressourcenverbrauch der beiden Versionen.

Für Rust habe ich übrigens noch eine dritte Version implementiert, die komplett auf struct und assoziierte Methoden verzichtet. Weiterhin ist der Vec für die aus einer Stellung ermittelten Nachfolgestellungen durch ein Array fester Größer ersetzt, das komplett auf dem Stack liegt. Das ist möglich, da es bei einem Spielfeld mit 32 Feldern nie mehr als 32 Züge aus einer Stellung geben kann. Die Aufrufe für eine dynamische Speicherverwaltung (malloc(), free()), die Vec im Hintergrund durchführt, fallen somit weg. Die Zeit sinkt damit von 17 s auf 12 s. Der zugehörige Code ist aber so hässlich, dass ich ihn hier nicht zeigen möchte. Im git Repository steht er im Verzeichnis array_solver_with_cache.

Ressourcenverbrauch

Lässt man Java ohne -Xmx Parameter laufen, liegt der Speicherverbrauch bei ca. 3.380 MByte (Erinnerung: 2 GByte werden für den Cache verbraucht). Ein Blick in den Task-Manager (ich arbeite mit Windows) zeigt, dass während der Laufzeit meistens nur einer der CPU-Kerne beschäftigt ist. Der "Kleinkram" - die Felder - lebt offensichtlich kurz genug, so dass der Garbage Collector mit genügend Reserve im Heap recht schnell ist. Anders sieht es aus, wenn man den Heap per -Xmx2053m auf den Wert verkleinert, der für den Cache und den Kleinkram notwendig ist. Der Gesamtspeicherverbrauch liegt dann bei ca. 2.117 MByte, das heißt, ca. 64 MByte benötigt die JVM zusätzlich zum Heap. Die Laufzeit steigt auf 53 s, mehr als das Doppelte. Im Task Manager sieht man, dass der Garbage Collector die restlichen Kerne auch in Beschlag nimmt.

Bei Rust gibt man keine Heap-Größe an, die Laufzeit nimmt sich, was angefordert wird. Laut Task-Manager benötigt die Anwendung 2048,4 MByte, zusätzlich zum Cache also nur 400 KByte, deutlich weniger als die 64MByte der Java-Variante.

Die Erkenntnis aus diesen Beobachtungen: Java ist in diesem Benchmark geringfügig langsamer als Rust, benötigt dafür aber deutlich mehr Ressourcen: Speicher und/oder CPU. Wenn man nur einen Benchmark ausführt und der eigene Laptop sich ansonsten langweilt ist es relativ egal, in der Praxis für größere Anwendungen gilt dies jedoch nicht: CPU und Speicher müssen bezahlt werden, sowohl im lokalen Rechenzentrum als auch in der Cloud. Startup-Zeiten sind ebenso relevant, wenn nicht ein Service mit konstanter Last lange läuft, sondern die Anwendung on demand skaliert wird oder als Lambda läuft: Instanzen sollten dann schnell verfügbar sein.

Fazit

Was nehme ich aus den Messungen für mich mit? Ob man - wie Rust - direkt Maschinencode erzeugt oder - wie Java - zweistufig vorgeht (Bytecode, Maschinencode) hat beides Vor- und Nachteile: Ein JIT kann die aktuellen Daten berücksichtigen, benötigt jedoch zusätzliche Ressourcen zur Laufzeit. Für lang laufende Server-Anwendungen mit vielen Threads und viel RAM für Daten fällt dies unter Umständen nicht stark ins Gewicht. Benötigt man jedoch kleine Server mit schneller Startup-Zeit für flexible Skalierung, macht sich dieser Overhead stärker bemerkbar, hier hat Rust klare Vorteile. Bei der Generierung des Titelbildes lag die KI mit einem fetten Java-Maskottchen da richtig (nein, dass habe ich nicht im Prompt so angefordert).

Gegenüber Java ist das gesamte Rust-Ökosystem noch recht jung. Das hat Nachteile (weniger Frameworks, weniger Erfahrung in der Entwicklercommunity), aber auch Vorteile: Rust konnte aus vielen "Fehlern" lernen, die bei der Entwicklung von Java und anderen Sprachen in den letzten Jahrzehnten gemacht wurden. Für mich ist klar, dass ich mich weiter mit Rust beschäftigen werde: Auf der einen Seite für Services, die in der Cloud auf kleinen Servern skalierbar laufen sollen, auf der anderen Seite für Spielprojekte auf Microcontrollern.