Créer un émulateur Game Boy en OCaml (2022)

• Pour aller au-delà des exemples simples avec OCaml et l’appliquer à un code de taille intermédiaire, l’auteur a créé l’émulateur Game Boy CAMLBOY, avec pour objectif une exécution dans le navigateur et des performances suffisantes pour jouer sur smartphone
• L’implémentation repose sur la méthode de rattrapage (catch up method), qui fait suivre CPU, timer et GPU au rythme des cycles CPU, sur un bus chargé d’orienter les lectures/écritures selon l’adresse, et sur des interfaces d’accès 8 bits et 16 bits
• Pour améliorer la testabilité du CPU, l’implémentation du bus a été injectée via un foncteur, et la confusion entre arguments d’instructions a été réduite grâce aux GADT en séparant les types 8 bits et 16 bits
• Les tests d’intégration combinent des test ROM et ppx_expect pour détecter les régressions et permettre une implémentation exploratoire, tandis que l’interface navigateur est réalisée avec js_of_ocaml et Brr
• Après réduction des goulets d’étranglement liés au GPU, au timer et à Bigstringaf avec le profiler de Chrome, puis désactivation de l’inlining de js_of_ocaml, le projet a atteint 100 FPS sur navigateur PC et 60 FPS sur smartphone

---

Objectifs et périmètre de CAMLBOY

• CAMLBOY est un émulateur Game Boy écrit en OCaml et exécuté dans le navigateur
• La démo inclut plusieurs ROM homebrew, avec Bouncing ball et Rocket Man Demo recommandées
• L’objectif est d’atteindre 60 FPS même sur les navigateurs de smartphones récents
• Par la suite, une PR a aussi rendu possible l’exécution WASM basée sur js_of_ocaml
• Le dépôt est public sur linoscope/CAMLBOY

Pourquoi créer un émulateur Game Boy en OCaml

• Après avoir étudié OCaml pendant quelques mois, l’auteur savait écrire des exemples simples, mais manquait encore d’expérience pratique pour structurer du code de taille intermédiaire ou plus et utiliser des fonctionnalités avancées en situation réelle
• Un émulateur Game Boy réunissait de bonnes conditions comme projet d’entraînement
  • les spécifications sont claires, donc peu d’incertitude sur ce qu’il faut implémenter
  • c’est assez complexe pour ne pas être bouclé en quelques jours ou semaines
  • mais pas au point d’être impossible à terminer en quelques mois
  • il y avait aussi un attachement personnel au Game Boy
• L’objectif d’implémentation mettait d’abord l’accent sur la lisibilité et la maintenabilité avant la performance, tout en incluant l’exécution dans le navigateur et la comparaison via benchmarks
  • compilation en JavaScript avec js_of_ocaml pour exécuter le projet dans le navigateur
  • atteindre un nombre de FPS jouable sur navigateur mobile
  • implémenter des benchmarks et comparer plusieurs backends de compilation OCaml

Architecture de l’émulateur et boucle principale

• Les principaux composants de CAMLBOY sont le CPU, le timer, le GPU, le bus, la cartridge, le contrôleur d’interruptions, le port série, le joypad, etc.
• Le bus achemine les lectures et écritures entre le CPU et les différents modules matériels selon l’adresse
  • par exemple, une écriture à l’adresse 0xFFFF est transmise au contrôleur d’interruptions pour activer ou désactiver les interruptions
  • les modules matériels connectés au bus implémentent l’interface Addressable_intf.S
  • le bus implémente l’interface Word_addressable_intf.S
• Sur le matériel réel, le CPU, le timer et le GPU partagent la même horloge, mais l’émulateur fonctionne dans une boucle séquentielle, ce qui impose une synchronisation explicite
• La boucle principale aligne la progression des modules via la méthode de rattrapage
  • le CPU exécute une instruction et enregistre le nombre de cycles consommés
  • le timer avance du même nombre de cycles que ceux consommés par le CPU
  • le GPU avance lui aussi du même nombre de cycles

