1BRC – Die ersten 80% Performance

Die One Billion Row Challenge (1BRC) startete als Projekt über den Jahreswechsel 2023/2024 und widmete sich einer vermeintlich einfachen Fragestellung: Wie schnell können Temperaturmesswerte aus einer Textdatei mittels Java verarbeitet werden, um Minimum-, Durchschnitts- und Maximumwerte pro Wetterstation zu berechnen? Die Herausforderung ergibt sich dabei aus dem Umfang des Datensatzes, der mit einer Milliarde Zeilen eine Gesamtgröße von etwa 13,8 GB umfasst.

Thomas Wuerthinger, Quan Anh Mai und Alfonso Peterssen erzielten mit 1,5 Sekunden auf 8 Cores das Spitzenresultat. Diese Performance war in diesem Ausmaß unerwartet. Bei einer detaillierten Analyse des Quellcodes wird jedoch ersichtlich, dass die Implementierung weit über die übliche Java-Entwicklung hinausgeht. Es handelt sich um eine hochkomplexe, auf diesen spezifischen Use-Case zugeschnittene Lösung, deren Optimierungen größtenteils nicht ohne Weiteres auf andere Szenarien übertragbar sind.

In diesem Artikel wird aufgezeigt, wie 80 % des Ergebnisses mit deutlich einfacherem und wartungsfreundlicherem Code erzielt werden können. Um die Komplexität gering zu halten, wird sich dabei auf einen Single-Threaded-Ansatz konzentriert. Die meisten der vorgestellten Konzepte lassen sich problemlos in eigenen Projekten anwenden. Dennoch werden gezielt Entscheidungen getroffen, die unter strengen Clean-Code-Gesichtspunkten als fragwürdig eingestuft werden könnten.

Die Herausforderung

Ende 2023 entstand aus einer Initiative von Gunnar Morling die Idee, das Einlesen von einer Milliarde Zeilen aus einer CSV-Datei unter maximalen Performance-Aspekten zu untersuchen. Da Performance-Herausforderungen erfahrungsgemäß effizient durch die Community gelöst werden, wurde daraus ein Wettbewerb entwickelt. Ziel war es zu ermitteln, welche Geschwindigkeiten moderner Java-Code durch kollektive Optimierung erreichen kann.

Es gilt, eine Datei mit einer Milliarde Zeilen zu verarbeiten, wobei jede Zeile den Namen einer Wetterstation sowie einen zugehörigen Temperaturwert enthält. Das Ziel besteht darin, die Minimum-, Durchschnitts- und Maximumwerte pro Wetterstation mit maximaler Geschwindigkeit zu berechnen.

Zagreb;19.7
Tromsø;-3.9
Gangtok;-1.7
Houston;32.4
Zürich;13.8

Aus reiner Bequemlichkeit entschied sich Gunnar für TreeMap::toString als Ausgabeformat. Alle Zahlen sind ordnungsgemäß gerundet und auf eine Dezimalstelle formatiert. Der finale Output sollte wie folgt aussehen:

# This is TreeMap::toString
# Data shown here is formatted for screen
{
   Abha=5.0/18.0/27.4, Abidjan=15.7/26.0/34.1,
   Abéché=12.1/29.4/35.6, Accra=14.7/26.4/33.1,
   Addis Ababa=2.1/16.0/24.3, Adelaide=4.1/17.3/29.7,
   ...
   Willemstad=-7.9,28.2,57.7, Winnipeg=-28.1,3.0,39.4,
   Wrocław=-27.5,9.6,50.2, Xi'an=-22.5,14.0,49.1,
   Yakutsk=-42.2,-8.8,26.4, Yangon=-2.6,27.6,59.0,
   Yaoundé=-10.1,23.6,58.3, Yellowknife=-38.4,-4.0,40.0,
   Yerevan=-18.4,12.4,49.6, Yinchuan=-25.4,9.5,42.0,
   Zagreb=-25.3,10.6,48.4, Zanzibar City=-5.0,26.1,61.2,
   Zürich=-20.9,9.4,43.5, Ürümqi=-26.8,7.4,43.7,
   İzmir=-15.8,18.0,50.1
}

Folgende Anforderungen müssen beachtet werden:

Die Anzahl der Stationen ist auf maximal 10.000 begrenzt, wobei die Basisversion der Datei lediglich 413 Stationen umfasst. Als Zeilentrenner wird ausschließlich \n verwendet. Sämtliche Temperaturwerte liegen im Bereich von -99.9 bis 99.9 und sind konsistent mit einer Dezimalstelle formatiert. Die maximale Länge eines Stationsnamens beträgt 100 Bytes.

Für den offiziellen Wettbewerb konnten bis zu 8 CPU-Cores genutzt werden. Da die Messung fünfmal durchgeführt und der Durchschnitt der drei besten Versuche ermittelt wurde, befand sich die Datei im File Cache. Für die hier angestrebte Lösung ist dieser Aspekt jedoch nicht entscheidend.

Nachfolgend werden die Messergebnisse aufgeführt. Es handelt sich hierbei um eigene Messungen und nicht um die offiziellen Wettbewerbsergebnisse. Zur Erinnerung: Um die Komplexität gering zu halten, wird vorerst auf Multi-Threading verzichtet. Die von Gunnar Morling vorgeschlagene Baseline basiert auf einer einfachen Implementierung mittels Java Streams.

Wichtig: Alle Zahlen in den Tabellen sind en_US formatiert, also 1,112.72 statt de_DE 1.112,72. Es hat die Übersetzung aus dem englischen Original erleichtert.

Die Ergebnisse

1. Digital Ocean, Amsterdam, Dedicated Machine, Intel CPU-optimized, 16 core, 32 GB, Jan 2025
2. Hetzner, Finnland, Dedicated Machine, AMD, 8 core, 32 GB, Jan 2025

Man kann schon unser für heute Ziel sehen. Wir wollen 5x schneller werden und damit am Ende bei 20% der originalen Laufzeit herauskommen. Wir sind dann also 80% schneller. Zwar stellt das keinen Rekordwert dar, doch der Großteil der angewandten Optimierungs- und Profiling-Methoden lässt sich direkt auf die eigene tägliche Entwicklungsarbeit übertragen.

Aber bitte nicht blindlings sämtliche Änderungen auf den eigenen Code anzuwenden. Die technische Machbarkeit rechtfertigt nicht automatisch die Umsetzung; sauberer und wartbarer Code behält stets Priorität.

Sämtliche Laufzeitdaten wurden auf 8-Core-Cloud-Instanzen bei Hetzner (AMD-CPUs) und Digital Ocean (Intel-CPUs) gemessen. Da Ergebnisse je nach Hardware und Setup variieren, sind exakte Reproduktionen der Zahlen oft schwierig. Für ein belastbares Bild der Laufzeiten ist daher immer die Betrachtung einer gesamten Messserie erforderlich.

