Einen Game-Boy-Emulator in OCaml bauen (2022)

• Um OCaml über Beispielniveau hinaus auf mittelgroßen Code anzuwenden, wurde der Game-Boy-Emulator CAMLBOY gebaut, mit dem Ziel, im Browser zu laufen und auf Smartphones mit spielbarer Leistung zu funktionieren
• Die Implementierung besteht aus der Catch-up-Methode, bei der CPU, Timer und GPU mit den CPU-Zyklen synchronisiert werden, aus einem Bus für adressbasiertes Lese-/Schreib-Routing sowie aus 8-Bit- und 16-Bit-Zugriffsinterfaces
• Um die Testbarkeit der CPU zu erhöhen, wurde die Bus-Implementierung per Functor injiziert; Verwechslungen bei Befehlsargumenten wurden mithilfe von GADT durch die Trennung von 8-Bit- und 16-Bit-Typen reduziert
• Integrationstests kombinierten Test-ROMs mit ppx_expect, um Regressionen zu erkennen und explorative Implementierung zu ermöglichen; die Browser-UI wurde mit js_of_ocaml und Brr umgesetzt
• Nachdem mit dem Chrome Profiler Engpässe in GPU, Timer und Bigstringaf reduziert wurden, erreichte das Projekt durch das Deaktivieren des js_of_ocaml-Inlinings 100 FPS im PC-Browser und 60 FPS auf Smartphones

---

Ziele und Umfang von CAMLBOY

• CAMLBOY ist ein in OCaml geschriebener Game-Boy-Emulator, der im Browser läuft
• Die Demo enthält mehrere Homebrew-ROMs; Bouncing ball und Rocket Man Demo werden besonders empfohlen
• Ziel ist die Ausführung mit 60 FPS selbst in modernen Smartphone-Browsern
• Später wurde per PR auch eine WASM-Ausführung auf Basis von js_of_ocaml möglich
• Das Repository ist unter linoscope/CAMLBOY öffentlich verfügbar

Warum ein Game-Boy-Emulator in OCaml?

• Auch nach einigen Monaten des Lernens von OCaml ließen sich zwar einfache Beispiele schreiben, doch es fehlte das Gefühl für den praktischen Einsatz bei mittelgroßen oder größeren Codebasen und für fortgeschrittene Features
• Ein Game-Boy-Emulator erfüllte gute Bedingungen als Übungsprojekt
  • Die Spezifikation ist klar, sodass wenig Unklarheit darüber besteht, was implementiert werden soll
  • Das Projekt ist komplex genug, um nicht in ein paar Tagen oder Wochen abgeschlossen zu sein
  • Es ist aber nicht so komplex, dass es nicht in einigen Monaten fertiggestellt werden könnte
  • Es gibt eine persönliche nostalgische Verbindung zum Game Boy
• Das Implementierungsziel legte zunächst Wert auf Lesbarkeit und Wartbarkeit statt auf reine Performance und schloss Browser-Ausführung sowie Benchmark-Vergleiche ein
  • Kompilierung nach JavaScript mit js_of_ocaml für die Ausführung im Browser
  • Erreichen spielbarer FPS im Smartphone-Browser
  • Implementierung von Benchmarks und Vergleich mehrerer OCaml-Compiler-Backends

Emulator-Architektur und Main Loop

• Die Hauptbestandteile von CAMLBOY sind CPU, Timer, GPU, Bus, Cartridge, Interrupt-Controller, Serial Port, Joypad und weitere Komponenten
• Der Bus leitet zwischen CPU und verschiedenen Hardware-Modulen Lese- und Schreibzugriffe anhand der Adresse weiter
  • Ein Schreibzugriff auf Adresse 0xFFFF wird zum Beispiel an den Interrupt-Controller weitergeleitet, um Interrupts zu aktivieren oder zu deaktivieren
  • An den Bus angeschlossene Hardware-Module implementieren das Interface Addressable_intf.S
  • Der Bus selbst implementiert das Interface Word_addressable_intf.S
• In echter Hardware teilen CPU, Timer und GPU denselben Takt, im Emulator ist wegen der sequentiellen Ausführung jedoch eine separate Synchronisation nötig
• Der Main Loop nutzt die Catch-up-Methode, um den Fortschritt der einzelnen Module anzugleichen
  • Die CPU führt eine Instruktion aus und protokolliert die verbrauchte Zahl an Zyklen
  • Der Timer wird um genau diese Zahl an CPU-Zyklen weitergeführt
  • Die GPU wird ebenfalls um dieselbe Zahl an Zyklen weitergeführt

Lese-/Schreibinterfaces und Bus-Implementierung