Interfaces de lecture/écriture et implémentation du bus

• Les modules prenant en charge les lectures/écritures 8 bits partagent la signature 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, etc. incluent la même interface sous la forme include Addressable_intf.S with type t := t
• Entre le CPU et le bus, des lectures/écritures 16 bits sont aussi nécessaires, donc Word_addressable_intf.S inclut Addressable_intf.S et ajoute read_word et write_word
• Le bus contient comme champs les modules connectés, tels que GPU, timer ou RAM, et transmet les lectures/écritures au module approprié en fonction de l’adresse
  • les accès à l’adresse 0xC000 sont routés vers la RAM
  • pour la carte mémoire complète, voir Pandocs Memory Map
• read_word implémente la lecture 16 bits en appelant read_byte deux fois, comme le fait aussi le matériel réel pour les accès 16 bits

Registres et amélioration de la testabilité du CPU

• Le CPU du Game Boy possède les registres 8 bits A, B, C, D, E, F, H, L
• Ces registres 8 bits peuvent être combinés en registres 16 bits AF, BC, DE, HL
• L’implémentation initiale du CPU contenait directement registers, bus, pc, etc., et run_instruction gérait fetch, decode et execute
• Cette structure était difficile à tester
  • le bus dépend de nombreux modules comme le GPU, le timer ou la RAM
  • pour créer un CPU en test unitaire, il fallait préparer le bus et tous les modules qui lui sont connectés
  • tant que le bus et tous les modules connectés n’étaient pas implémentés, il était impossible d’instancier le CPU
• Le CPU a été réécrit comme un foncteur afin d’abstraire l’implémentation concrète du bus
  • injection de l’implémentation du bus sous la forme module Make (Bus : Word_addressable_intf.S)
  • en test, le CPU est instancié avec un Mock_bus basé sur un simple tableau d’octets
  • ce changement permet d’utiliser une implémentation mock au lieu du vrai bus dans les tests unitaires du CPU

Jeu d’instructions et usage des GADT

• Le jeu d’instructions du Game Boy contient des instructions prenant des arguments 8 bits et d’autres prenant des arguments 16 bits
  • ADD8 A, 0x12 additionne le registre 8 bits A avec une valeur immédiate 8 bits
  • ADD16 AF, 0x1234 additionne le registre 16 bits AF avec une valeur immédiate 16 bits
• La première tentative représentait les arguments avec des variants comme Immediate8, Immediate16, R, RR
• Avec cette approche par variants, il était difficile de fixer un type de retour unique pour read_arg
  • R r renvoie un uint8
  • RR rr renvoie un uint16
  • les types de retour diffèrent au sein d’un même match
• Les GADT ont servi à redéfinir les types d’arguments
  • Immediate8 : uint8 -> uint8 arg
  • Immediate16 : uint16 -> uint16 arg
  • R : Registers.r -> uint8 arg
  • RR : Registers.rr -> uint16 arg
• Avec cette structure, le type de retour varie selon le type d’argument, comme dans read_arg : type a. a Instruction.arg -> a
  • ADD8 n’accepte que uint8 arg * uint8 arg
  • ADD16 n’accepte que uint16 arg * uint16 arg
  • cela réduit au niveau du type les confusions entre arguments d’instructions 8 bits et 16 bits

Cartridge et modules de première classe

• Une cartridge Game Boy ne se limite pas à une simple ROM et peut embarquer du matériel supplémentaire selon son type
• Une cartridge de type ROM_ONLY ne contient qu’une ROM stockant les données et le code du jeu
  • Tetris en est un exemple
• Une cartridge de type MBC3 contient, en plus de la ROM, de la RAM dédiée et un timer
  • Pokémon Red en est un exemple
• Comme les fonctionnalités diffèrent selon le type de cartridge, chacune a été implémentée dans un module séparé
• Pour choisir à l’exécution le module correspondant au type de cartridge, le projet utilise des modules de première classe
  • Detect_cartridge.f est conçu pour recevoir les octets de la ROM et renvoyer (module Cartridge_intf.S)

