4 Milliarden `if`-Anweisungen
(andreasjhkarlsson.github.io)- Eine spielerische Idee, die Erkennung von gerade/ungerade nur durch Auflisten von Vergleichsanweisungen und ohne
%umzusetzen, wurde von 8 Bit auf 32 Bit ausgedehnt und legte dabei die Grenzen von Compilern und ausführbaren Dateiformaten offen - Mit einem Python-Codegenerator wurden
if (number == n)-Zeilen automatisch erzeugt; der 8-Bit- und 16-Bit-Bereich funktionierte, bei 32 Bit explodierte die Zahl der Vergleichsziele jedoch auf rund 4,2 Milliarden - Die 32-Bit-C-Version erzeugte nach 48 Stunden eine etwa 330 GB große C-Datei, und MSVC scheiterte beim Kompilieren an der Zeilennummerngrenze und mangelndem Heap-Speicher
- Um die 4-GB-Beschränkung von PE-Dateien zu umgehen, wurden x86-64-Instruktionen direkt erzeugt und daraus die 40-GB-Binärdatei
isEven.bingebaut, die unter Windows per Memory Mapping wie ausführbarer Code aufgerufen wurde - Das finale Programm erkannte nach dem Wechsel von
atoizustrtoulauch große 32-Bit-Werte korrekt; große Eingaben lieferten auf einem System mit Core i5 12600K, 32 GB RAM und M.2-SSD in etwa 10 Sekunden ein Ergebnis
Gerade/Ungerade nur mit Vergleichsanweisungen bestimmen
- Der Ausgangspunkt war ein Code-Screenshot aus sozialen Medien, der das klassische Problem der Gerade/Ungerade-Erkennung ohne Modulus-Operation lösen wollte
- Für jede Zahl gibt es ein
if (number == n), das mitprintfausgibt, ob diese Zahl gerade oder ungerade ist - Das erste C-Beispiel verwendete
uint8_t number = atoi(argv[1]);und schrieb die Vergleichsanweisungen von 0 bis 10 von Hand - Es wurde mit
/Odohne Optimierung kompiliert, damit der Compiler den Algorithmus nicht verändert0,4ergabeneven3,7ergabenodd50,11,99erzeugten gar keine Ausgabe
- Der Grund war, dass es nach dem letzten
ifkeine weitere Vergleichsanweisung mehr gab, also wurden mehr if-Anweisungen benötigt
if-Anweisungen mit Python erzeugen
- Statt alle Vergleichsanweisungen von Hand zu schreiben, wurde ein Metaprogramming-Ansatz genutzt, bei dem Python den C-Code ausgibt
- Das Python-Skript erzeugt mit
for i in range(2**8)Vergleichsanweisungen für 0 bis 255- Wenn
i % 2 == 0, dannprintf("even\n"); - sonst
printf("odd\n");
- Wenn
- Das erzeugte C-Programm funktionierte über den gesamten 8-Bit-Bereich
99warodd50wareven240wareven241warodd
Bis 16 Bit klappt es noch mit C-Kompilierung
- Dasselbe Verfahren wurde mit
uint16_tundrange(2**16)auf 16 Bit erweitert - Die erzeugte C-Datei hatte etwa 130.000 Zeilen
- Nach dem Kompilieren mit MSVC funktionierte das Programm für verschiedene Werte korrekt
21000wareven3475warodd3warodd65001warodd65532wareven
- Die ausführbare Datei war etwa 2 MB groß, was auf einem PC mit 31,8 GB RAM kein Problem war
32-Bit-C-Datei und Compiler-Grenzen
- Das nächste Ziel war, mit
uint32_tundrange(2**32)den gesamten 32-Bit-Bereich per Vergleichsanweisungen abzudecken - 32 Bit enthalten 65.536-mal mehr Zahlen als 16 Bit
- Nach 48 Stunden Laufzeit des Python-Generators entstand eine etwa 330 GB große C-Datei
- Die Kompilierung mit MSVC stieß schnell an Grenzen
warning C4049: Der Compiler erreichte die Grenze für Zeilennummern und stellte die Ausgabe von Zeilennummern ein- Die Zeilennummerngrenze liegt bei
16777215 fatal error C1060: compiler is out of heap space
- Auch das Portable-Executable-Format(.exe) unter Windows hat praktisch die Einschränkung, nur schwer über 4 GB hinauszugehen; damit war der C-Kompilierungsweg, über 4 Milliarden Vergleiche in eine ausführbare Datei zu packen, blockiert
- In diesem Zusammenhang wurde die Beschränkung der maximalen PE-Dateigröße erwähnt
Maschinencode direkt erzeugen und ausführen
- Um die Grenzen von Compiler und ausführbarem Dateiformat zu umgehen, wurde auf ein Verfahren umgestellt, das x86-64-Instruktionen direkt als Binärdaten ausgibt
- Die Zielfunktion hatte die Form
IsEven, nahm ihr Argument inECXentgegen und lieferte den Rückgabewert inEAXXOR EAX, EAXsetzt den Standard-Rückgabewert für ungerade Zahlen auf 0- Für jede Zahl folgt
CMP ECX, i - Bei geraden Zahlen:
INC EAXund dannRET - Bei ungeraden Zahlen: direkt
RET
- Verwendet wurden x86-64 assembly und opcode; nach den Opcodes der einzelnen Instruktionen wurde ChatGPT gefragt
- Das Python-Skript öffnet
isEven.binals Binärdatei und schreibt Vergleichsinstruktionen für alle Zahlen von 0 bis2**32 - 1 - Die erzeugte
isEven.binwar etwa 40 GB groß und enthielt die rund 4,2 Milliarden Vergleiche, die für den vollständigen 32-Bit-Zahlenraum nötig sind
40-GB-Code per Windows-Memory-Mapping aufrufen
- Das Host-C-Programm öffnet
isEven.binund mappt die Datei per Windows-API in den Speicher, statt sie komplett einzulesen - Der Ablauf war wie folgt
CreateFileA, umisEven.binmitGENERIC_READ | GENERIC_EXECUTEzu öffnenGetFileSizeEx, um die 64-Bit-Dateigröße zu prüfenCreateFileMappingmitPAGE_EXECUTE_READMapViewOfFile, um ein ausführbares und lesbares Mapping zu erzeugen- Den gemappten Zeiger zu
int (*isEven)(int)casten und aufrufen
- Dieses Verfahren behandelt die 40-GB-Datei so, als wäre sie bereits im Speicher vorhanden, und überlässt die tatsächliche Bereitstellung dem virtuellen Speicher des Betriebssystems
- Im ersten Test funktionierte fast alles korrekt, aber bei
4200000000kam fälschlichoddheraus - Die Ursache war, dass
atoigroße unsigned-Werte nicht korrekt verarbeitet; nach dem Wechsel zustrtoul(argv[1], NULL, 10)ergab4200000000evenund4200000001odd
Beobachtungen zur Performance
- Kleine Zahlen lieferten sofort ein Ergebnis, und selbst große Zahlen nahe der
2^32-Grenze kamen in etwa 10 Sekunden zurück - Die Testumgebung bestand aus einem Core i5 12600K, 32 GB RAM und einer M.2-SSD
- Die beobachtete maximale SSD-Lesegeschwindigkeit während der Berechnung lag bei etwa 800 MB/s
- Dass selbst beim Lesen von 40 GB Daten von der Platte, beim Mapping in den physischen Speicher und bei kaum nutzbaren CPU-Cache-Vorteilen noch diese Geschwindigkeit erreicht wurde, blieb als überraschendes Ergebnis stehen
1 Kommentare
Meinungen auf Hacker News
Ich wünschte, ich hätte noch eines meiner frühen Programme. 1996, mit 16, sah ich im Anhang eines Lineare-Algebra-Buchs den Abschnitt über Computergrafik und war, mit der Programmierung, die ich im vorherigen Semester gelernt hatte, völlig versessen darauf, ein Programm zu schreiben, das rotierende Wireframes einiger Formen zeichnete.
Deswegen wäre ich im Unterricht fast durchgefallen; damals kannte ich noch keine Arrays, daher waren alle Eckpunkte und Elemente der Rotationsmatrix jeweils hartcodierte Variablen, und auch die Matrixmultiplikation bestand aus langen Listen von Rechenausdrücken, die ich ohne Schleifen für jeden Eckpunkt kopieren und anpassen musste.
Um etwas auf den Bildschirm zu zeichnen, musste man ab einer bestimmten Adresse in den Speicher schreiben, also kannte ich Pointer, und es gab eine Schleife zum Rastern der Linien zwischen den Eckpunkten. Letztlich hatte ich also das Konzept von Arrays und Indizierung schon im Kopf, wusste nur nicht, wie man sie direkt verwendet.
(x1,y1)bis(x4,y4)schreiben zu müssen.Ich sagte meinem Vater, ich wolle in einer
for-Schleife so etwas wiexn,ynverwenden, wobeinangibt, welcher Geist gemeint ist; daraufhin holte er ein BASIC-Buch hervor und zeigte mir, dassx(n)tatsächlich funktioniert.Daran muss ich denken, wenn es um Bildung geht. Abstrakte Konzepte werden am besten verstanden, wenn Lernende wirklich Bedarf daran haben; etwas, das sie den ganzen Tag nur verständnislos anstarren, kann in Sekunden oder Minuten einrasten, wenn es ihr eigenes Problem löst.
Ich hatte keinen Informatik-Hintergrund, las die Datei auf die dümmstmögliche Weise ein, und wegen verschachtelter Schleifen bekam ich ständig Fehler wegen Speicherverbrauchs und Platzmangels. Also setzte ich überall, wo es ging,
$variable = nullein, und tatsächlich lief es dann.print,input,ifundgotoselbst beigebracht hatte, war die erste GWBasic-Funktion, die ich mit Hilfe von jemand anderem lernte,chain.Das wirkt viel zu over-engineered. Ich verstehe nicht, warum man dafür Code generiert; das lässt sich mit einer einfachen
for-Schleife lösen.In
isOddwiederholt man von0bisneinfachodd = !oddund gibt das Ergebnis zurück.Playground-Link: https://go.dev/play/p/8TIfzGrdWDF
Ich habe es noch nicht profiliert, aber nach Bauchgefühl und Branchenerfahrung ist das schnell.
n == 0,falsezurückgeben; bei positiven Zahlen!isOdd(n-1), bei negativen!isOdd(n+1).Der Assembler sieht etwa so aus:
testq %rdi, %rdi,setg %al,andb %dil, %al,retq.Wenn man neben dem Build auf
...klickt, kann man den Assembler sehen: https://play.rust-lang.org/?version=stable&mode=release&edit...Leider scheint der Go Playground keine Assembler-Ausgabe zu unterstützen.
isEven(n int64) bool { return !isOdd(n) }n = unendlichist, läuft es unendlich weiter.Dieser Ansatz passt perfekt zu dem npm-Paket is-even[1] mit 196.023 wöchentlichen Downloads oder dem npm-Paket is-odd[2] mit 285.501 wöchentlichen Downloads. Es wäre doch großartig, wenn man
npm installeingibt und dann ein 40-GB-is-even und ein 40-GB-is-odd heruntergeladen werden[1] https://www.npmjs.com/package/is-even
[2] https://www.npmjs.com/package/is-odd
node_modules-Verzeichnisse gelangen wollteAuch
ansi-colorsbesteht nicht nur aus einem Gesamtpaket für Farben, sondern hat Pakete pro Farbe, und daneben gibt es noch allen möglichen anderen Kram. Weil solche Dinge in CLI-Tools oder plausibel wirkende Pakete hineingeraten und sich gegenseitig referenzieren, kann auch ein echtes Projekt allein durch eine harmlos wirkende Abhängigkeit Dutzende jonschlinkert-Pakete hereinziehen[1] https://www.npmjs.com/~jonschlinkert
Nach
var isOdd = require('is-odd');kommt nur nochmodule.exports = function isEven(i) { return !isOdd(i); };Wenn es in JS wirklich mühsam ist festzustellen, ob ein Wert vom Typ Zahl ist, könnte dieses Paket sinnvoll sein, aber es müsste doch ein allgemeineres Paket geben, das auch andere eingebaute Typen abdeckt
Allerdings behandelt isNumber auch Strings, die in Zahlen umgewandelt werden können, als Zahlen, was zu merkwürdigen Ergebnissen führen kann. Zum Beispiel ist
const a = '1'; isNumber(a); // true, aberconst b = a + a;wird zum String'11'Natürlich ist es die übliche JS-Dummheit, dass
2*azu2wird und sowohl1+'1'als auch'1'+1jeweils'11'ergeben, aber deshalb kann die Antwort,'1'sei eine Zahl, eben falsch sein. Dieses Paket wurde letzte Woche jedoch 46 Millionen Mal heruntergeladen, und nur weil Weihnachten war, war der Wert niedrig; in den Wochen davor lag der Durchschnitt eher bei etwa 70 Millionen. Wie bei unserem Projekt dürfte es meistens als Abhängigkeit mitkommennullexportiert, dabei aber 400 MB Speicher verbraucht; aus irgendeinem Grund wurde es auf HN geflaggt[2]Mit 41 GitHub-Sternen und 100 % Testabdeckung[3] war es eindeutig produktionsreif
[1]: https://github.com/mickael-kerjean/nulll
[2]: https://news.ycombinator.com/item?id=17072675
[3]: https://github.com/mickael-kerjean/nulll/blob/master/test.js
u32, sondern f64, also reicht das nicht. Selbst wenn man nur den sicheren Integer-Bereich unterstützt, sind das2⁵⁴, also mehr als 4 Millionen Mal größer als2³²Die Größe des Maschinencodes dürfte pro Branch nur um 4 Byte wachsen, also um etwa 40 %, womit man grob bei 224 Exbibyte landet. Und das auch nur, wenn man die letzten 10 Bit faul überspringt
Wenn man es richtig macht, müsste man das vielleicht noch mit 1.000 multiplizieren; über NaN-Muster habe ich nicht gründlich nachgedacht, also könnte es auch etwas weniger sein. Mit Unterstützung für
bigintwäre es vielleicht einfach unendlichIch weiß nicht, warum man das überhaupt so machen sollte. Genau für so etwas wurden Datenbanken erfunden. Man speichert einfach das Mapping von Zahlen auf die Klassifizierung
even/oddin einer SQLite-DatenbankDieser Ansatz hat außerdem den Vorteil, dass man das Programm nicht jedes Mal aktualisieren muss, wenn sich die Klassifizierung einer Zahl von ungerade zu gerade ändert
Das einzige Problem könnte sein, wenn TLS selbst von einer Gerade-/Ungerade-Funktion abhängt, aber vermutlich ist das nicht der Fall
even_or_oddund gibt ihr Spalten wieis_odd,is_even,is_zero,is_one,is_two,is_three.1trägt man alsis_odd,is_oneein,2alsis_even,is_twoDas hilft auch bei der Datenportabilität und hält alles in einem menschenlesbaren Format, falls man es von Hand prüfen muss
Einer der lustigsten Beiträge, die ich hier gelesen habe. Man sollte den Source Code online stellen, damit ChatGPT daraus „lernen“ kann
/* Copyright 2023. All unauthorized distribution of this source code will be persecuted to the fullest extent of the law*/Wer könnte es jemandem verdenken, bei so elegantem Code?
Ich verstehe den Witz überhaupt nicht. Dass jemand so etwas baut, sei mal dahingestellt, aber die derzeit 1198 Upvotes irritieren mich
Eine Lookup-Tabelle für berechenbare Werte ist weder neu noch ein Witz. Sie ist eine reale Lösung für den Zeit-/Speicher-Trade-off, und der Autor weiß das auch
Das Problem selbst ist absurd, aber sehr primitiv, daher gab es keinen Zweifel, dass es machbar ist; abgesehen von der Beobachtung, dass er ein 40-GB-Programm auf seinem Rechner etwa 10 Sekunden lang verarbeitet hat, gab es auch keine echten Messungen
Was haben wir also gelernt? Dass exe-Dateien nicht größer als 4 GB sein können? Dass ein Programm mit
2^32ifs etwa 300 GB groß ist? Ich weiß nicht, warum 1198 Leute das interessant fandenAnders als „Hexing the technical interview“ oder SIGBOVIK-Artikel wirkt das hier nicht verrückt, sondern einfach sinnlos
Es war so extrem, dass kein Compiler damit klarkam, nicht einmal ein bekannter Assembler. Also musste er direkt ein Maschinencode-Binary erzeugen, damit es funktioniert, und es funktioniert tatsächlich. Wahnsinn
Jedes einzelne
ifwürde der Reihe nach darauf geprüft, ob es zur Eingabe passt, und die Ausgabe des Originalprogramms, dass es bei kleinen Zahlen viel schneller fertig ist, stützt das. Kleine Zahlen stehen nämlich weiter vorn im CodeBei einer
switch-Anweisung mit 4 Milliardencases würde ich dagegen erwarten, dass sie zu irgendeiner Lookup-Tabelle kompiliert wird. Allerdings weiß ich nicht, wie der ohne Optimierung kompilierte Code aussieht, wenn der Datentyp eine unsigned Integer istErstaunliche Technologie. Man sollte sie an AWS verkaufen, damit sie sie allen, die keine 40-GB-Executables richtig hosten können, als Enterprise-ready AWS EvenOrOdd API anbieten
Mit der Kraft der Cloud wäre dieses Programm nicht aufzuhalten
Mich wundert, dass niemand dazwischengegrätscht ist bei der Behauptung, das Programm habe 40 GB an Instruktionen nur mit etwa 800 MB/s * 10 Sekunden Plattenlesen „verarbeitet“
Ich vermute, da ist irgendein cleveres Caching auf Betriebssystemebene im Spiel; dann hieße das aber, dass der Benchmark mit
nnahe2^32nicht wirklich korrekt ausgeführt wurdeOder die CPU ist vielleicht schlau genug, um Millionen Instruktionen vorauszuspringen
Zuerst dachte ich, die Rechnung müsse falsch sein, aber grob überschlagen wirkt es ziemlich plausibel. Die Zahlen sind außerdem alle vage gerundet, und der Eingabewert war auch nicht das absolute Maximum, sondern nur ein hoher Wert
ifs sindSie weiß nicht, ob dieser Code geordnet ist, eindeutig ist oder überhaupt gültige Instruktionen sind. Theoretisch könnte man während der Programmausführung irgendein
ifin eine Endlosschleife ändern. Das Betriebssystem würde das zwar nicht erlaubenIch bin wirklich neugierig. Ein lineares Zugriffsmuster hilft sicher, aber 800 MiB/s?
mmapeingebunden wird, belegen ungenutzte Pages nur Page-Table-Einträge und werden nicht geladen. Tatsächlich geladen werden nur die Pages, zu denen direkt gesprungen wird. Ein sauberer TrickDas vorausschauende Genie Ross van der Gussom ist jetzt mein liebstes Fabelwesen
Ich empfehle diesen Artikel: https://cerfacs.fr/coop/fortran-vs-python
Der ganze Text fühlt sich wie eine Allegorie auf LLM-Entwicklung an. Ein Kritiker würde wohl sagen: enorme Ressourcen und „Trainingsdaten“ aufwenden, um die Lösung zu „memorieren“
Ich frage mich, ob das die Absicht des Autors war
for-Schleife ausführt. Diese Allegorie fühlt sich wie die eigentliche Motivation des Textes an, und es wirkt weniger wie ein Engineering-Thema als wie ein Text über den unmittelbar bevorstehenden Irrsinn