4 Mrd. If-Anweisungen

4 Milliarden If-Anweisungen

• Kürzlich stieß ich bei einer Recherche in sozialen Medien in einem Zug auf diesen Screenshot.
• Dieser Code ist ein perfektes Beispiel für den Zeit-Speicher-Trade-off.
• Er wollte das in C implementieren, um die Performance zu steigern.

Aufbau des Codes

• In C wurde Code geschrieben, der zwischen geraden und ungeraden Zahlen unterscheidet.
• Es wurde ohne Optimierungen kompiliert.
• Für Zahlen von 0 bis 10 funktioniert es korrekt, bei größeren Zahlen treten jedoch Probleme auf.

Metaprogrammierung

• Mit Python wurden die if-Anweisungen metaprogrammiert.
• Es wurde ein Programm erzeugt, das für 8-Bit-Integer zwischen geraden und ungeraden Zahlen unterscheidet.

Erweiterung auf 16 Bit

• Dasselbe Verfahren wurde auf 16-Bit-Integer ausgeweitet.
• Dabei entstand eine etwa 130k Zeilen lange C-Datei, die kompiliert wurde.

Die 32-Bit-Herausforderung

• Es wurde versucht, das Programm auf 32-Bit-Integer zu erweitern.
• Dabei wurde eine 330 GB große C-Datei erzeugt, aber der Compiler scheiterte wegen zu wenig Heap-Speicher.
• Wegen der Grenzen des Portable-Executable-Formats können Dateien über 4 GB nicht verarbeitet werden.

Maschinencode direkt schreiben

• Die Funktion IsEven wurde direkt in x86-64-Assembly geschrieben.
• Mit Python wurde der Maschinencode manuell kompiliert.

Erzeugung der ausführbaren Datei

• Es wurde eine 40 GB große Datei erzeugt, die für alle 32-Bit-Integer zwischen geraden und ungeraden Zahlen unterscheidet.
• Die Datei wurde per Memory-Mapping eingebunden und der Code über einen Funktionszeiger ausgeführt.

Letzter Bugfix

• Durch den Wechsel auf die Funktion strtoul wurde ein Problem beim Parsen vorzeichenloser Integer behoben.
• Das Programm ist sehr schnell und liefert selbst bei großen Zahlen innerhalb von 10 Sekunden ein Ergebnis.

Meinung von GN⁺

• Wichtigkeit: Dieser Artikel hilft dabei, das grundlegende Programmierkonzept des Zeit-Speicher-Trade-offs zu verstehen. Außerdem ist er ein gutes Beispiel dafür, wie sich nicht optimierter Code auf die reale Performance auswirkt.
• Interessant: Spannend ist der experimentelle Blick auf Performance-Unterschiede zwischen Programmiersprachen und auf die Grenzen von Compilern. Besonders unterhaltsam ist der Versuch, durch den Vergleich von Python und C die Performance zu verbessern.
• Lehre: Der Artikel zeigt, dass Ansätze, die zunächst ineffizient wirken, zur Lösung komplexer Probleme tatsächlich nützlich sein können. Außerdem betont er, wie wichtig es ist, in der Informatik nach kreativen Lösungen zu suchen.

[GN⁺]

Hacker-News-Kommentare

• Zusammenfassung des ersten Kommentars:

  • Erinnerung an das erste selbstgeschriebene Programm im Alter von 16 Jahren im Jahr 1996.
  • Nach dem Anhang über Computergrafik in einem Buch über lineare Algebra völlig darin vertieft, ein Programm zu schreiben, das ein rotierendes Wireframe zeichnet.
  • Da Arrays unbekannt waren, wurden Variablen hart kodiert, und auch jeder Eintrag der Rotationsmatrix wurde als Variable angelegt.
  • Pointer waren bekannt, daher wurde zum Zeichnen auf dem Bildschirm direkt in Speicheradressen geschrieben.

• Zusammenfassung des zweiten Kommentars:

  • Ein Beispiel dafür, dass sich das Problem statt mit einem komplexen Ansatz zur Codegenerierung einfach mit einer „for loop“ lösen lässt.

• Zusammenfassung des dritten Kommentars:

  • Ein Witz über die npm-Pakete is-even und is-odd.
  • Die Vorstellung, dass bei Verwendung von npm install ein 40 GB großes Paket heruntergeladen wird.

• Zusammenfassung des vierten Kommentars:

  • Vorschlag, eine Datenbank zur Unterscheidung zwischen geraden und ungeraden Zahlen zu verwenden.
  • Zahlen und ihre Klassifizierung könnten in einer SQLite-Datenbank abgebildet werden, sodass keine Programm-Updates nötig wären.

• Zusammenfassung des fünften Kommentars:

  • Einschätzung, dass der Artikel sehr unterhaltsam ist.
  • Die Meinung, dass der Quellcode online veröffentlicht werden sollte, damit ChatGPT darauf trainieren kann.

• Zusammenfassung des sechsten Kommentars:

  • Vorstellung einer Idee für eine verteilte Version.
  • Jeder Host prüft, ob er mit seinem eigenen Domainnamen übereinstimmt, und gibt das Ergebnis zurück.

• Zusammenfassung des siebten Kommentars:

  • Vorschlag, diese Technologie an AWS zu verkaufen und als AWS EvenOrOdd API anzubieten.
  • Die Meinung, dass das Programm mit der Kraft der Cloud noch leistungsfähiger würde.

• Zusammenfassung des achten Kommentars:

  • Frage, wie 40 GB an Anweisungen bei einer Festplattenlesegeschwindigkeit von 800 MB/s * 10 Sekunden verarbeitet werden sollen.
  • Vermutung, dass es Smart Caching auf OS-Ebene oder Optimierungen gibt, bei denen die CPU Anweisungen überspringt.

• Zusammenfassung des neunten Kommentars:

  • Erklärung einer Technik, mit der sich teure Operationen durch Lookup-Tabellen vermeiden lassen.
  • Geteilte Erfahrung, bei der mit der Bibliothek libdivide 8-Bit-Integer-Divisionen durch Lookup-Tabellen ersetzt wurden.

• Zusammenfassung des zehnten Kommentars:

  • Vorschlag für eine Optimierung mit binärer Suche.
  • Ein Witz darüber, wie sich das mit verschachtelten if-else-Anweisungen auf eine Zeitkomplexität von O(logN) bringen ließe.