HE32, Rust & "the NAND2TETRIS experience"

Motivation

Vor einem Vierteljahr habe ich das Buch “The Elements of Computing Systems” (Nisan/Schocken, wichtig: 2.Auflage!) geschenkt bekommen und die ca. 300 Seiten gleich in einem Rutsch durchgelesen. Faszinierend, insbesondere wenn ich mich an mein eher rudimentäres Verständnis meines alten Dragon-Books erinnere (dort werden im Wesentlichen die Grundlagen für die Nutzung von lex & yacc gelegt - heute: flex & bison). Ich habe damals nach ca. 3/4 des Buches aufgehört …

Das neuere Buch ist ursprünglich aus dem - in der angelsächsischen Welt - recht bekannten “Nand-to-Tetris”-Kurs entstanden.
Weitere Infos & Unterlagen können auf der zugehörigen Website abgerufen werden.

1. Der Kurs

Inhaltlich geht es in 12 Kapiteln vom NAND-Gatter bis zur einfachen “Betriebssystem”-Erstellung (die auf der Website unter “Projects” abgerufen werden).

Die ersten fünf Kapitel befassen sich mit dem Aufbau einer “eigenen” CPU, Speicherelementen etc. aus einfachsten NAND-Gattern und deren Zusammenschaltung zum “Hack”-Computer!
Kapitel 6 behandelt die Erstellung eines passenden Assemblers,
Kapitel 7 & 8 befassen sich mit der Erstellung eines Übersetzers einer eigenen VM bzw. deren “intermediate Language” (VM/IL -> Assembler)
Kapitel 9 - 11 behandeln dann die Erstellung eines Compilers für eine prozedurale aber schon objektorientierte Sprache (genannt “Jack”, übersetzt wird dann in VM-Code/IL).
Kapitel 12 erklärt, wie man ein passendes “Betriebssystem” (OS, “Operating System”) erstellt - wobei es hier eigentlich um eine Kombination von BIOS & Standard-Library geht.

Das Geniale: Der Schwierigkeitsgrad bleibt immer akzeptabel, gerade für das Selbststudium! Man merkt an vielen Stellen, wie die Rückfragen der Studenten im Laufe der Jahre in den Text zurückgeflossen sind. Praktisch alle Problemstellen (für das Verständnis) werden sehr detailliert erläutert.
Technisch werden im Software-Teil ab Kapitel 6 immer recht enge API-Vorgaben gemacht, jedoch ist man frei in der Wahl der Programmiersprache zur Realisierung (ich habe meine Lösung zeitsparend in Python erstellt - natürlich hier nicht veröffentlicht, schließlich soll sich jeder seine Lösung selbst erarbeiten!).
Mitgeliefert werden alle notwendigen Emulatoren und Hilfsmittel um die Ergebnisse mit den korrekten Lösungen automatisiert zu vergleichen (auf der Website unter “Software”).

Ich habe zwei Monate für den ganzen Kurs gebraucht. Für die ersten 10 Kapitel einen Monat, für die restlichen zwei noch einmal einen ganzen Monat (der Schwierigkeitsgrad steigt zwar kaum an, jedoch baut sich immer mehr Wissen auf, d.h. die Komplexität nimmt zu).

Meine Empfehlung: Pädagogisch wertvoll!

2. Ausführung

2.1 Hardware & Assembler

Zunächst wird im Hardware-Teil eine ISA definiert, d.h. man “baut” analog zu einer echten CPU eine Theoretische, die “Hack”-CPU mit dem “Hack”-Befehlssatz (in einer Kurs-spezifischen HDL). Diese wird im beigestellten Simulator mittels Testscript verifiziert. Das sieht dann ungefähr so aus:

Der Befehlssatz en détail:

Hierfür ist ein Assembler zu erstellen, der als Output 16-Bit Code (als “Binär-Text”) generiert, z.Bsp. wie folgt:

2.2 VM / IL

Zunächst macht man sich mit einer vordefinierten IL (Intermediate language) für eine theoretische VM (Virtual Machine) vertraut. Hierzu kann der beigestellte VM-Emulator genutzt werden:

Als nächstes wird ein Übersetzer erstellt, von VM-Code zu Assembly Language. Wenn man diesen mit dem unter 2.1 erstellten Assembler kombiniert, kann man also schon von VM-Code direkt in “Native Code” übersetzen …

2.3 Hochsprache

Als Krönung soll jetzt noch ein “echter” Hochsprachen-Compiler erstellt werden. Hierzu wird eine relativ einfache Sprache - genannt “Jack” - vorgegeben (es gibt schon ein VSC-Plugin!). Sogar Objekte können bereits angelegt werden!

Hier mal die formale Definition:

Praktisch sieht der Code z.Bsp. so aus:

Auch hierfür ist - unter Anleitung - ein Compiler zu erstellen. Dieser erzeugt aus Jack dann VM-Code:

Sieht doch gar nicht so kompliziert aus!

Wenn man jetzt diesen Compiler vor VM-Übersetzer und Assembler schaltet, hat man eine komplette Toolchain um aus Jack den Hack-Maschinencode zu erzeugen.

2.4 OS

Final erstellt man im Kurs eine Mischung aus BIOS und “Standard”-Lib (nach vorgegebenem API) - etwas großspurig als “Betriebssystem” bezeichnet.

Interessant ist zum Beispiel das Modul “Memory”. Hier schraubt man eine Speicherverwaltung selber zusammen, inkl. Garbage Collection Strategie - wirklich lehrreich!

Bei Screen- und Output-Modul befasst man sich mit Bildschirmspeicher und Character-Generierung, wie zu C64-Zeiten …

3. Ein kleines Defizit und dessen Beseitigung

3.1 Von 16-Bit zu 32-Bit Worten

Leider ist der Addressbereich des “Instruction Set” auf 15-Bits limitiert, es lassen sich also nur 32768 Speicherstellen adressieren. Für das RAM ist das zunächst egal, was wirklich kneift ist der eingeschränkte ROM-Bereich. Wenn man also gemäß 2.4 (s.o.) ein “OS” erstellt hat, kann man es nicht komplett laden, da es ca. 60K Wortcode erzeugt. Auch der mitgelieferte Emulator lehnt entsprechende Code-Mengen ab.

Könnte man da vielleicht Abhilfe schaffen? (Spoiler-Alert: Man kann!)

Wenn man den Addressbereich nur um 3 Bit erweitert könnte man 256K Worte addressieren - das müsste doch für OS und die zusätzliche eigentliche Applikation reichen?

Ich habe also alles der Einfachheit halber auf 32-Bit umgestellt, drei Bits einfach oben auf die unteren 15 Bits “aufgepfropft” und das alte Bit 15 in das Bit 31 verschoben.

Den bereits existierenden (selbstgeschriebenen) Assembler habe ich um eine Option für die Generierung von diesem 32-Bit Code erweitert.

Fehlt nur noch eine Testumgebung …

3.2 Becoming a Rustacean

Mit Kresse hab’ ich eine Wette laufen: Jedes Jahr mindestens eine neue Sprache zu lernen. Nachdem Linus Torvalds verkündet hat, das auch Rust im Linux Kernel genutzt werden darf, fand ich, das es Zeit ist hier mal nachzurüsten.

Xperimental: Mach lieber Go, Rust ist wie C++ (reichlich überladen …). Hätte ich mal auf ihn gehört!

Was mir auch nicht gleich klar war: Rust ist eine funktionale Sprache (wie Scheme, Lisp, Haskell u.ä.), es sieht nur optisch wie eine Prozedurale aus.

Bis Kapitel 17 (inkl., von insgesamt 21) habe ich mich durch das Rust-Manual vorgearbeitet, dann habe ich die Arbeit am HE32-Projekt in Rust aufgenommen (“Hack”-Emulator 32-Bit) - und bin gleich am indirekten Vector-Zugriff gescheitert (ein solideres Verständnis von “RefCell” hätte geholfen - Danke Vespasian)!
Auch hatte ich zunächst für parallele Threads geplant und vorsichtshalber eine Menge mit Arc & Mutex hantiert - überflüssigerweise & eine echte Performance-Bremse.

Weil eine neue Sprache lernen ja immer eine Unterforderung ist (💀!), habe ich mich zwecks Komplexitätssteigerung auch gleich für eine GUI-Lösung entschieden 🏋 (hier sieht man noch, das die GUI-Landschaft für Rust im Fluß ist - nach einiger Web-Recherche habe ich mich für Qt5 mit ritual entschieden).