Tests d’intégration avec test ROM et ppx_expect

• Une test ROM est un programme destiné à vérifier une fonctionnalité précise de l’émulateur
  • validation du fonctionnement des instructions arithmétiques de base
  • validation de la prise en charge des cartridges de type MBC1
• Contrairement à une ROM de jeu ordinaire, une test ROM indique quelle fonctionnalité a échoué et peut souvent s’exécuter même si certaines fonctions essentielles manquent encore, ce qui en fait un outil précieux pour développer un émulateur
• Les test ROM affichent généralement leurs résultats à l’écran
  • mooneye test ROMs affiche en cas d’échec un dump des registres et les informations d’assertion échouée
  • certaines test ROM, comme blargg test roms, envoient un résultat ASCII via le port série
• Les tests d’intégration utilisent ppx_expect
  • M.run_test_rom_and_print_framebuffer exécute la ROM puis affiche l’état final de l’écran en caractères ASCII
  • la chaîne produite est comparée à la valeur attendue dans [%expect{|...|}]
  • pour une présentation de ppx_expect, voir l’article de Jane Street
• Cette configuration de test permet de détecter les régressions même lors de gros changements de code et rend possible un flux de programmation exploratoire
  • trouver une test ROM validant la nouvelle fonctionnalité
  • configurer un test ppx_expect
  • committer la sortie en échec
  • implémenter la fonctionnalité
  • vérifier que le résultat du test passe à Test OK

Compilation JavaScript et interface navigateur

• Grâce à js_of_ocaml, la compilation vers JavaScript n’a pas été difficile
• Il n’a fallu qu’un seul commit pour faire fonctionner l’émulateur dans le navigateur
• L’interface navigateur a été réalisée avec Brr
• Brr mappe les objets JS sur des modules OCaml plutôt que sur des objets OCaml
  • l’API navigateur intégrée de js_of_ocaml mappe les objets JS sur des objets OCaml, ce qui demande de connaître le système objet d’OCaml
  • utiliser Brr réduit cette charge liée au modèle objet d’OCaml

Processus d’optimisation des performances

• La première exécution dans le navigateur fonctionnait, mais était trop lente pour être réellement jouable
  • environ 20 FPS sur navigateur PC
  • comme le vrai Game Boy fonctionne à 60 FPS, il fallait multiplier les performances par environ trois
• Le profiler de Chrome a servi à identifier les goulets d’étranglement
  • le GPU consommait environ 73 % du temps
  • tile_data.ml en prenait 34 %, oam_table.ml 18 % et tile_map 8 %
  • timer.ml et certaines fonctions de Bigstringaf consommaient aussi beaucoup de temps
• La suppression progressive de ces goulets d’étranglement a fait monter les FPS étape par étape
  • optimisation de oam_table.ml : 14 FPS → 24 FPS
  • optimisation de tile_data.ml : 24 FPS → 35 FPS
  • optimisation de timer.ml : 35 FPS → 40 FPS
  • optimisation de tile_map.ml : 40 FPS → 50 FPS
  • utilisation de Bigstringaf.unsafe_get à la place de Bigstringaf.get : 50 FPS → 60 FPS
• Le projet a ensuite atteint 60 FPS sur navigateur PC, mais restait entre 20 et 40 FPS sur smartphone
• La sortie JS du build release était plus lente que celle du build dev, et avec l’aide de discuss.ocaml.org, il a été établi que l’inlining de js_of_ocaml dégradait les performances JS
  • voir la discussion sur discuss.ocaml.org
  • une mise à jour du 12 janvier 2022 précise que cet effet négatif est traité dans ocsigen/js_of_ocaml#1220
• Après désactivation de l’inlining, le projet a atteint 100 FPS sur PC et 60 FPS sur smartphone
• Les optimisations de performance côté JS ont aussi amélioré les performances natives, avec environ 1000 FPS en exécution native

Benchmarks et limites de comparaison