• Module mit 8-Bit-Lese- und Schreibzugriffen teilen sich die Signatur Addressable_intf.S
  • read_byte : t -> uint16 -> uint8
  • write_byte : t -> addr:uint16 -> data:uint8 -> unit
  • accepts : t -> uint16 -> bool
• ram.mli, gpu.mli, joypad.mli, timer.mli und weitere binden dasselbe Interface in der Form include Addressable_intf.S with type t := t ein
• Zwischen CPU und Bus sind auch 16-Bit-Lese- und Schreibzugriffe nötig; daher enthält Word_addressable_intf.S das Addressable_intf.S-Interface und ergänzt read_word sowie write_word
• Der Bus besitzt Felder für angeschlossene Module wie GPU, Timer und RAM und leitet Lese- und Schreibzugriffe anhand der Adresse an das passende Modul weiter
  • Lese- und Schreibzugriffe auf Adresse 0xC000 werden an den RAM weitergereicht
  • Für die vollständige Speicherabbildung wird auf die Pandocs Memory Map verwiesen
• read_word implementiert 16-Bit-Lesezugriffe über zwei Aufrufe von read_byte; auch die reale Hardware verarbeitet 16-Bit-Zugriffe als zwei 8-Bit-Zugriffe

Register und verbesserte CPU-Testbarkeit

• Die Game-Boy-CPU besitzt die 8-Bit-Register A, B, C, D, E, F, H, L
• Diese 8-Bit-Register lassen sich zu den 16-Bit-Registern AF, BC, DE, HL kombinieren
• Die anfängliche CPU-Implementierung war eine Struktur, die registers, bus, pc und weitere Felder direkt enthielt und in run_instruction Fetch, Decode und Execute ausführte
• Diese Struktur war schwer testbar
  • Der Bus hängt von vielen Modulen wie GPU, Timer und RAM ab
  • Um in Unit-Tests eine CPU zu erzeugen, mussten auch Bus und alle angeschlossenen Module vorbereitet werden
  • Bevor Bus und alle angeschlossenen Module implementiert waren, ließ sich keine CPU-Instanz erzeugen
• Die CPU wurde deshalb als Functor neu implementiert, um die konkrete Bus-Implementierung zu abstrahieren
  • Die Form module Make (Bus : Word_addressable_intf.S) injiziert die Bus-Implementierung
  • In Tests wird die CPU mit einem einzelnen Byte-Array-basierten Mock_bus instanziiert
  • Dadurch konnten CPU-Unit-Tests statt des echten Bus eine Mock-Implementierung verwenden

Befehlssatz und Einsatz von GADT

• Der Game-Boy-Befehlssatz enthält Instruktionen mit 8-Bit-Argumenten und solche mit 16-Bit-Argumenten
  • ADD8 A, 0x12 addiert das 8-Bit-Register A und einen 8-Bit-Immediate-Wert
  • ADD16 AF, 0x1234 addiert das 16-Bit-Register AF und einen 16-Bit-Immediate-Wert
• Im ersten Versuch wurden Argumente mit Varianten wie Immediate8, Immediate16, R, RR dargestellt
• Beim Variantenansatz war es schwierig, einen einheitlichen Rückgabetyp für read_arg festzulegen
  • R r gibt uint8 zurück
  • RR rr gibt uint16 zurück
  • Innerhalb desselben match-Ausdrucks unterscheiden sich die Rückgabetypen
• Mithilfe von GADT wurden die Argumenttypen neu definiert
  • Immediate8 : uint8 -> uint8 arg
  • Immediate16 : uint16 -> uint16 arg
  • R : Registers.r -> uint8 arg
  • RR : Registers.rr -> uint16 arg
• In dieser Struktur kann der Rückgabetyp von read_arg abhängig vom Argumenttyp variieren, etwa in read_arg : type a. a Instruction.arg -> a
  • ADD8 akzeptiert nur uint8 arg * uint8 arg
  • ADD16 akzeptiert nur uint16 arg * uint16 arg
  • Verwechslungen zwischen 8-Bit- und 16-Bit-Instruktionsargumenten lassen sich damit auf Typebene reduzieren

Cartridge und First-Class Modules

• Eine Game-Boy-Cartridge ist nicht nur einfaches ROM, sondern kann je nach Typ zusätzliche Hardware enthalten
• Der Cartridge-Typ ROM_ONLY enthält nur ROM mit Spieldaten und Code
  • Als Beispiel wird Tetris genannt
• Der Cartridge-Typ MBC3 enthält zusätzlich zum ROM eigenständigen RAM und einen Timer
  • Als Beispiel wird Pokémon Red genannt