Die Gewinnerlösung nutzt Unsafe, GraalVM Native Builds, komplexe Bit-Manipulation und weitere Techniken, die im regulären Entwicklungsalltag wenig Anwendung finden. Dies ist zwar technisch beeindruckend, jedoch nur begrenzt in die Praxis übertragbar – mit Ausnahme von GraalVM Native Images.

Wer tiefer in die finale Lösung eintauchen möchte, sollte sich insbesondere mit dem Branchless Parsing (auch bekannt als SWAR – SIMD Within A Register) auseinandersetzen, da dies im Vergleich zu anderen Ansätzen sowie der heute vorgestellten Lösung den wesentlichen Performance-Unterschied macht.

Unser Ziel: 80 % schneller

Das Ziel besteht nicht darin, die Geschwindigkeit der Gewinnerlösung zu erreichen – welche etwa 9 Sekunden in einem Single-Thread benötigt –, sondern etwa ein Fünftel der ursprünglichen Laufzeit zu erzielen und damit eine Einsparung von 80 % zu realisieren.

Der vollständige Quellcode ist unter https://github.com/rschwietzke/1brc-the-first-80-meters einsehbar. Im Folgenden wird entweder direkt auf die jeweilige Implementierung verlinkt oder lediglich der Klassenname angeführt.

Ein kurzer Exkurs zum methodischen Vorgehen: Da das ursprüngliche 1BRC auf einzelnen Java-Dateien basiert, die mehrfach ausgeführt werden, wurde zur Vereinfachung der Messungen ein Framework entwickelt. Dieses ermöglicht eine präzise Ausführung jeder Lösung inklusive Warm-up, Checksum-Validierung und Batch-Verarbeitung, was zudem tiefere Einblicke in die JIT-Kompilierung von Java erlaubt.

0 – Die Ausgangslage

Die Baseline bildet die ursprüngliche Lösung von Gunnar Morling. Diese basiert auf einer Stream-Implementierung, welche Standard-Java-Features wie collecting und groupingBy nutzt. Die detaillierte Interpretation dieses Ansatzes wird übersprungen, da hierzu bereits zahlreiche Artikel existieren.

Sowohl dieser als auch alle folgenden Code-Ausschnitte wurden für diesen Artikel modifiziert. Den vollständigen Quellcode findet man auf GitHub.

Collector<Measurement, MeasurementAggregator, ResultRow> collector =
        Collector.of(MeasurementAggregator::new,
        (agg, m) -> {
            agg.min = Math.min(agg.min, m.value);
            agg.max = Math.max(agg.max, m.value);
            agg.sum += m.value;
            agg.count++;
        }, (agg1, agg2) -> {
            var res = new MeasurementAggregator();
            res.min = Math.min(agg1.min, agg2.min);
            res.max = Math.max(agg1.max, agg2.max);
            res.sum = agg1.sum + agg2.sum;
            res.count = agg1.count + agg2.count;

            return res;
        }, agg -> {
            return new ResultRow(agg.min, (Math.round(agg.sum * 10.0) / 10.0) / agg.count, agg.max);
        });

// Measurement is a record
// MeasurementAggregator is a regular data class
// ResultRow is a class that can print to the proper output format
var result = Files.lines(Paths.get(fileName))
        .map(l -> l.split(";"))
        .map(l -> new Measurement(l))
        .collect(groupingBy(m -> m.station(), collector));

return new TreeMap<>(result).toString();

Der obige Code weist eine beträchtliche Laufzeit auf, doch die genauen Hotspots der Ausführung sind zunächst unbekannt. Um gezielte Optimierungen vorzunehmen und Vermutungen zu vermeiden, ist eine fundierte Analyse erforderlich. Hierfür bietet sich der AsyncProfiler an – eines der vielseitigsten und leistungsstärksten Open-Source-Werkzeuge für das Profiling von Java-Anwendungen.

Mittels der entsprechenden Kommandozeile lässt sich ein Flamegraph erstellen, der eine interaktive Untersuchung der Performance-Engpässe ermöglicht.

java
    - agentpath:libasyncProfiler.so=start,event=cpu,flamegraph,file=flamegraph.html \
    -cp target/classes/ \
    org.rschwietzke.devoxxpl24.BRC01_BaselineST measurements.txt 2 2

Dies ist der letzte Flamegraph, der in diesem Artikel gezeigt wird. Wer gern interaktiv einen Flamegraph ausprobieren möchte, der JFokus 2025 Talk “1BRC – The first 80% of the Journey” enthält jede Menge interaktive Beispiele. Für den verbleibenden Teil des Artikels nutzen wir nur eine tabellarische Übersicht.

1 – Keine Streams

Streams lassen sich nicht ohne Weiteres optimieren, weshalb diese in eine klassische Form von Java-Code überführt werden. Der gewählte Ansatz entspricht einer entrollten Stream-Operation, bei der collect und groupBy manuell implementiert werden.

final Map<String, Temperatures> cities = new HashMap<>();

try (var reader = Files.newBufferedReader(Paths.get(fileName)))
{
    String line;
    while ((line = reader.readLine()) != null)
    {
        // split the line
        final String[] cols = line.split(";");

        // get us the data to store
        final String city = cols[0];
        final double temperature = Double.parseDouble(cols[1]);

        // store and sum up the data
        // Map::merge(key, value, remappingFunction)
        cities.merge(city, new Temperatures(temperature), (t1, t2) -> t1.merge(t2));
    }
}

// ok, we got everything, now we need to order it
return new TreeMap<String, Temperatures>(cities).toString();

Ein Blick auf die Daten des Flamegraphs verdeutlicht die Verteilung: DO bezieht sich auf den DigitalOcean-Server mit Intel-Prozessor, während HE die Messwerte des AMD-basierten 8-Core-Systems bei Hetzner repräsentiert.

Durch den Verzicht auf den Stream-Code konnte eine Steigerung der Ausführungsgeschwindigkeit erzielt werden.

Wichtig: Dies bedeutet keineswegs, dass Streams grundsätzlich gemieden werden sollten. Streams stellen ein mächtiges Werkzeug dar und sind dort einzusetzen, wo sie angemessen sind. Für hochgradig performance-kritischen Code sind sie unter Umständen nicht die optimale Wahl, für die tägliche Entwicklung bieten sie jedoch enorme Vorteile.

Die Werte haben sich geringfügig verschoben, die Gesamtverteilung bleibt jedoch nahezu identisch.

2 – Split

split() beansprucht den Großteil der Laufzeit, weshalb wir unser Tuning auch damit beginnen.

