Die Herausforderung, 1 Milliarde Zeilen mit Go zu verarbeiten: Mit 9 Methoden von 1 Minute 45 Sekunden auf 4 Sekunden verkürzt

• 1BRC: eine Challenge, bei der Code geschrieben wird, der Temperaturmesswerte aus einer Textdatei mit 1 Milliarde Zeilen liest und für jede Messstation Minimum/Durchschnitt/Maximum berechnet
• Sie lief vom 1. Januar bis 31. Januar 2024, mit dem Ziel, modernes Java maximal auszureizen
• Das weckte Interesse, und viele begannen, die Aufgabe in verschiedenen Sprachen anzugehen (Rust, Go, C++, SQL)
• Detaillierte Vorstellung von 9 in Go geschriebenen Lösungen (von langsam nach schnell)

Basis-Messwerte

• Das Lesen der Textdaten mit 1 Milliarde Zeilen (13 GB) mit dem Befehl cat dauert 1,052 Sekunden.
• Der Befehl wc, der die Datei tatsächlich verarbeitet, braucht fast 1 Minute (55,710 Sekunden).
• Eine Lösung mit AWK benötigt zur Lösung des Problems 7 Minuten 35 Sekunden.

Lösung 1: Einfaches und idiomatisches Go

• Die erste Lösung mit der Go-Standardbibliothek benötigt 1 Minute 45 Sekunden.
• Die Zeilen werden mit bufio.Scanner gelesen und mit strings.Cut am Trennzeichen ';' aufgeteilt.
• Die Temperatur wird mit strconv.ParseFloat geparst, und die Ergebnisse werden mit einer Go-Map aggregiert.

Lösung 2: Map mit Pointer-Werten

• Um doppeltes Hashing in der Map zu vermeiden, wird map[string]*stats verwendet.
• Durch die Verwendung von Pointer-Werten sinkt die Laufzeit von 1 Minute 45 Sekunden auf 1 Minute 31 Sekunden.

Lösung 3: strconv.ParseFloat vermeiden

• Statt strconv.ParseFloat wird eigener Code zum Parsen der Temperatur verwendet.
• Die Laufzeit sinkt von 1 Minute 31 Sekunden auf 55,8 Sekunden.

Lösung 4: Festkomma-Ganzzahlen verwenden

• Temperaturen werden als Ganzzahlen dargestellt, um Gleitkomma-Operationen zu vermeiden.
• Die Laufzeit sinkt von 55,8 Sekunden auf 51,0 Sekunden.

Lösung 5: bytes.Cut vermeiden

• Statt den gesamten Stationsnamen zu scannen, um ';' zu finden, wird rückwärts vom Ende her geparst.
• Die Laufzeit sinkt von 51,0 Sekunden auf 46,0 Sekunden.

Lösung 6: bufio.Scanner vermeiden

• bufio.Scanner wird entfernt, und die Datei wird in großen Chunks gelesen.
• Die Laufzeit sinkt von 46,0 Sekunden auf 41,3 Sekunden.

Lösung 7: Benutzerdefinierte Hash-Tabelle

• Statt Gos eingebauter Map wird eine benutzerdefinierte Hash-Tabelle implementiert.
• Die Laufzeit sinkt von 41,3 Sekunden auf 25,8 Sekunden.

Lösung 8: Parallele Chunk-Verarbeitung

• Der einfache und idiomatische Code wird parallelisiert, wodurch die Laufzeit von 1 Minute 45 Sekunden auf 24,3 Sekunden sinkt.

Lösung 9: Alle Optimierungen plus Parallelisierung

• Alle Optimierungen werden mit Parallelisierung kombiniert, wodurch die Laufzeit von 24,3 Sekunden auf 3,99 Sekunden sinkt.

Ergebnistabelle

• Es gibt eine Tabelle zum Vergleich aller Go-Lösungen sowie der schnellsten Go- und Java-Lösungen.
• Die schnellste Go-Version verarbeitet die Daten in 2,90 Sekunden, die Java-Version in 0,953 Sekunden.
• Die Java-Version, die unter 1 Sekunde bleibt, stammt von Thomas Wuerthinger (dem Schöpfer von GraalVM), was wohl nur möglich ist, weil er auf diesem Gebiet ein Experte ist

Abschließende Anmerkungen

• Bei alltäglichen Programmieraufgaben ist einfacher und idiomatischer Code ein guter Ausgangspunkt.
• Beim Aufbau von Datenverarbeitungs-Pipelines kann 4-fach oder 26-fach schnellerer Code die Nutzerzufriedenheit steigern und Rechenkosten sparen.
• Wer eine Runtime oder einen Interpreter entwickelt, für den sind Performance-Verbesserungen besonders wichtig.

Meinung von GN⁺