• Da sich die Funktionalität je nach Cartridge-Typ unterscheidet, wurde jeder Typ als eigenes Modul implementiert
• Um zur Laufzeit das zum Cartridge-Typ passende Modul auszuwählen, wurden First-Class Modules verwendet
  • Detect_cartridge.f ist so entworfen, dass es ROM-Bytes annimmt und (module Cartridge_intf.S) zurückgibt

Integrationstests mit Test-ROMs und ppx_expect

• Test-ROMs sind Programme, die bestimmte Funktionen des Emulators überprüfen
  • Überprüfung grundlegender arithmetischer Instruktionen
  • Überprüfung der Unterstützung für den Cartridge-Typ MBC1
• Im Gegensatz zu normalen Spiele-ROMs zeigen Test-ROMs an, in welchem Bereich eine Funktion fehlschlägt, und können auch dann laufen, wenn einige Kernfunktionen noch fehlen, was sie für die Emulator-Entwicklung nützlich macht
• Test-ROMs geben ihre Ergebnisse meist auf dem Bildschirm aus
  • Die mooneye test ROMs zeigen bei Fehlern Register-Dumps und Informationen zu fehlgeschlagenen Assertions an
  • Es gibt auch Test-ROMs wie die blargg test roms, die ASCII-Ergebnisse über den Serial Port ausgeben
• Für Integrationstests wurde ppx_expect verwendet
  • M.run_test_rom_and_print_framebuffer führt ein ROM aus und gibt den finalen Bildschirmzustand als ASCII-Zeichen aus
  • Der Ausgabestring wird mit dem Erwartungswert in [%expect{|...|}] verglichen
  • Zur Erklärung von ppx_expect wird auf den Jane-Street-Beitrag verwiesen
• Dieses Test-Setup fängt auch bei großen Codeänderungen Regressionen ab und ermöglicht einen explorativen Programmierfluss
  • Ein Test-ROM für die Verifikation einer neuen Funktion suchen
  • Einen ppx_expect-Test einrichten
  • Die fehlschlagende Ausgabe committen
  • Die Funktion implementieren
  • Prüfen, ob das Testergebnis zu Test OK wechselt

JavaScript-Kompilierung und Browser-UI

• Dank js_of_ocaml war die Kompilierung nach JavaScript nicht besonders schwierig
• Damit der Emulator im Browser läuft, war ein einzelner Commit nötig
• Für die Umsetzung der Browser-UI wurde Brr verwendet
• Brr mappt JS-Objekte nicht auf OCaml-Objekte, sondern auf OCaml-Module
  • Die eingebauten Browser-APIs von js_of_ocaml mappen JS-Objekte auf OCaml-Objekte, wodurch Kenntnisse des OCaml-Objektmodells nötig sind
  • Die Nutzung von Brr reduziert die Hürde rund um das OCaml-Objektmodell

Performance-Optimierung

• Die anfängliche Browser-Ausführung funktionierte, war aber zu langsam zum vernünftigen Spielen
  • Im PC-Browser wurden etwa 20 FPS erreicht
  • Da ein echter Game Boy mit 60 FPS läuft, musste die Performance etwa verdreifacht werden
• Mit dem Chrome Profiler wurden Engpässe gefunden
  • Die GPU verbrauchte etwa 73 % der Zeit
  • tile_data.ml verbrauchte 34 %, oam_table.ml 18 % und tile_map 8 %
  • Auch timer.ml und einige Bigstringaf-Funktionen verbrauchten viel Zeit
• Die Beseitigung dieser Engpässe erhöhte die FPS schrittweise
  • oam_table.ml optimiert: 14 FPS → 24 FPS
  • tile_data.ml optimiert: 24 FPS → 35 FPS
  • timer.ml optimiert: 35 FPS → 40 FPS
  • tile_map.ml optimiert: 40 FPS → 50 FPS
  • Bigstringaf.get durch Bigstringaf.unsafe_get ersetzt: 50 FPS → 60 FPS
• Danach wurden im PC-Browser 60 FPS erreicht, auf Smartphones lag die Leistung jedoch weiterhin nur bei 20 bis 40 FPS
• Die JS-Ausgabe des Release-Builds war langsamer als die des Dev-Builds; mit Hilfe von discuss.ocaml.org wurde festgestellt, dass Inlining in js_of_ocaml die Ursache der schlechteren JS-Performance war
  • Die zugehörige Diskussion findet sich im Beitrag auf discuss.ocaml.org
  • Ein Update vom 12. Januar 2022 behandelt die negativen Effekte in ocsigen/js_of_ocaml#1220
• Nach dem Deaktivieren des Inlinings wurden 100 FPS auf dem PC und 60 FPS auf Smartphones erreicht
• Die Optimierungen der JS-Performance verbesserten auch die native Performance; nativ läuft der Emulator mit rund 1000 FPS