Bei split() handelt es sich um eine sehr mächtige Methode, die üblicherweise reguläre Ausdrücke verwendet, um einen String zu unterteilen. Eine Analyse des JDK-Quellcodes von split() verdeutlicht, dass die Methode versucht, effizient zu agieren: Sie bietet einen sogenannten „Fastpath“ an, sofern das Trennzeichen ein einzelnes Zeichen und kein regulärer Ausdruck ist. Der JIT-Compiler (Just-In-Time) kann dies unter Umständen mittels Constant Folding optimieren. Dennoch bleibt es ein Aufruf einer umfangreicheren Methode, die Objekte instanziiert und möglicherweise nicht inlined wird – also nicht direkt in den aufrufenden Code kopiert wird, um den Overhead eines Methodensprungs zu vermeiden.

// our cities with temperatures
final Map<String, Temperatures> cities = new HashMap<>();

try (var reader = Files.newBufferedReader(Paths.get(fileName)))
{
    String line;
    while ((line = reader.readLine()) != null)
    {
        // split the line
        final int pos = line.indexOf(';'); // <--

        // get us the city
        final String city = line.substring(0, pos); // <--
        final String temperatureAsString = line.substring(pos + 1); // <--

        // parse our temperature
        final double temperature = Double.parseDouble(temperatureAsString);

        // merge the data into the captured data
        cities.merge(city, new Temperatures(temperature), (t1, t2) -> t1.merge(t2));
    }
}

// ok, we got everything, now we need to order it and print it
return new TreeMap<String, Temperatures>(cities).toString();

Das Ergebnis ist bemerkenswert: Fast ohne Aufwand haben wir 20 % gewonnen. Interessanterweise unterscheiden sich AMD- und Intel-Systeme – ein Muster, das sich im weiteren Verlauf wiederholen wird.

Dennoch sollte keineswegs jedes String::split in einer bestehenden Codebase ersetzt werden. Der Großteil des Codes ist nicht performance-kritisch, und die Verwendung von split ist oft lesbarer sowie potenziell weniger fehleranfällig.

Sollten auf der lokalen Maschine Geschwindigkeitsvorteile gemessen werden, darf nicht automatisch davon ausgegangen werden, dass diese Effekte auf einem Production-Server oder einer anderen Architektur gleichermaßen auftreten. Messungen und Profiling müssen stets in der Umgebung durchgeführt werden, in der die Optimierung letztlich wirksam sein soll.

Unser split ist in indexOf und substring aufgegangen.

3 – Double Parsing

Eine Untersuchung des Quellcodes von Double::parseDouble im JDK offenbart eine über 200 Zeilen umfassende Implementierung, die nahezu sämtliche Edge-Cases abdeckt. In unserem Szenario treten derartige Sonderfälle jedoch nicht auf. Da bekannt ist, dass die Eingabe stets einem validen Double-Wert mit genau einer Dezimalstelle entspricht, kann dieses Wissen gezielt zur Optimierung genutzt werden.

public static double parseDouble(final String s) {
    return parseDouble(s, 0, s.length() - 1);
}

private static final double[] multipliers = {
    1, 1, 0.1, 0.01, 0.001, 0.000_1, 0.000_01, 0.000_001, 0.000_000_1, 0.000_000_01,
    0.000_000_001, 0.000_000_000_1, 0.000_000_000_01, 0.000_000_000_001, 0.000_000_000_000_1,
    0.000_000_000_000_01, 0.000_000_000_000_001, 0.000_000_000_000_000_1, 0.000_000_000_000_000_01};

public static double parseDouble(final String s, final int offset, final int end) {
    final int negative = s.charAt(offset) == '-' ? offset + 1 : offset;

    long value = 0;
    int decimalPos = end;

    for (int i = negative; i <= end; i++) {
        final int d = s.charAt(i);
        if (d == '.') {
            decimalPos = i;
            continue;
        }
        final int v = d - DIGITOFFSET;
        value = ((value << 3) + (value << 1));
        value += v;
    }

    // adjust the decimal places
    value = negative != offset ? -value : value;
    return value * multipliers[end - decimalPos + 1];
}

Für die Implementierung wurde auf bereits existierenden Code aus einem anderen Projekt zurückgegriffen, der zudem die Anforderungen kommender Schritte abdeckt.

Aufgrund der inhärenten Ungenauigkeit von Gleitkommaberechnungen auf CPU-Ebene (gemäß IEEE 754) ist dieser Ansatz mathematisch nicht zu 100 % präzise. Durch die strikte Beschränkung auf eine einzige Dezimalstelle erweist er sich jedoch für den vorliegenden Anwendungsfall als hinreichend genau.

Auf dem Intel-System wurde ein signifikanter Performance-Gewinn erzielt, während die Laufzeit auf der AMD-CPU nur um 10 Sekunden reduziert wurde.

4 – Ein String weniger

Bei einer Analyse des aktuellen Quellcodes wird ersichtlich, dass ein neuer String lediglich instanziiert wird, um ihn an die Methode Double::parseDouble zu übergeben. Da dieser String ausschließlich lesend verarbeitet wird, ist die Erzeugung dieser Instanz überflüssig.

Daher wird dazu übergegangen, den Double-Wert basierend auf der Position des Semikolons im ursprünglichen Datensatz direkt zu parsen.

while ((line = reader.readLine()) != null)
{
    // split the line
    final int pos = line.indexOf(';');

    // get us the city
    final String city = line.substring(0, pos);
    // OLD: final String temperatureAsString = line.substring(pos + 1);

    // parse our temperature inline without an instance of a string for temperature
    // OLD: final double temperature = Double.parseDouble(temperatureAsString);
    final double temperature = ParseDouble.parseDouble(line, pos + 1, line.length() - 1);

    // merge the data into the captured data
    cities.merge(city, new Temperatures(temperature), (t1, t2) -> t1.merge(t2));
}

Dieser Schritt erwies sich als unkompliziert und zugleich äußerst effektiv.

5 – Double ist zu viel Arbeit

Falls jemand früher mit älteren Systemen gearbeitet hat – etwa einem 486er oder den ersten Pentium-Modellen –, weiß man, dass Operationen mit double einen erheblichen Mehraufwand bedeuten und langsamer als int sind. Da wir wissen, dass unser Double hier einem Format wie XX.X entspricht, können wir alle Werte problemlos als Ganzzahlen (int) behandeln. Die Korrektur erfolgt dann erst bei der finalen Datenausgabe.

Generell verursacht der Datentyp double signifikanten Overhead. Dies ist auch der Grund, warum moderne KI-Modelle auf deutlich kleineren Gleitkomma-Einheiten wie FP16, BF16 oder FP8 operieren; vereinzelt kommt sogar FP4 zum Einsatz.

/**
 * Parses a double but ends up with an int, only because we know
 * the format of the results -99.9 to 99.9
 */
public static int parseInteger(final String s, final int offset, final int end)
{
    final int negative = s.charAt(offset) == '-' ? offset + 1 : offset;

    int value = 0;

    for (int i = negative; i <= end; i++)
    {
        final int d = s.charAt(i);
        if (d == '.')
        {
            continue;
        }
        final int v = d - DIGITOFFSET;
        // multiply by 10 = multiply by 8 + multiply by 2
        value = ((value << 3) + (value << 1));
        value += v;
    }

    value = negative != offset ? -value : value;
    return value;
}