• Un mode de benchmark headless a été implémenté pour exécuter l’émulateur sans interface
• Les FPS ont été mesurés sur plusieurs backends de compilation OCaml
• Ce benchmark se prête mal à une comparaison directe des FPS avec d’autres émulateurs Game Boy
  • les performances d’un émulateur dépendent fortement de sa précision et de l’étendue des fonctionnalités implémentées
  • CAMLBOY n’implémente pas l’APU (Audio Processing Unit), donc comparer ses FPS avec ceux d’émulateurs gérant l’APU n’a pas beaucoup de sens

Retour d’expérience avec OCaml

• L’écosystème OCaml s’est beaucoup amélioré par rapport à la dernière utilisation de l’auteur, environ six ans plus tôt
  • grâce à dune, on se rapproche d’une expérience où il suffit de placer les fichiers dans des répertoires pour que le système de build s’en charge
  • avec Merlin et OCamlformat, la mise en place de l’autocomplétion, de la navigation dans le code et du formatage automatique est devenue globalement simple
  • en utilisant setup-ocaml, il est possible de configurer build et tests dans GitHub Actions
• L’implémentation de CAMLBOY utilise beaucoup d’état mutable pour des raisons de performance
  • de nombreux modules exposent des fonctions du type t -> ... -> unit, ce qui implique une modification d’un état mutable
  • malgré ce caractère peu « fonctionnel », l’auteur n’a pas eu l’impression de perdre les avantages d’OCaml
• Ce qu’il apprécie avant tout n’est pas tant le côté « fonctionnel » que les types statiques, les variants, le pattern matching, le système de modules et la bonne inférence de types

Ce qui a été moins agréable avec OCaml

• Même si l’écosystème a progressé, certains domaines restent complexes ou insuffisamment documentés
  • lors de la résolution des dépendances de manière reproductible, la documentation officielle d’opam manquait d’instructions claires
  • l’auteur a dû lire le code source de setup-ocaml pour trouver les bonnes commandes
  • devoir « publier » localement un package avant de pouvoir installer ce package publié localement lui a semblé compliqué
• Le coût syntaxique d’une dépendance à l’abstraction est élevé
  • pour faire dépendre B de l’interface C_intf plutôt que de l’implémentation concrète C, il faut transformer B en foncteur
  • une fois B devenu foncteur, A ne peut plus référencer B.foo comme avant et doit lui aussi devenir un foncteur recevant B_intf
  • transformer un module en foncteur modifie non seulement sa dépendance à d’autres modules, mais aussi la manière dont d’autres modules dépendent de lui
• Ce problème apparaît lorsqu’on veut isoler uniquement la partie Bus -> Cartridge dans le graphe de dépendances Camlboy -> Bus -> Cartridge
• En POO, il suffirait de faire accepter par le constructeur de la classe B une interface C_intf au lieu de la classe concrète C, sans changer le type même de B
  • la POO a toutefois un coût en dynamic dispatch
  • et les fonctionnalités objet d’OCaml sont moins familières à beaucoup de développeurs, ce qui peut restreindre le lectorat du code

Références

• Ressources OCaml
  • Learn OCaml Workshop : support d’atelier utilisé en interne chez Jane Street, basé sur l’apprentissage via du code OCaml à trous et des tests à compléter
  • Real World OCaml : ressource orientée cas pratiques recommandée à celles et ceux qui connaissent déjà la syntaxe de base d’OCaml ou ont de l’expérience dans un autre langage fonctionnel
• Ressources Game Boy
  • The Ultimate Game Boy Talk : vidéo d’environ une heure expliquant l’architecture du Game Boy
  • gbops : table du jeu d’instructions du Game Boy
  • Game Boy CPU Manual : manuel CPU utilisé pour implémenter les instructions, bien que certaines parties, notamment autour des flags de registre, soient imprécises
  • Pandocs : wiki de référence pour le fonctionnement de modules matériels comme le GPU ou le timer
  • Imran Nazar’s blog : tutoriel de création d’un émulateur Game Boy en JavaScript, utile pour estimer l’ampleur globale de l’implémentation