Die Herausforderung mit einer Milliarde Zeilen

 (morling.dev)
2 Punkte von GN⁺ 2024-01-05 | 2 Kommentare | Auf WhatsApp teilen
  • Die One Billion Row Challenge (1BRC), die den ganzen Januar 2024 lief, ist eine Performance-Challenge, bei der gemessen wird, wie schnell Java bei der Verarbeitung einer Textdatei mit einer Milliarde Zeilen werden kann.
  • Die Eingabe ist einfacher Text im Format station;temperature, aber es müssen für jede Messstation die Minimal-, Durchschnitts- und Maximaltemperatur berechnet und korrekt nach Namen sortiert ausgegeben werden.
  • Für die Implementierung ist nur Java erlaubt; die über SDKMan bereitgestellten Distributionen und Early-Access-Builds von openjdk.net dürfen verwendet werden, externe Abhängigkeiten sind jedoch verboten.
  • Teilnehmende reichen ihren Beitrag per Pull Request im GitHub-1brc-Repository ein und können die bereitgestellte Referenzimplementierung zum Vergleich von Ausgabeformat und Performance nutzen.
  • Die Bewertung erfolgt in derselben Hetzner-Cloud-CCX33-Umgebung: fünf Durchläufe, dann werden Best- und Schlechtestwert gestrichen und aus den übrigen drei Läufen der Durchschnitt für das Leaderboard gebildet.

Die Java-Aufgabe, die eine Milliarde Zeilen am schnellsten aggregiert

  • Die One Billion Row Challenge ist eine Java-Performance-Challenge, die vom 1. bis 31. Januar 2024 stattfand.
  • Teilnehmende schreiben ein Java-Programm, das Temperaturmesswerte aus einer Textdatei liest und für jede Wetterstation Minimal-, Durchschnitts- und Maximaltemperatur berechnet.
  • Der Kern der Schwierigkeit liegt darin, dass die Eingabedatei 1.000.000.000 Zeilen umfasst.
  • Die Eingabe hat eine einfache Struktur mit genau einem Messwert pro Zeile.
    • Beispiel: Hamburg;12.0
    • Beispiel: Bulawayo;8.9
    • Beispiel: Palembang;38.8
  • Die Ausgabe muss die Stationsnamen alphabetisch sortieren und für jede Station die Werte min/mean/max anzeigen.
    • Beispiel: {Abha=5.0/18.0/27.4, Abidjan=15.7/26.0/34.1, ...}

Einreichungsregeln und Ausführungsumgebung

  • Ziel ist es, die schnellste Java-Implementierung für dieselbe Aufgabe zu erstellen.
  • Für Optimierungen können virtuelle Threads, die Vector API und SIMD, GC-Optimierung, AOT-Kompilierung und Ähnliches genutzt werden.
  • Die grundlegenden Regeln sind wie folgt.
    • Der Beitrag muss in Java geschrieben sein.
    • Java-Distributionen von SDKMan sowie Early-Access-Builds von openjdk.net dürfen verwendet werden.
    • Auch EA-Builds von OpenJDK-Projekten wie Valhalla sind erlaubt.
    • Externe Abhängigkeiten dürfen nicht verwendet werden.
  • Teilnehmende klonen das 1brc-Repository und reichen ihre Implementierung gemäß den Anweisungen in der README ein.
  • Die Referenzimplementierung dient als Vergleichsmaßstab und zur Prüfung des korrekten Ausgabeformats.
  • Eingereicht wird durch das Öffnen eines Pull Requests im Upstream-Repository.

Berechnung des Leaderboards und Community-Austausch

  • Die Bewertung erfolgt auf einer Instanz von Hetzner Cloud CCX33.
    • Spezifikation: 8 dedizierte vCPU, 32 GB RAM
    • Die End-to-End-Laufzeit wird mit dem Programm time gemessen.
    • Jeder Beitrag wird fünfmal hintereinander ausgeführt.
    • Der langsamste und der schnellste Lauf werden ausgeschlossen.
    • Aus den verbleibenden drei Laufzeiten wird der Durchschnitt als Ergebnis des Beitrags gebildet.
    • Das Ergebnis wird dem Leaderboard hinzugefügt.
  • Diskussionen über Optimierungstechniken werden in den Discussions des GitHub-Repositories fortgeführt.
  • Es gibt außerdem ein Show & Tell zum Teilen von Implementierungen in anderen Sprachen als Java; dort werden etwa 1BRC-Umsetzungen in Rust, Go und C++ vorgestellt.