Das neue Double-Parsing beschränkt sich nun faktisch auf eine reine Ganzzahl-Verarbeitung (int), wobei die Dezimalinformationen vorerst ignoriert werden. Im Wesentlichen wird die Arbeit mit double-Werten auf den Zeitpunkt der Ergebnisausgabe verschoben. Es ist jedoch anzumerken, dass dies noch nicht das Ende der Fahnenstange darstellt.

Der Performance-Gewinn fiel in diesem Schritt eher enttäuschend aus. Dabei gilt es jedoch einen wesentlichen Aspekt moderner Hardware zu berücksichtigen: Eine CPU verfügt in der Regel über mehr Execution Units für Integer-Operationen als für Double-Precision-Berechnungen. Da moderne CPUs Instruktionen parallel verarbeiten, versetzen wir sie durch diesen Wechsel in die Lage, die verfügbaren Ressourcen effizienter auszuschöpfen. Ob wir in diesem speziellen Fall bereits messbar davon profitieren, lässt sich allerdings nur schwer feststellen.

6 – Schau an, kein Lambda

Momentan nutzen wir einen Lambda-Ausdruck, um die Daten zusammenzuführen. Da wir für später weitere Optimierungen planen, müssen wir diesen Ansatz eventuell anpassen.

while ((line = reader.readLine()) != null)
{
    // split the line
    final int pos = line.indexOf(';');

    // get us the city
    final String city = line.substring(0, pos);

    // parse our temperature inline without an instance of a string for temperature
    final int temperature = ParseDouble.parseInteger(line, pos + 1, line.length() - 1);

    // get city and update
    // OLD: cities.merge(city, new Temperatures(temperature), (t1, t2) -> t1.merge(t2));
    final var v = cities.get(city);
    final var t = new Temperatures(temperature);
    cities.put(city, v != null ? v.merge(t) : t);
}

Das war unerwartet: Wir sind nun langsamer. Die Ursache hierfür ist nicht sofort offensichtlich, lässt sich aber einfach erklären.

Wenn wir Daten mittels get abrufen, muss zunächst der hashCode berechnet werden, um die Daten an der entsprechenden Position zu finden (Memory-Read). Für das anschließende put wird dieser gesamte Vorgang wiederholt. Unser vorheriger Lambda-Ausdruck konnte diese Schritte kombinieren; es war lediglich ein Methodenaufruf nötig, bei dem der hashCode nur einmal berechnet und nur einmal auf die zugrunde liegende Datenstruktur zugegriffen werden musste. Aber keine Sorge – wir werden diesen Effizienzgrad wieder erreichen.

7 – Das Anti-Pattern – Mutability

Bevor wir versuchen, die ursprüngliche Geschwindigkeit wiederherzustellen, sollten wir unseren Code auf offensichtlichere Optimierungspotenziale prüfen.

Aktuell verwendet der Code noch immutable (unveränderliche) Klassen zur Speicherung der Temperaturdaten. Das entspricht zwar modernen Best-Practices und ist ideal für nebenläufigen Code, da es Fehlerquellen minimiert, erweist sich jedoch als stiller Performance-Killer. In der Informatik ist nichts umsonst: weder der Speicher noch die CPU-Zyklen oder die Speicherbandbreite. Jedes Mal, wenn eine neue Instanz erstellt wird, um lediglich einen Wert zu aktualisieren, muss die JVM Speicher allokieren und diesen später über die Garbage Collection wieder bereinigen.

Wir stellen daher auf eine mutable (veränderliche) Temperature-Klasse um. Dabei ist wichtig zu verstehen: Nicht die Garbage Collection selbst ist hier das Hauptproblem, sondern der Aufwand für die ständige Allokation neuer Objekte.

while ((line = reader.readLine()) != null)
{
    ...
    // get city
    final Temperatures v = cities.get(city);
    if (v != null)
    {
        // know it, put both together
        v.add(temperature);
    }
    else
    {
        // we have not seen that city yet, create a container and store it
        cities.put(city, new Temperatures(temperature));
    }
}

Wir erstellen nur dann eine neue Temperatures-Instanz, wenn wir die Stadt zuvor noch nicht gesehen haben. Wenn wir die Stadt bereits kennen, fügen wir die Temperatur einfach der bestehenden Instanz hinzu.

Das hat sehr geholfen. Werfen wir einen Blick auf den aktuellen Zustand unseres Codes. Ich habe mir erlaubt, einige der zuvor gezeigten Daten zu entfernen, um die Ansicht kompakt zu halten.

Das Mutieren der Daten macht das merge überflüssig und führt dazu, dass put nur noch sehr selten aufgerufen wird – so selten, dass es in unseren Profiling-Daten gar nicht mehr auftaucht. Das get ist dabei nicht langsamer geworden; es nimmt lediglich einen prozentual größeren Anteil an der verbleibenden Gesamtlaufzeit ein. Zudem ist unsere add-Methode mittlerweile so schnell und höchstwahrscheinlich geinlined, dass sie im Flamegraph nicht mehr als separater Aufruf sichtbar ist.

8 – Eine einfachere Map

Als wir den Lambda-Ausdruck entfernten, verringerte sich die Geschwindigkeit. Diesem Problem widmen wir uns nun. Wir verwenden aktuell die Standard-HashMap aus dem JDK – eine hervorragende und vielseitige Implementierung. Allerdings benötigen wir diese Vielseitigkeit in unserem speziellen Fall nicht. Unsere Profiling-Daten zeigen zudem, dass Methoden wie getNode deutlich sichtbar sind. Ein Blick in den Quellcode der HashMap verdeutlicht, dass Schlüssel und Wert in einem zusätzlichen Wrapper-Objekt, dem Node, gespeichert werden. Das lässt sich effizienter gestalten.

Unsere Map nutzt Backing-Arrays mit Wrapper-Objekten, die Schlüssel und Werte halten. Zudem wird im Falle von Kollisionen eine verkettete Liste aus diesen Wrapper-Objekten aufgebaut.

Eine vereinfachte Map-Implementierung könnte folgendermaßen aussehen:

Unsere offene Map verwendet ebenfalls ein Backing-Array, speichert jedoch Schlüssel und Wert direkt nebeneinander. Sicherlich ist dies in Bezug auf die Code-Ästhetik weniger ideal. Im Falle von Kollisionen speichern wir die weiteren Daten einfach an der jeweils nächsten freien Position im Array. Als Ausgangspunkt für diese Implementierung habe ich ObjObjMap verwendet.

Ein gewisser Gewinn für AMD-CPUs, aber kein nennenswerter für Intel.

9 – Kompaktes Set

Unsere aktuelle Map hat einen Nachteil: Sie benötigt zwei Slots sowie einen Wrapper für die Werte. Warum also nicht beides in einem einzigen Eintrag kombinieren? Auf diese Weise erhalten wir ein Set.