Eigentlich soll Rust ja “sicher” im Hinblick auf Speicherzugriffe sein, schade auch, das für Qt5 dann große Teile wieder auf “unsafe” gedreht werden (müssen) 🖕 …
Wenigstens läßt sich der Timer-Event von Qt gut nutzen!
Nicht so gut funktioniert das Einklinken in die Event-Schleife zwecks Abfangen der Tastatur und Weiterreichung an die Emulation (das Symbol wird nicht richtig aufgelöst - ist zumindest nicht auffindbar?!). Daher habe ich das Modul (“crate” in Rust-Terminologie) device_query dafür genutzt. Da es so etwas wie globale Variablen nicht gibt 🤔(?) habe ich das Crate “lazy_static” ebenfalls hinzugezogen.

Nach einigen Performance-Optimierungen läuft der HE32 jetzt ganz passabel. Nur an zwei Stellen waren die System-Bibliotheken anzupassen: In Math.multiply musste die Bitzahl erhöht werden und Sys.wait musste an die neue Abarbeitungsgeschwindigkeit angepasst werden.

Die Quellen zu HE32 finden sich wie gehabt auf dem hacKNology git-server.

4. Was kann man - ganz praktisch - an Erkenntnissen gewinnen?

Der Kurs empfiehlt sich unbedingt für Ingenieure oder Naturwissenschaftler. Wer im Informatik-Studium nur die “Fertigprodukte” Flex und Bison kennengelernt hat, jedoch interessiert ist am Eigenbau, ist hier ebenfalls richtig. Ist schon ein tolles Gefühl, wenn man eine “eigene” Compiler-Toolchain gebaut hat!
Ich würde immer das Buch empfehlen als Grundlage (und die PDFs nur bei Bedarf hinzuziehen). Hier wird quasi die Vorlesung nachgeliefert.
Der Compilerbau hat seit den 80ern Fortschritte gemacht: Die Erfindung einer zwischengeschalteten VM/IL erlaubt eine deutliche Komplexitätsreduzierung, man muß eben nicht mehr direkt aus der Hochsprache Assembly-Code für die Zielplattform generieren.
Ok, schneller wird’s nicht - Performance ist allerdings heutzutage nicht mehr so das Problem.
Außerdem erlaubt das Konzept die Aufteilung in Frontend/VM/Backend - und als Frontend können dann bei Bedarf verschiedene Hochsprachen Verwendung finden, als Backend sind unterschiedliche Targets mit vertretbarem Aufwand machbar (siehe hierzu z.Bsp.: LLVM).
💡Rust: Der Verzicht auf “saubere” Mehrtaskfähigkeit beschleunigt die Abarbeitung ca. vierfach.
💡Eine CPU mit nur zwei Registern (ohne PC) muss extrem viel über den Stack abwickeln. Sowohl in der Emulation wie auch in der Realität (externer Speicherzugriff!) ist das SEHR langsam. Hier gilt also: Viel(e Register) hilft viel!

5. Ausblick

Man könnte z.Bsp. mit einer CPU mit mehr Registern (oder auch einem CPU-lokalen Teil-Stack?) experimentieren … 🤔
Ebenfalls denkbar: Höherwertige CPU-Befehle (womit wir bei der alten RISC/CISC Diskussion angekommen wären!).
Man sieht: Der Kurs macht Lust auf mehr …

VM: Ein VM-Emulator in Rust wird schneller als die derzeitige Java-Variante sein. Wenigstens ist der mitgelieferte VM-Emulator langsamer als HE32, er müsste aber eigentlich schneller sein (wg. der enorm reduzierten Anzahl höherwertiger Befehle die sich aber immer noch gut/schnell emulieren lassen).

🗣 Wenn ich ihn richtig verstanden habe, will Vespasian eine verbesserte HE32-Version gestützt auf das Tokio-Framework entwickeln (oder eine qemu-Version implementieren, die den Assembler-Code wieder auf VM-Code wandelt - oder so ähnlich?). Beides um die Performance nochmal richtig zu steigern. Ich bin gespannt …