Verwandte Beiträge

2 Kommentare

 
GN⁺ 2024-01-05
Meinungen auf Hacker News

  • Die Lösung, die derzeit die beste Performance zu haben scheint [0], berücksichtigt Hash-Kollisionen nicht; wenn es im Datensatz genügend unterschiedliche Städte gibt, dürfte sie falsche Ergebnisse liefern
    Ich frage mich, ob ich da etwas übersehe
    [0] https://github.com/gunnarmorling/1brc/blob/main/src/main/jav...

    • Stimmt. Das Problem kam gestern auf, und tatsächlich verließen sich zwei Lösungen auf Hash-Funktionen, die auf einen bestimmten Datensatz zugeschnitten waren, und verstießen damit gegen die Regel, dass sie für alle Messstationsnamen funktionieren müssen; bei der Auswertung wurde das übersehen
      Vorerst wurden die Einträge aus der Rangliste entfernt, und die beiden Autoren korrigieren ihre Einreichungen, sodass sie später wieder hinzugefügt werden sollen
      [0] https://twitter.com/mtopolnik/status/1742652716919251052

  • Mit folgendem Ansatz sollte sich das Ganze meiner Ansicht nach in 0,3 Sekunden verarbeiten lassen
    Da Temperaturen eine Nachkommastelle haben, reichen im Normalfall etwa 400 Werte; auch Ortsnamen sind mit etwa 400 endlich, sodass man eine Lookup-Tabelle mit rund 160.000 Kombinationen aus Temperatur × Ortsname erstellen kann
    Man generiert automatisch eine Zustandsmaschine, die jede dieser 160.000 Kombinationen, egal an welcher Rotationsposition innerhalb eines 4-Byte-Registers sie liegt, auf einen eindeutigen Bucket in einer Hash-Tabelle abbildet, und führt in einem 32-Bit-Zustandsregister pro Zyklus einen Lookup in der Zustandsübergangstabelle sowie ein XOR mit den nächsten 4 Bytes aus
    Man läuft mit Speichergeschwindigkeit über den gesamten Datensatz und erhöht die Zähler pro Zustand; da es nur 65K Zustände gibt, passen die Zähler in den Cache
    Mit AVX512 könnte man pro Core 512 solcher 32-Bit-Zustandsmaschinen parallel laufen lassen, sodass die Berechnung nicht der Bottleneck wäre
    Hohe/niedrige Temperaturen oder unbekannte Ortsnamen, die nicht auf gültige Buckets abgebildet werden, leitet man an langsameren Code weiter; auch die Behandlung von Minimum/Maximum lässt sich über einen solchen Escape abwickeln, was nur ein paar tausend Mal vorkommt
    Dieser Ansatz kann schon mit einem einzelnen AVX512-Core mit Speichergeschwindigkeit laufen, daher sehe ich keinen Vorteil darin, ihn auf mehrere Cores aufzuteilen

    • Eine Lookup-Tabelle ist nicht nötig. Gefordert sind nur Minimum/Durchschnitt/Maximum, also lässt sich alles in einem einzigen Durchlauf berechnen, ohne die Daten zu speichern
      Benötigt werden lediglich eine Hash-Tabelle mit 400 Einträgen, drei Fließkommawerte für laufendes Minimum, Mittelwert und Maximum sowie ein Integer-Zähler zum Aktualisieren des Mittelwerts
      Selbst mit 16 Bytes für den Namen passt das Ganze in 16 KB
      Die Laufzeit wird von Ein-/Ausgabe dominiert, danach vermutlich vom JSON-Parsing
    • Ein einzelner Core kann die Speicherbandbreite nicht auslasten. Cores sind durch Speicherparallelität und Latenz begrenzt
      Die meisten aktuellen x86-Serverchips können zwei SIMD-Loads pro Takt retire'n, sodass mit AVX2 bei 1 GHz etwa 32 GB/s möglich sind; AVX-512 ist also nicht zwingend nötig, um die Bandbreite pro Core zu maximieren
      Wenn man aber aus DRAM liest, wird man viel früher ausgebremst, auf typischen Servern wahrscheinlich irgendwo um 10–16 GB/s
      Solange der Großteil der Daten in den RAM ausweicht, bricht der Durchsatz eines einzelnen Cores deutlich ein, und bei großen Streaming-Aufgaben lohnt sich Multi-Core-Parallelität fast immer
      Das lässt sich leicht überprüfen, indem man einen Speicherblock allokiert, der deutlich größer als der L3-Cache ist, die Page Faults vorab auslöst und dann in einer engen Schleife entrollte Vektor-Loads (AVX2/AVX-512) ausführt
    • Da der nächste Zustand immer vom vorherigen Zustand abhängt, weiß ich nicht, wie man die Zustandsmaschine parallel ausführen soll
      Außerdem ist fraglich, wie das Zustandsregister interpretiert werden soll. Wenn man es mit den 4 Eingabebytes XORt, kann bei unerwarteten Ortsnamen im Grunde jeder von 4,7 Milliarden möglichen Werten herauskommen
      Selbst bei erwarteten Ortsnamen braucht man, wenn sie länger als 4 Bytes sind, nicht jeweils mehrere Zustände, um sie von anderen Namen mit gemeinsamem Präfix zu unterscheiden?
    • Man müsste wohl die Auslegung der Regeln prüfen. Es ist nicht klar, ob Code gültig ist, der auf die bekannten 400 Ortsnamen spezialisiert ist, aber über einen langsamen Pfad zusätzliche Namen unterstützt
      Die Regeln sagen, dass jede Lösung für beliebige UTF-8-Messstationsnamen funktionieren muss, auch wenn der Datengenerator eine feste Menge von Stationsnamen verwendet
    • Um Ortsnamen zu finden, muss man am Ende ohnehin die gesamte Datei lesen und parsen

  • Statt den langsamsten und den schnellsten Lauf zu verwerfen und den Durchschnitt der übrigen drei zu nehmen, fände ich es besser, die zwei langsamen Läufe zu verwerfen oder einfach den schnellsten Wert anzuerkennen
    Ich sehe keinen stichhaltigen Grund, ein gutes Ergebnis zu verwerfen

    • Das ist eine ziemlich übliche Messmethode namens getrimmter Mittelwert (Trimmed Mean): https://statisticsbyjim.com/basics/trimmed-mean/
    • Es gibt einen Grund, den besten Lauf zu verwerfen. Wenn man annimmt, dass sich das System vorhersagbar verhält und nur durch Hintergrundaufgaben langsamer wird, kann es sinnvoll sein, den besten Lauf zu verwenden
      Gibt es im Programm aber auch nur eine kleine Quelle von Nichtdeterminismus – was häufiger vorkommt, als man denkt –, ist die Bestzeit wahrscheinlich wenig repräsentativ
      Dazu ist https://tratt.net/laurie/blog/2019/minimum_times_tend_to_mis... ein guter Artikel
    • Wenn es nicht akzeptabel ist, den schnellsten Lauf zu verwerfen, frage ich mich, warum man dann dafür ist, den langsamsten Lauf zu verwerfen

  • Wer es mit den Regeln genau nimmt, möchte beim ersten Lauf einen Hintergrund-Daemon starten, die gesamte Datei in den Speicher laden und dort fixieren und dann sogar den Cache vorwärmen, sodass spätere Läufe praktisch nur noch einen linearen Scan machen
    Je nachdem, wie weit man die Regeln auslegt, scheint es auch möglich, die Ergebnisse schon beim ersten Lauf vorab zu berechnen; ebenso könnte man die Zahlen vorher in ein dichteres Format parsen und sie in späteren Läufen direkt als laufende Summe einlesen
    Das entspricht überhaupt nicht dem Geist des Wettbewerbs, scheint nach den sichtbaren Regeln aber nicht ausdrücklich verboten zu sein
    Wenn man Vorabberechnungen nicht mag, wären auch Tricks wie das vorherige Sortieren der Eingabe, Vorab-Parsing oder Komprimieren, Sortieren und eine sortierte Speicheranordnung möglich
    Im Extremfall könnte man sogar das Skript calculate_time patchen, sodass es 0 Sekunden zurückgibt und für Konkurrenten 9999

    • Wenn man den Teilnehmenden genau die Datei gibt, die im Wettbewerb tatsächlich verwendet wird, entsteht ein echtes Problem
      Zwischen dem Hartcodieren der Antwort in einer Zeile, ohne die Eingabe überhaupt zu lesen, und einer Verarbeitung unter der Annahme, den Dateiinhalt nicht zu kennen, gibt es ungefähr eine Milliarde Stufen in der Grauzone der Vorabberechnung
      Am Ende könnte es ein Wettbewerb darüber werden, was faire Vorabberechnung ist und was nicht
      Deshalb zeigen Machine-Learning-Wettbewerbe den Teilnehmenden die finalen Daten nicht
    • Das dürfte gegen diese Regel verstoßen
      Dort steht, dass die Berechnung zur Laufzeit der Anwendung erfolgen muss und dass die Messdatei nicht zur Build-Zeit verarbeitet und das Ergebnis in das Binary eingebrannt werden darf
    • Meiner Meinung nach sollten die Regeln ausdrücklich festlegen, dass jeder Lauf in einem separaten tmpfs ausgeführt wird und zwischen den Läufen alle Prozesse sowie der Page Cache geleert werden

  • Ich frage mich, ob das nicht schlicht durch die Festplattengeschwindigkeit begrenzt ist. Ich bezweifle, dass Optimierungen wie SIMD oder Multithreading viel bringen
    Es hängt zwar von der Zahl der unterschiedlichen Stationen und der Art der Hash-Lookups ab, aber im Vergleich zu I/O bin ich skeptisch, ob das überhaupt messbar ist

    • Festplattenzugriffe lassen sich parallelisieren, und NVMe ist sehr schnell, daher kann der Engpass eher bei der CPU als bei der Festplatte liegen
      Systeme, die für moderne Hardware entworfen wurden, nutzen genau das aus; redpanda.com, wo ich arbeite, ist ein solches Beispiel
      Parsing macht einen großen Teil der Rechenzeit aus, und SIMD-Techniken wie SWAR zum Finden von Trennzeichen können helfen
      Wenn man eine saubere Implementierung solcher Algorithmen sehen möchte, ist Stringzilla gut: https://github.com/ashvardanian/StringZilla
      Auf den Punkt, dass die Datei nach dem ersten Lauf vollständig im Speicher gecacht ist, habe ich hier geantwortet: https://news.ycombinator.com/item?id=38864034
    • Das hängt vollständig von Workload und Hardware ab. Selbst normale Consumer-SSDs können problemlos 7 GB/s (56 Gbps) halten, wenn von 2 TB nur 700 GB genutzt werden
      Typische Server haben genug PCIe-Lanes für 15 solcher SSDs, sodass die I/O-Bandbreite eines Servers in etwa auf dem Niveau der Speicherbandbreite liegt
      Teurere Server haben schnellere und mehr Lanes, etwa PCIe 5.0
      Diese Datei hat eine Milliarde Zeilen und ist komprimiert etwa 1 GB groß; nach dem ersten, verworfenen Lauf liegt sie im Speicher, daher spielt die I/O-Bandbreite in diesem Szenario keine Rolle
      Im GitHub-Repository steht, sie sei unkomprimiert 12 GB groß, aber auch das bestätigt, dass die I/O-Bandbreite nicht entscheidend ist
    • Dieser Vortrag von Daniel Lemire ist interessant: https://www.youtube.com/watch?v=wlvKAT7SZIQ
      Die Kernaussage ist, dass die Festplatte nur selten der Engpass ist
    • Das hängt vom Betriebssystem und Dateisystem ab. Die Eingabedatei ist etwa 12 GB groß und wird auf einer Maschine mit 32 GB RAM fünfmal ausgeführt, daher kann nach dem ersten Lauf die gesamte Datei im Speicher gecacht sein
      Unter Linux mit ext2 zum Beispiel ist es wahrscheinlich, dass nach dem ersten Lauf die ganze Datei gecacht ist; bei ZFS muss das nicht der Fall sein
    • Für das schnellste Parsing scheint es naheliegend, alles in den RAM zu laden und vom Ende her rückwärts zu verarbeiten
      Dann kommen die Ziffern von der niedrigsten zur höchsten Stelle, danach das Trennzeichen und der String, und man läuft weiter, bis man EOF oder einen Zeilenumbruch erreicht

  • Laut Regeln müssen Einreichungen für alle Eingaben korrekt funktionieren, aber offenbar dürfen und sollten sie wohl auf die spezifischen Eingaben abgestimmt werden, die von create_measurements.sh erzeugt werden
    Man kann sich zum Beispiel eine Einreichung vorstellen, die eine auf die gegebene Stationsmenge zugeschnittene perfekte Hash-Funktion verwendet

    • Wenn diese Anforderung gilt, wäre es klug, die Testdaten anders zu gestalten als die Beispieldaten
      So ließen sich überangepasste Optimierungen verhindern
    • Durch UTF-8 wird es deutlich schwieriger. Wenn man aber nur dem Wortlaut und nicht dem Geist der Regeln folgt, kann man einfach zu einer langsamen Implementierung wechseln, sobald ein Byte größer als 127 erkannt wird
      Ein Byte größer als 127 bedeutet ein mehrbyteiges UTF-8-Zeichen

  • Aus Spaß habe ich einen Geschwindigkeitsvergleich awk gegen Java gemacht
    Es ist ein Skript, das mit awk -F';' pro Station Summe, Anzahl, Minimum und Maximum akkumuliert und am Ende den Durchschnitt berechnet und ausgibt

    • Ich würde gern einen Geschwindigkeitsvergleich mit PostgreSQLs File Foreign Data Wrapper sehen: https://www.postgresql.org/docs/current/file-fdw.html
      Dabei würde man mit file_fdw die CSV-Datei als externe Tabelle anlegen und per GROUP BY station_name MIN, AVG und MAX berechnen
    • Mit ClickHouse local kommt man auf etwa 15,2 Sekunden
      In clickhouse local wird file('measurements.txt', 'CSV', 'station String, t Float32') gelesen, nach Stationen gruppiert und min, max, avg berechnet, mit max_threads = 8
      Der Großteil der Zeit wird für das Parsen der Datei aufgewendet
    • Da die Variable sum recht groß werden kann, sollte man besser einen Streaming-Mittelwert verwenden
      Zum Beispiel nach dem Muster new_mean = ((n*old_mean)+temp)/(n+1)

  • Eine interessante Challenge, aber schade, dass sie nur für Java ist. Ich freue mich auf den Moment, in dem Leute anfangen, JVM-Bytecode direkt von Hand zu erstellen

    • In der Diskussion scheint es Einreichungen in mehreren Sprachen zu geben. Go, Rust, Python, C++ usw.
      [0] https://github.com/gunnarmorling/1brc/discussions
    • Oder man könnte „muss in Java geschrieben sein“ auch als „muss zum Start der Ausführung die JVM verwenden“ interpretieren, und aus Java heraus andere Prozesse zu starten ist eindeutig möglich

  • Macht Spaß. Fühlt sich an wie die Nachbereitung zu Advent of Code
    Wenn es ein fairer Vergleich zwischen Sprachen sein soll, müssten auch make und die Build-Zeit einbezogen werden. Ich habe Java/Maven seit ein paar Jahren nicht mehr benutzt, aber als ich sah, dass der Download bei ./mvnw clean verify nach zwei Minuten immer noch lief, fiel mir wieder ein, warum

    • Java-Build-Zeiten sind sehr schnell. Was hier gerade gemessen wird, ist die Internetgeschwindigkeit
      Und als Build-Tool für inkrementelle Kompilierung ist Gradle schneller
    • Wenn man die Build-Zeit einbezieht, sollte man auch die Programmierzeit einbeziehen, und beides durch die Anzahl der Male teilen, die der Code über seine Lebensdauer ausgeführt wird
      Außerdem müsste man einen angemessenen Anteil der Zeit hinzurechnen, die es braucht, Programmieren zu lernen
      Bei solchen Challenges würde wahrscheinlich eine sehr naive Version gewinnen; das ist meiner Meinung nach nicht nur unrealistisch, sondern widerspricht auch dem Sinn der Challenge
    • Ich verstehe nicht, warum man clean ausführt
      Das ist, als würde man den Cache wegwerfen und sich dann beschweren, dass es langsam ist
    • Maven ist nicht nötig
      Es heißt, dass keine externen Abhängigkeiten verwendet werden dürfen

  • An der Technischen Universität Tschechien gab es in einem C-Kurs eine sehr ähnliche Aufgabe
    Alle Einreichungen der Studierenden wurden fortlaufend auf einer Rangliste bewertet, und viele Studierende steckten Dutzende Stunden in Optimierungen, um Zusatzpunkte für bessere Ergebnisse zu bekommen – praktisch Statuspunkte
 
dlehals2 2024-01-10

Der Erstplatzierte schafft es in 6 Sekunden … beeindruckend.