Wir können nun doppelt so viele Objektreferenzen in eine CPU-Cache-Line packen. Da wir das Temperatures-Objekt bereits direkt adressieren, entfällt das Nachschlagen eines zweiten Objekts. Das reduziert die Speicherzugriffe und beschleunigt den gesamten Prozess erheblich.

Im Zuge dieser Änderung eliminieren wir auch die separate put-Methode. Wir kehren zu dem Konzept zurück, das wir beim Entfernen des Lambda-Ausdrucks aufgegeben haben: Wir rufen die Methode einmal auf und lassen sie intern entscheiden, ob ein neuer Eintrag erstellt oder ein bestehender aktualisiert wird. Zudem verschieben wir die gesamte Logik für das Temperatures-Handling direkt in die Set-Klasse.

Sicher, Themen wie Wiederverwendbarkeit, saubere Architektur und Clean Code leiden darunter. Manchmal muss man jedoch Eleganz gegen rohe Performance eintauschen. Es ist kein generisches Set mehr – aber wir setzen hier alles auf maximale Geschwindigkeit, nicht wahr?

private Temperatures[] m_data;

public void getPutOrUpdate( final String city, int value ) {
    final int hash = city.hashCode();
    int ptr = hash & m_mask;
    Temperatures k = m_data[ ptr ];

    if ( k == FREE_KEY ) {
        put(new Temperatures(city, value));
      0;
    }

    if ( k.equals( city ) ) {
        k.add(value);
        return;
    }

    while ( true ) {
        ptr = (ptr + 1) & m_mask; //that's next index
        k = m_data[ ptr ];
        if ( k == FREE_KEY ) {
            put(new Temperatures(city, value));
            return;
        }
        if ( k.equals( city ) ) {
            k.add(value);
            return;
        }
    }
}

Ok, wir haben etwa 2% gewonnen. Nicht viel, aber wir machen Fortschritte.

10 – I/O Schwerarbeit

Nachdem alle „günstigen“ Optimierungen erledigt wurden, muss die I/O-Seite des Prozesses betrachtet werden. Es stellt sich die Frage: Wie kann readLine beschleunigt werden?

Schauen wir doch noch einmal auf die Daten, die uns geliefert werden, sowie deren Definition. Die Daten sind klar strukturiert und fehlerfrei. Alles wird als valides UTF-8 bereitgestellt, wobei ASCII-Zeichen eingeschlossen sind. Dies betrifft die ersten 127 Bytes (nicht Chars).

Da alle Zahlen, Semikolons und Zeilenumbrüche im ASCII-Format vorliegen, gibt es keinen Grund, alles beim Einlesen von Disk sofort in char umzuwandeln. Da von der Disk ohnehin nur Bytes gelesen werden, wird die Umwandlung in char so lange verzögert, bis es absolut nötig ist. Dies ähnelt dem Double-zu-Int-Ansatz: Aktionen, die für die unmittelbare Verarbeitung nicht notwendig sind, werden aufgeschoben.

try (var raf = new RandomAccessFile(fileName, "r");
     var channel = raf.getChannel();)
{
    final Line line = new Line(channel);

    while (true)
    {
        // get us a range of bytes marked in our buffer
        line.readFromChannel();

        if (line.hasNewLine)
        {
            // parse our temperature inline without an instance of a string for temperature
            final int temperature = ParseDouble.parseInteger(line.data,
                line.semicolonPos + 1, line.newlinePos - 1);

            // find and update
            cities.getPutOrUpdate(line, temperature);
        }
        if (line.EOF)
        {
            break;
        }
    }
}

private ByteBuffer buffer = ByteBuffer.allocate(MIN_BUFFERSIZE);
private byte[] data = buffer.array();

private void readFromChannel()
{
    hasNewLine = false;

    try
    {
        // are we nearing the end of the buffer?
        if (end - pos < REMAINING_MIN_BUFFERSIZE)
        {
            // we move the buffer indirectly, because
            // the ByteBuffer just wraps our array,
            // not for the faint of heart
            System.arraycopy(data, pos, data, 0, data.length - pos);
            end = end - pos;
            pos = 0;
            buffer.position(end);

            // fill the buffer up
            final int readBytes = channel.read(buffer);
            if (readBytes == -1)
            {
                EOF = true;
            }

            end = buffer.position();
        }
    }
    catch (IOException e)
    {
        ...
    }
    lineStartPos = pos;

    // look for semicolon and new line
    int i = pos;
    for (; i < end; i++)
    {
        final byte b = data[i];
        if (b == ';')
        {
            semicolonPos = i;
            break;
        }
    }

    i++;
    for (; i < end; i++)
    {
        final byte b = data[i];
        if (b == '\n')
        {
            newlinePos = i;
            pos = i + 1;
            hasNewLine = true;
            return;
        }
    }
}

Es könnte direkt der ByteBuffer genutzt und Bytes daraus gelesen werden, jedoch führt der wiederholte Aufruf von Methoden, welche die Range des Backing-Arrays prüfen (Bounds-Checks), zu signifikantem Overhead. Stattdessen wird direkt auf das Backing-Array zugegriffen, um zusätzliche Geschwindigkeit zu gewinnen. Clean-Code-Fans schließen bitte die Augen.

Was für ein Sprung! Die Profiling-Daten werden nun einer Prüfung unterzogen. Da der Code mittlerweile eine starke Veränderung erfahren hat, wird das Profiling auf die letzten beiden Messungen begrenzt.

In der readLine-Methode ist ein Aufruf von read enthalten, welcher 2,2 % der Laufzeit beansprucht. Die restliche Zeit wird für die Datenverarbeitung aufgewendet. Es wird eingeräumt, dass eine Extraktion in eine eigene Methode sauberer gewesen wäre. Beim nächsten Mal, versprochen!

Es gibt etwas umsonst

Wenn der Baseline-Code mit EpsilonGC ausgeführt wird, zeigt sich eine Heap-Nutzung von etwa 3,2 GB für 10 Millionen Zeilen. Hochgerechnet auf eine Milliarde Zeilen ergibt das astronomische 320 GB. Letztlich handelt es sich dabei um reinen Memory Churn: Speicher anfordern, nutzen, bereinigen, auf Erreichbarkeit prüfen, zur Freiliste hinzufügen oder Speicher verschieben.

Wichtig zu wissen: Es wird hier nicht wirklich durchgehend gegen das OS allokiert oder deallokiert, da die JVM ihr eigenes Management für Memory-Segmente betreibt – also einmal einen großen Chunk vom OS anfordert und diesen so lange wie möglich behält.

EpsilonGC (siehe JEP 318) ist ein Garbage Collector, der schlichtweg gar keine GC durchführt. Speicher wird lediglich zugewiesen, aber niemals freigegeben. Ein Programm wird also zwangsläufig abstürzen, sobald mehr Speicher benötigt wird, als der Heap hergibt. Das ist allerdings perfekt für Tuning-Zwecke und Analysen, da sämtliche Hintergrund-Prozesse des GC komplett offline sind und die Messungen nicht verfälschen.