• Dieser Artikel bietet eine interessante Fallstudie zur Performance-Optimierung, indem er verschiedene Methoden zur Optimierung großskaliger Datenverarbeitung mit der Go-Sprache untersucht.
• Er zeigt, dass im Optimierungsprozess die Implementierung von Datenstrukturen jenseits der Go-Standardbibliothek, etwa einer benutzerdefinierten Hash-Tabelle, eine wichtige Rolle spielt.
• Er betont die Wirkung von Parallelisierung und zeigt, wie die Kombination aus Single-Core-Optimierung und Parallelisierung beeindruckende Performance-Gewinne ermöglicht.
• Der Artikel liefert nützliche Einblicke für Softwareentwickler, die performancekritische Anwendungen entwickeln.
• Wie nützlich solche Optimierungen in einer realen Produktionsumgebung sind, kann je nach Anwendungsfall unterschiedlich sein. Nicht jede Anwendung benötigt dieses Maß an Optimierung.

[cosine20]

Mich würde interessieren, welche konkreten Arbeiten in Schritt 7 durchgeführt wurden. In diesem Abschnitt scheint die Leistungssteigerung ja enorm gewesen zu sein, haha.

[sddsdd94]

Interessant ist, dass die Zeitgewinne bei der Performance für jeden einzelnen Schritt getrennt dargestellt wurden, haha.

[galadbran]

Mit wc dauert es auch nur 1 Minute.... Wie immer gilt: Am besten ist es, gar keinen Code zu schreiben... haha

[jhbaek]

Danke fürs Teilen dieses guten Artikels. Er erinnert mich an die Zeit, als ich regelrecht besessen von Systemoptimierung war, haha.
Mit zunehmender Entwicklungserfahrung habe ich oft erlebt, dass maximal optimierter Code schwer wartbar ist und sich in einem organisatorischen Umfeld nur schwer betreiben lässt. So habe ich mich nach und nach vom Weg der Optimierung entfernt. (Plötzliche persönliche Rückschau)

[misolab]

Für die Organisation optimierter Code!!

[GN⁺]

Hacker-News-Kommentare

• Der erste Nutzer erwähnte, dass er keine Erfahrung mit Code-Optimierung für Datenmanipulation hatte und deshalb insbesondere den ersten Abschnitt interessant fand, in dem mit cat, wc usw. Basis-Messwerte ermittelt wurden. Er hielt diese Methode für einen einfachen Weg, einen „vernünftigen“ Bereich zu erhalten.
• Der zweite Nutzer erwähnte, dass die Verarbeitungszeit bei Verwendung der Polars-Bibliothek 33 Sekunden betrug, und zeigte Interesse an der einfachsten Lösung, die nahe an die schnellste manuell optimierte Lösung herankommt.
• Der dritte Nutzer sagte, dass die Performance-Analyseberichte der Go-Sprache verwirrend seien, und erklärte, dass Daten schwer vorhersagbar sein können und der Branch-Predictor falsche Vorhersagen treffen kann, wenn die Ausführungszeit einer bestimmten Codezeile nicht intuitiv erscheint.
• Der vierte Nutzer teilte sein Ergebnis bei der Durchführung der 1BRC (1 Billion Row Challenge) in Go und erwähnte, dass er Go-spezifische Optimierungstechniken gelernt habe. Dazu gehörten etwa grenzprüfungsfreie Speicherzugriffe mit unsafe.Pointer, dass Funktionen aus den Standardbibliothekspaketen bytes und bits in Assembler geschrieben sind, Einstellungen zum Deaktivieren der Garbage Collection und Methoden, Goroutinen an Threads zu binden.
• Der fünfte Nutzer behauptete, dass ein Shell-Script-Entwickler die Verarbeitung dieser speziellen 1 Milliarde Zeilen bereits abgeschlossen hätte, während sich Entwickler anderer Sprachen noch vorbereiteten.
• Der sechste Nutzer argumentierte, dass Datenbanken schneller, weniger komplex und robuster gegenüber Datenaktualisierungen seien als Anwendungscode, und betonte, dass mehr Arbeit in der Datenbank erledigt werden sollte.
• Der siebte Nutzer berichtete von seiner Erfahrung, 2010 mit PostgreSQL eine Web-App entwickelt zu haben, die 270 Millionen Zeilen an Klimadaten von Environment Canada abfragte, und dass diese Software ausgezeichnet wurde. Die App war so optimiert, dass Berichte in weniger als einer Minute erzeugt werden konnten.
• Der achte Nutzer erwähnte, dass es beeindruckend sei, dass paralleler Code in Go dennoch den idiomatischen Codestil von Go beibehält.
• Der neunte Nutzer sagte, dass awk, grep und ähnliche Tools beim Umgang mit großen Textdateien in der CLI deutlich schneller seien, wenn man Unicode-Parsing auslässt, und behauptete, dass sich die Verarbeitungszeit beim awk-Ansatz durch Hinzufügen von LC_ALL=C auf unter eine Minute reduzieren lasse.
• Der letzte Nutzer fand es interessant, dass die schnellste Java-Version schneller ist als die schnellste Go-Version, und bewertete die Leistung der Java Virtual Machine (JVM) als ziemlich gut.