Benchmarks und Grenzen von Vergleichen

• Es wurde ein Headless-Benchmarking-Modus implementiert, der den Emulator ohne UI ausführt
• Die FPS wurden über mehrere OCaml-Compiler-Backends hinweg gemessen
• Dieser Benchmark eignet sich nur eingeschränkt für FPS-Vergleiche mit anderen Game-Boy-Emulatoren
  • Die Emulator-Performance hängt stark von Genauigkeit und Umfang der implementierten Funktionen ab
  • CAMLBOY implementiert keine APU (Audio Processing Unit), daher ist ein FPS-Vergleich mit Emulatoren mit APU-Unterstützung wenig aussagekräftig

Erfahrungen mit OCaml

• Das OCaml-Ökosystem hat sich im Vergleich zu vor etwa sechs Jahren deutlich verbessert
  • Dank dune fühlt es sich eher so an, als würde man Dateien einfach in Verzeichnisse legen und das Build-System erledigt den Rest
  • Mit Merlin und OCamlformat lassen sich Autovervollständigung, Code-Navigation und automatische Formatierung meist leicht einführen
  • Mit setup-ocaml können Build und Tests in GitHub Actions eingerichtet werden
• Bei der Implementierung von CAMLBOY wurde aus Performance-Gründen viel mutable state verwendet
  • Viele Module besitzen Funktionen vom Typ t -> ... -> unit, was Änderungen an einem mutable state bedeutet
  • Trotz dieser nicht besonders „funktionalen“ Implementierung ging das Gefühl für die Vorteile von OCaml nicht verloren
• Der bevorzugte Punkt liegt weniger im „Funktionalen“ selbst als vielmehr bei statischen Typen, Varianten, Pattern Matching, dem Modulsystem und guter Typinferenz

Unbequeme Punkte in OCaml

• Trotz der Verbesserungen bleibt das Ökosystem in manchen Bereichen komplex oder unzureichend dokumentiert
  • Bei der reproduzierbaren Auflösung von Abhängigkeiten fehlte in der offiziellen opam-Dokumentation eine klare Anleitung
  • Um die nötigen Befehle zu finden, wurde der Quellcode von setup-ocaml gelesen
  • Der Ansatz, ein Paket lokal zu „publishen“ und danach dieses lokal publizierte Paket zu installieren, wirkte unnötig kompliziert
• Die syntaktischen Kosten abstraktionsorientierter Abhängigkeiten sind hoch
  • Damit B nicht von der konkreten Implementierung von C, sondern vom Interface C_intf abhängt, muss B in einen Functor umgewandelt werden
  • Sobald B ein Functor ist, kann A nicht mehr wie bisher B.foo referenzieren; daher muss auch A in einen Functor umgewandelt werden, der B_intf annimmt
  • Wenn ein Modul zu einem Functor wird, ändert sich nicht nur, wie dieses Modul von anderen Modulen abhängt, sondern auch, wie andere Module von ihm abhängen
• Dieses Problem trat auf, als im Abhängigkeitsgraphen Camlboy -> Bus -> Cartridge nur der Teil Bus -> Cartridge entkoppelt werden sollte
• In OOP kann der Konstruktor der Klasse B so geändert werden, dass er statt der konkreten Klasse C ein Interface C_intf annimmt, ohne dass sich der Typ der Klasse B selbst verändert
  • Dafür gibt es in OOP allerdings die Kosten von Dynamic Dispatch
  • Außerdem sind viele mit den OOP-Features von OCaml nicht vertraut, was die potenzielle Leserschaft des Codes einschränken kann

Referenzen

• Materialien zu OCaml
  • Learn OCaml Workshop: Workshop-Material, das intern bei Jane Street verwendet wurde und OCaml über das Ausfüllen lückenhafter OCaml-Codebeispiele samt Tests vermittelt
  • Real World OCaml: empfehlenswertes praxisnahes Material für Menschen, die die Grundsyntax von OCaml kennen oder Erfahrung mit anderen funktionalen Sprachen haben
• Materialien zum Game Boy
  • The Ultimate Game Boy Talk: Video, das die Game-Boy-Architektur in etwa einer Stunde erklärt
  • gbops: Tabelle des Game-Boy-Befehlssatzes
  • Game Boy CPU Manual: CPU-Handbuch, das bei der Implementierung der Instruktionen verwendet wurde; manche Teile, besonders rund um Register-Flags, sind ungenau
  • Pandocs: Wiki als Referenz für das Verhalten von Hardware-Modulen wie GPU und Timer
  • Imran Nazar’s blog: Tutorial zur Implementierung eines Game-Boy-Emulators in JavaScript, das half, den groben Implementierungsumfang abzuschätzen