Eine wichtige Warnung: Da EpsilonGC den Speicher niemals freigibt, findet auch keine Kompaktierung statt. Normalerweise schieben Garbage Collector Live-Objekte im Speicher zusammen, um Lücken zu schließen. Bei EpsilonGC hingegen bleiben die Live-Objekte nach einer Weile verstreut liegen, unterbrochen von “toten” Objekten.

Das führt zu einer schlechteren Cache-Effizienz, da zusammengehörige Daten nicht mehr zwangsläufig in derselben Cache-Line landen. Der Prozessor muss also häufiger auf den langsamen RAM zugreifen, anstatt die Daten direkt im schnellen Cache vorzufinden.

# Run with max heap 4 GB for 10 M lines
java -Xlog:gc*=debug
     -Xms4g -Xmx4g
     -XX:+UnlockExperimentalVMOptions
     -XX:+UseEpsilonGC
     -cp target/classes/
     org.rschwietzke.devoxxpl24.BRC01_BaselineST
     data-10m.txt 0 1

[3.726s][info][gc] Heap: 4096M reserved, 3204M (78.22%) committed, 3199M (78.11%) used

Wird das für Version 13 wiederholt, bevor auf das Byte-Lesen umgestellt wurde, zeigt sich ein Speicherverbrauch von 1,04 GB für 10 Millionen Zeilen. Das summiert sich auf insgesamt 104 GB für 1 Milliarde Zeilen.

# Run with max heap 4 GB for 10 M lines
java ...
     org.rschwietzke.devoxxpl24.BRC13_HardcodedSetST
     data-10m.txt 0 1

[2,035s][info][gc] Heap: 4096M reserved, 1129M (27,57%) committed, 1037M (25,33%) used

Wird das mit Version 14 und dem Byte-Lesen wiederholt, werden lediglich 3,7 MB für 1 Milliarde Zeilen verbraucht. Ja, das ist kein Fehler: weniger als 4 MB für 1 Milliarde Zeilen.

# Run with max heap 4 MB(!) for 1000 M lines
java ...
     -Xms4m -Xmx4m
     org.rschwietzke.devoxxpl24.BRC14_ReadBytesST
     data-1000m.txt 0 1

[55.401s][info][gc] Heap: 4096K reserved, 4096K (100.0%) committed, 3634K (88.73%) used

Dies ist ein eher unerwarteter Bonus: Der Code ist nun effektiv GC-frei (GC-less). Es wird fast kein Speicher verbraucht, und die Daten passen wahrscheinlich in den CPU-Cache. Ein wichtiger Hinweis: Es werden zwar immer noch 13 GB an Daten von der Datei in das Programm transferiert, aber da dies nicht über den Heap abgewickelt wird, entfallen die ständigen Allokationen und die Garbage Collection. Während der CPU-Cache eventuell eine gewisse „Pollution“ erfährt (bei der das Lesen neuer Daten von der Platte nützliche Daten aus dem Cache verdrängt), ist die Gesamteffizienz massiv.

11 – Zurück zu den Zahlen

Ein riesiger Sprung wurde gemacht, aber das Ziel einer 80-prozentigen Reduzierung ist noch nicht ganz erreicht. Während die Ergebnisse auf dem Intel-System bereits sehr nah dran sind, hängen die AMD-Werte noch leicht hinterher.

Zuerst wird ein „billiges“ Tuning ausprobiert. Dabei wird sich erneut dem Zahlen-Parsing gewidmet. Wir entfernen die Schleife und arbeiten mit den Informationen des Zahlenformates.

/**
 * Parses a double but ends up with an int, only because we know
 * the format of the results -99.9 to 99.9
 */
public static int parseIntegerFixed(final byte[] b, final int offset, final int end) {
    final int length = end - offset; // one is missing, we care for that later

    // we know the first three pieces already 9.9
    int p0 = b[end];
    int p1 = b[end - 2] * 10;
    int value = p0 + p1 - (DIGITOFFSET + DIGITOFFSET * 10);

    // we are 9.9
    if (length == 2) {
        return value;
    }

    // ok, we are either -9.9 or 99.9 or -99.9
    if (b[offset] != (byte)'-') {
        // we are 99.9
        value += b[end - 3] * 100 - DIGITOFFSET * 100;
        return value;
    }

    // we are either -99.9 or -9.9
    if (length == 3) {
        // -9.9
        return -value;
    }

    // -99.9
    value += b[end - 3] * 100 - DIGITOFFSET * 100;
    return -value;
}

Es konnte noch ein wenig Saft aus der Performance-Zitrone gepresst werden. Durch das Eliminieren der Schleife wird die Arbeit der CPU erleichtert. Es gibt zwar immer noch mehrere If-Bedingungen, aber sie halten den Code lesbar. Da eine CPU Sprünge nicht mag, haben If-Statements und Schleifen immer eine Auswirkung auf die Performance.

Die CPU versucht, den wahrscheinlichen Branch zu erraten, und führt diesen Code bereits spekulativ in ihrer Pipeline aus. Erweisen sich die If-Bedingungen als falsch, wird das temporäre Ergebnis verworfen und auf dem anderen Branch fortgefahren. Je weniger dieser “Misses” auftreten, desto schneller ist der Ablauf, da moderne CPUs viele Befehle gleichzeitig und nicht nur strikt nacheinander ausführen. Wenn dieser parallele Fluss gestört wird, sinkt die Geschwindigkeit.

12 – Min/Max in einfach

Schauen wir uns unseren Code genauer an und beginnen mit diesem Teil, der die Gesamtwerte für eine Stadt aktualisiert.

public void add(final int value)
{
    this.min = Math.min(this.min, value);
    this.max = Math.max(this.max, value);
    this.total += value;
    this.count++;
}

Dieser Code vergleicht den neuen Wert stets mit dem Minimum und schreibt in den Speicher, auch wenn sich der Wert nicht geändert hat. Dasselbe gilt für das Maximum, auch wenn das Minimum bereits aktualisiert wurde. Während Math.min und Math.max wahrscheinlich effiziente Intrinsics sind, sollten unnötige Schreibvorgänge vermieden werden. In den meisten Fällen müssen weder das Minimum noch das Maximum aktualisiert werden. Wir schreiben natürlich nicht sofort in den Speicher direkt, sondern erst in den Cache, aber selbst dafür benötigt man CPU‑Instruktionen (unser Code weiß nichts von Caches).

public void add(final int value)
{
    if (value < this.min)
    {
        this.min = value;
    }
    else if (value > this.max)
    {
        this.max = value;
    }
    this.total += value;
    this.count++;
}

Die folgende Liste zeigt eine weitere Verbesserung, die ich noch nicht im Detail erklärt habe (BRC20_UseArrayNoBufferST): Wir nutzen die direkte Referenz unseres Backing-Arrays, anstatt den ByteBuffer jedes Mal nach diesem Array zu fragen, denn es ändert sich nie.

Es ist interessant festzustellen, dass der Buffer-Trick Intel beschleunigt, aber nicht AMD, während Min/Max auf beide eine ähnliche Wirkung hat. Dennoch sind wir noch nicht am Ziel.

13 – Eine Schleife weniger

Schauen wir noch einmal genau hin und speziell auf die aktuelle Liste der Hot-Methods. Es ist erkennbar, dass viel Zeit für die hashCode-Berechnung aufgewendet wird. Wie kann dies effizienter gestaltet werden?

// OLD: look for semicolon and new line
int i = pos;
for (; i < end; i++)
{
    final byte b = data[i];
    if (b == ';')
    {
        semicolonPos = i;
        break;
    }
}

// Later
public int ByteBuffer::hashCode() {
    int h = 1;
    int p = position();
    for (int i = limit() - 1; i >= p; i--)
        h = 31 * h + (int)get(i);

    return h;
}

In der ersten Schleife wird nach dem Semikolon gesucht, und später wird im Wesentlichen dieselbe Schleife verwendet, um den hashCode zu berechnen. Machen wir das doch einfach in einem Rutsch!

// NEW: look for semicolon and calculate the hashCode
// Ensure that we are not including the semicolon of course
int h = 1;
int i = pos;
for (; i < end; i++)
{
    final byte b = data[i];
    if (b == ';')
    {
        semicolonPos = i;
        break;
    }
    h = 31 * h + b;
}
this.hashCode = h;

Geschafft! Die Intel-Maschine hat die 20%-Barriere (80%-Reduktion) durchbrochen, während die AMD-Maschine fast am Ziel ist.

Weiteres Tuning für AMDs

Um die AMD-CPU über die Ziellinie zu bringen, wird weiteres Tuning durchgeführt und mit Ideen experimentiert. Einige werden beibehalten, andere verworfen. Am Ende wird ersichtlich sein, dass der Code wie versprochen fünfmal schneller läuft – ohne Nutzung von Unsafe, ohne Bit-Magie und ohne GraalVM. Um die Artikellänge zu begrenzen, werden die anderen Änderungen nicht im Detail diskutiert.

Im Repository ist der komplette Code einsehbar. Dort sind auch Beispiele für Ansätze enthalten, die nicht funktioniert haben. Zudem kann man sehen, dass beim Vergleich mit einem anderen Datensatz ein Defekt entdeckt wurde: BRC58_UnnoticedCharSkipping. Trotz der implementierten Prüfsumme treten manche Fehler erst auf, wenn der Input variiert.

Da ist das Ergebnis – optimiert, ohne den Code in ein komplettes Desaster zu verwandeln. Es ist vielleicht ein wenig unübersichtlich, aber immer noch wartbar. Es sollte bedacht werden, dass sich hier auf saubere, gut formatierte Daten verlassen wird. Müssten Prüfungen für fehlerhafte Daten oder unterschiedliche Längen hinzugefügt werden, sähen Komplexität und Performance gänzlich anders aus.

Ist aufgefallen, dass nach dem Bugfix (BRC58) wieder Performance verloren ging? Warum das Ergebnis dennoch vorher in Ordnung war, lässt sich so erklären: Wenn über 2.000 Temperaturen pro Stadt addiert werden und der Durchschnitt gebildet wird, fällt es kaum ins Gewicht, ob alle 2.000 Werte korrekt gelesen wurden. Dies würde nur auffallen, wenn die Abweichung zu groß wird oder einer der Extremwerte fehlt.

Lerneffekt: Die Testdaten sollten stets variiert werden!

Hinter den Kulissen

Für Fans von Hardcore-Performance und Low-Level-Fakten wird nun in die CPU- und Speicherdetails eingetaucht. Diese Statistiken wurden mit dem perf-Tool erstellt, welches durch den Linux-Kernel bereitgestellt wird.

perf funktioniert nicht auf allen Cloud-Maschinen; es besteht eine Abhängigkeit von der Virtualisierungsschicht und den gesetzten Berechtigungen. Die Ergebnisse können daher variieren.

Die ursprüngliche Baseline, die 80-%-Lösung (BRC45) und der Gesamtsieger des Wettbewerbs werden verglichen, um die Auswirkungen dieser Optimierungen auf Hardware-Ebene zu verstehen.

Fazit: Ursprünglich wurden etwa 2.258 CPU-Instruktionen für jede CSV-Zeile benötigt. Durch die optimierte Version wurde dieser Wert auf 303 gesenkt, und vom Gewinner-Code wird die Aufgabe mit nur 164 Instruktionen erledigt.

IPC (Instruktionen pro Zyklus) misst, wie viel Arbeit von der CPU mit jedem Hertz erledigt wird. Eine höhere Zahl bedeutet eine bessere Auslastung der internen Ressourcen der CPU. Branch-Misses treten auf, wenn von der CPU falsch vorhergesagt wird, welchen Weg ein if oder eine Schleife nehmen wird. Dies führt zu einem Pipeline-Stall, durch den Zeit verschwendet wird.

Baseline bis BRC45

# org.rschwietzke.devoxxpl24.BRC01_BaselineST
# Hetzner, AMD, 21.0.4-tem
# Measurement Runtime: 150,932 ms 100%

       160,915.21 ms task-clock              #   1.066 CPUs utilized
           37,195    context-switches        # 231.147 /sec
            6,232    cpu-migrations          #  38.728 /sec
          236,617    page-faults             #   1.470 K/sec
  539,415,718,644    cycles                  #   3.352 GHz
   41,233,849,888    stalled-cycles-frontend #   7.64% frontend cycles idle
2,258,010,166,520    instructions            #    4.19 insn per cycle
                                             #    0.02 stalled cycles per insn
  522,584,792,160    branches                #   3.248 G/sec
    2,479,441,210    branch-misses           #   0.47% of all branches

    150.932228741 seconds time elapsed

    145.057695000 seconds user
     11.626114000 seconds sys

#2258 instructions per CSV line

# org.rschwietzke.devoxxpl24.BRC45_DoubleTheSetSize
# Hetzner, AMD, 21.0.4-tem
# Mean Measurement Runtime: 27,061 ms 17.9% (to baseline)

      27,538.78 msec task-clock              #   1.018 CPUs utilized
          1,029      context-switches        #  37.365 /sec
             29      cpu-migrations          #   1.053 /sec
          7,885      page-faults             # 286.324 /sec
 98,276,507,946      cycles                  #   3.569 GHz
 10,431,399,857      stalled-cycles-frontend #  10.61% frontend cycles idle
303,659,521,159      instructions            #    3.09 insn per cycle
                                             #    0.03 stalled cycles per insn
 55,868,360,010      branches                #   2.029 G/sec
  1,540,980,291      branch-misses           #  2.76% of all branches

   27.061235813 seconds time elapsed

   26.366348000 seconds user
    1.062075000 seconds sys

# 303 instructions per CSV line

• Die Anzahl der Branches sank um den Faktor fünf von der Baseline zu unserem BRC45.
• Cache-Misses (stalled-cycles-frontend) sanken um 75%.
• Wir benötigen nur noch 14% der Instruktionen.
• Die absolute Anzahl der Branch-Misses ist gesunken, relativ gesehen sind sie jedoch gestiegen.

BRC45 zum 1BRC Gewinner

# Thomas Wuerthinger, 1 core
# Hetzner, AMD, 21.0.4-tem
# Mean Measurement Runtime: 11,281 ms 7.4% (to baseline)
# 41.7% of BRC45_DoubleTheSetSize

      11,269.99 msec task-clock              #   0.999 CPUs utilized
          1,748      context-switches        # 155.102 /sec
              1      cpu-migrations          #   0.089 /sec
        223,183      page-faults             #  19.803 K/sec
 39,555,927,795      cycles                  #   3.510 GHz
  2,945,609,903      stalled-cycles-frontend #  7.45% frontend cycles idle
164,487,950,474      instructions            #    4.16 insn per cycle
                                             #    0.02 stalled cycles per insn
 15,668,783,505      branches                #   1.390 G/sec
    149,371,238      branch-misses           #  0.95% of all branches

   11.281867347 seconds time elapsed

    0.076590000 seconds user
    0.130600000 seconds sys

# 164 instructions per CSV line

• Die Reduzierung der Branches ist gewaltig und resultiert hauptsächlich aus dem branchless Parsing von Zahlen.
• Die Reduzierung der Instruktionen stammt primär aus dem Lesen von 8 Bytes statt Byte für Byte zu lesen.
• Die Reduktion der Branch-Misses lässt den Code förmlich fliegen.

Übrigens könnte man Unsafe⁣ vermeiden und ein long ganz legal mit der getLong()-Methode aus dem ByteBuffer lesen. Leider gibt es keinen einfachen Weg, das ohne Bit-Magie zu parsen. Außerdem enthält ein Aufruf von getLong Bereichsprüfungen, die unsere Gewinne teilweise wieder aufzehren.

Unterschiedliche Maschinen

Wir haben bereits gesehen, dass CPUs sehr verschieden sind, und diese Warnung lässt sich problemlos auf Typen von Maschinen ausweiten. Das ist eine Auswahl von Cloud-Maschinen plus mein Laptop.

Es wird dringend empfohlen, Benchmarks auf der Hardware durchzuführen, auf der auch der Produktivcode ausgeführt werden soll, ansonsten könnte ein Teil des Tuning-Aufwands umsonst gewesen sein.

Manchmal könnte es einfach ausreichen sein, für ein paar Cent mehr einen anderen Typ zu wählen, statt Tage mit Tuning zu verbringen. Aber am Ende kann Tuning auch jede Menge Kosten sparen.

Die Cloud ist nebelig

Performance-Messungen in der Cloud sind oft eine Falle, da man selten allein auf der Hardware ist. Geteilte Ressourcen bedeuten, dass kleine Performance-Gewinne leicht von „noisy neighbors“ oder unerwarteten Schwankungen in der CPU- und Speicherbandbreite überdeckt werden können. Außerdem können Features wie Burst-Kapazität zu inkonsistenten Ergebnissen führen. Zu allem Überfluss versagen Low-Level-Profiling-Tools wie perf oft in virtualisierten Umgebungen, was einen im Blindflug lässt, wenn man Hardware-Effekte verstehen will.

# BRC01_BaselineST - DigitalOcean Intel CPU 16c
Warmup Runtime:      219,665 ms
Warmup Runtime:      220,341 ms
Warmup Runtime:      219,312 ms
Measurement Runtime: 219,020 ms
Measurement Runtime: 223,180 ms
Measurement Runtime: 226,418 ms

BRC27_SmallPutST - DigitalOcean Intel CPU 16c

Warmup Runtime:      38,792 ms
Warmup Runtime:      37,929 ms
Warmup Runtime:      39,136 ms
Measurement Runtime: 39,197 ms
Measurement Runtime: 39,103 ms
Measurement Runtime: 39,106 ms

Die obige Auflistung zeigt einige Durchläufe auf DigitalOcean Intel-Hardware. Man sieht, wie die Laufzeiten schwanken. Die optimierte Version ist etwas stabiler, was teilweise an JVM-Effekten wie dem Ausbleiben von GC liegen könnte (da wir auf einen Zero-Allocation-Ansatz umgestellt haben). Für Mikrooptimierungen können jedoch selbst diese kleinen Schwankungen eine erhebliche Hürde darstellen.

Zusammenfassung

Die One Billion Row Challenge ist eine fantastische Möglichkeit, die Java-Performance zu erkunden. Durch einen systematischen Tuning-Ansatz – beginnend bei einer sauberen Baseline über die schrittweise Optimierung von Stream-Nutzung bis hin zu I/O und eigenen Collection-Implementierungen – haben wir eine Reduzierung der Laufzeit um 80% erreicht, und das nur mit Standard-Java-Features.

Diese Techniken sind nicht nur für Programmierwettbewerbe gedacht; sie zeigen, wie ein tieferes Verständnis der JVM, des Speichermanagements und der Hardware-Charakteristika zu großen Effizienzsteigerungen führen kann. Nicht vergessen: Schneller bedeutet weniger Ressourcen, und das übersetzt sich direkt in niedrigere Infrastrukturkosten.

Obwohl Unsafe meiner Meinung nach kein Standard-Feature ist und extreme Bit-Magie zwar völlig legal ist, aber den Code für die meisten schwer verständlich macht, fallen diese Techniken unter: nur wenn wirklich nötig, nur durch Experten und nur mit einer Menge Dokumentation.

Wer lieber sieht und hört, kann sich diesen Vortrag auch auf YouTube ansehen und die Slides online durchstöbern. Wenn diese Art von Inhalten euch gefällt, lasst es mich bitte wissen. Weitere Performance-Inhalte finden Sie in meinem persönlichen Blog.

Hinweis: Messen und optimieren sollte man nur dort, wo ein Problem vorliegt. Das Problem sollte auch klar formuliert sein, denn das Tuning für Laufzeit-, Ressourcen- oder Kostenprobleme unterscheidet sich deutlich.

Neugierig geworden?
René Schwietzke ist Speaker auf der JCON (20. – 23. April 2026). In diesem Artikel geht es um die One Billion Row Challenge – und in seiner JCON-Session zeigt er, wie man die Lösung mit moderner Java-Concurrency über mehrere Cores skaliert.
Falls Du die Session verpasst, kein Problem! Das Video zum Talk ist nach der JCON verfügbar.