Crear un emulador de Game Boy en OCaml (2022)

• Se creó CAMLBOY, un emulador de Game Boy, para aplicar OCaml más allá del nivel de ejemplos a código de tamaño mediano, con el objetivo de ejecutarlo en el navegador y lograr rendimiento jugable en smartphones
• La implementación se compone del catch up method, que hace que CPU, timer y GPU se pongan al día según los ciclos de CPU; un bus encargado de enrutar lecturas y escrituras por dirección; e interfaces de acceso de 8 y 16 bits
• Para mejorar la capacidad de prueba de la CPU, la implementación del bus se inyectó como functor, y la confusión entre argumentos de instrucciones se redujo separando tipos de 8 y 16 bits con GADT
• Las pruebas de integración combinaron test ROMs con ppx_expect para detectar regresiones y permitir una implementación exploratoria; la UI del navegador se implementó con js_of_ocaml y Brr
• Tras reducir cuellos de botella en GPU, timer y Bigstringaf con Chrome profiler, y luego desactivar el inlining de js_of_ocaml, se alcanzaron 100 FPS en navegador de PC y 60 FPS en smartphones

---

Objetivos y alcance de CAMLBOY

• CAMLBOY es un emulador de Game Boy escrito en OCaml que se ejecuta en el navegador
• La demo incluye varias ROM homebrew, y se recomiendan Bouncing ball y Rocket Man Demo
• También apunta a ejecutarse a 60 FPS en navegadores de smartphones modernos
• Más adelante, mediante un PR, también pasó a ser posible la ejecución en WASM basada en js_of_ocaml
• El repositorio está publicado en linoscope/CAMLBOY

Por qué crear un emulador de Game Boy en OCaml

• Después de estudiar OCaml durante algunos meses, era posible escribir ejemplos simples, pero faltaba experiencia práctica para organizar código de tamaño mediano o mayor y usar funciones avanzadas en casos reales
• Un emulador de Game Boy reunía condiciones adecuadas como proyecto de práctica
  • La especificación es clara, así que hay poco margen para dudar sobre qué implementar
  • Es lo bastante complejo como para no terminarse en unos días o semanas
  • No es tan excesivamente complejo como para no poder completarse en unos meses
  • Hay recuerdos personales asociados a la Game Boy
• El objetivo de implementación puso primero la legibilidad y mantenibilidad, antes que el rendimiento, e incluyó ejecución en navegador y comparaciones de benchmarks
  • Compilar a JavaScript con js_of_ocaml para ejecutarlo en el navegador
  • Alcanzar FPS jugables en navegadores de smartphones
  • Implementar benchmarks y comparar varios backends del compilador de OCaml

Estructura del emulador y loop principal

• Los componentes principales de CAMLBOY se dividen en CPU, timer, GPU, bus, cartridge, interrupt controller, serial port, joypad, entre otros
• El bus enruta lecturas y escrituras entre la CPU y varios módulos de hardware según la dirección
  • Por ejemplo, una escritura en la dirección 0xFFFF se envía al interrupt controller para activar o desactivar interrupciones
  • Los módulos de hardware conectados al bus implementan la interfaz Addressable_intf.S
  • El bus implementa la interfaz Word_addressable_intf.S
• En el hardware real, CPU, timer y GPU comparten el mismo reloj, pero el emulador usa un loop de ejecución secuencial, por lo que requiere sincronización aparte
• El loop principal ajusta el avance de cada módulo mediante el catch up method
  • La CPU ejecuta una instrucción y registra cuántos ciclos consumió
  • El timer avanza tantos ciclos como consumió la CPU
  • La GPU también avanza la misma cantidad de ciclos

Interfaces de lectura/escritura e implementación del bus

• Los módulos que admiten lectura y escritura de 8 bits comparten la signatura 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, entre otros, incluyen la misma interfaz con la forma include Addressable_intf.S with type t := t
• Entre la CPU y el bus también se necesitan lecturas y escrituras de 16 bits, por lo que Word_addressable_intf.S incluye Addressable_intf.S y agrega read_word, write_word
• El bus tiene como campos los módulos conectados, como GPU, timer y RAM, y delega lecturas y escrituras al módulo correspondiente según la dirección
  • Las lecturas y escrituras en la dirección 0xC000 se enrutan a la RAM
  • El mapa de memoria completo se puede consultar en Pandocs Memory Map
• read_word implementa una lectura de 16 bits llamando dos veces a read_byte; el hardware real también procesa un acceso de 16 bits como dos accesos de 8 bits

Registros y mejora de la capacidad de prueba de la CPU

• La CPU de Game Boy tiene registros de 8 bits A, B, C, D, E, F, H, L
• Los registros de 8 bits se combinan y también se usan como registros de 16 bits AF, BC, DE, HL
• La implementación inicial de la CPU tenía directamente registers, bus, pc, etc., y run_instruction realizaba fetch, decode y execute
• Esta estructura era difícil de testear
  • El bus dependía de muchos módulos, como GPU, timer y RAM
  • Para crear una CPU en pruebas unitarias, había que preparar el bus y todos los módulos conectados
  • No se podía crear una instancia de CPU antes de que estuvieran implementados el bus y todos los módulos conectados
• La CPU se reimplementó como functor para abstraer la implementación concreta del bus
  • La implementación del bus se inyecta con la forma module Make (Bus : Word_addressable_intf.S)
  • En las pruebas, la CPU se instancia con un Mock_bus basado en un único byte array
  • Con este cambio, las pruebas unitarias de CPU pueden usar una implementación mock en lugar del bus real

Conjunto de instrucciones y uso de GADT

• El conjunto de instrucciones de Game Boy incluye instrucciones que reciben argumentos de 8 bits e instrucciones que reciben argumentos de 16 bits
  • ADD8 A, 0x12 suma el registro A de 8 bits y un valor inmediato de 8 bits
  • ADD16 AF, 0x1234 suma el registro AF de 16 bits y un valor inmediato de 16 bits
• El primer intento representaba los argumentos con variants como Immediate8, Immediate16, R, RR
• Con el enfoque de variants, era difícil fijar un único tipo de retorno para read_arg
  • R r devuelve uint8
  • RR rr devuelve uint16
  • Dentro de la misma expresión match, el tipo de retorno cambia
• Se redefinieron los tipos de argumentos usando GADT
  • Immediate8 : uint8 -> uint8 arg
  • Immediate16 : uint16 -> uint16 arg
  • R : Registers.r -> uint8 arg
  • RR : Registers.rr -> uint16 arg
• En esta estructura, el tipo de retorno cambia según el tipo del argumento, como en read_arg : type a. a Instruction.arg -> a
  • ADD8 solo recibe uint8 arg * uint8 arg
  • ADD16 solo recibe uint16 arg * uint16 arg
  • La confusión entre argumentos de instrucciones de 8 y 16 bits puede reducirse a nivel de tipos

Cartridge y módulos de primera clase

• Un cartridge de Game Boy no es solo una ROM simple; según el tipo, puede incluir hardware adicional
• Un cartridge de tipo ROM_ONLY contiene solo la ROM que almacena los datos y el código del juego
  • Se usa Tetris como ejemplo
• Un cartridge de tipo MBC3 incluye RAM independiente y timer además de la ROM
  • Se usa Pokémon Red como ejemplo
• Como cada tipo de cartridge tiene funciones distintas, se implementan como módulos separados
• Para elegir en tiempo de ejecución el módulo correspondiente al tipo de cartridge, se usan módulos de primera clase
  • Detect_cartridge.f está diseñado para recibir bytes de ROM y devolver (module Cartridge_intf.S)

test ROMs y pruebas de integración basadas en ppx_expect

• Una test ROM es un programa que verifica una función específica del emulador
  • Confirmar el funcionamiento de instrucciones aritméticas básicas
  • Confirmar soporte para cartridges de tipo MBC1
• A diferencia de una ROM de juego común, una test ROM indica el alcance de la función que falló y puede ejecutarse incluso si faltan algunas funciones clave, por lo que es útil para desarrollar emuladores
• Las test ROMs suelen imprimir el resultado de la prueba en pantalla
  • mooneye test ROMs muestra un volcado de registros e información de assertion fallida cuando hay un error
  • También hay test ROMs, como blargg test roms, que imprimen resultados ASCII por serial port
• Las pruebas de integración usan ppx_expect
  • M.run_test_rom_and_print_framebuffer ejecuta la ROM e imprime el estado final de la pantalla como caracteres ASCII
  • La cadena de salida se compara con el valor esperado dentro de [%expect{|...|}]
  • La explicación de ppx_expect puede consultarse en el artículo de Jane Street
• Esta configuración de pruebas detecta regresiones incluso ante cambios grandes de código y permite un flujo de programación exploratoria
  • Buscar una test ROM que verifique la nueva función
  • Configurar una prueba con ppx_expect
  • Committear la salida fallida
  • Implementar la función
  • Verificar que el resultado de la prueba cambie a Test OK

Compilación a JavaScript y UI del navegador

• Gracias a js_of_ocaml, la compilación a JavaScript no fue difícil
• Hizo falta un solo commit para que el emulador funcionara en el navegador
• Para implementar la UI del navegador se usó Brr
• Brr mapea objetos JS a módulos de OCaml, no a objetos de OCaml
  • Las APIs de navegador integradas en js_of_ocaml mapean objetos JS a objetos de OCaml, por lo que requieren conocer el sistema de objetos de OCaml
  • Usar Brr reduce la carga de entender el modelo de objetos de OCaml

Proceso de optimización de rendimiento

• La ejecución inicial en navegador funcionaba, pero era tan lenta que resultaba difícil jugar
  • En un navegador de PC rondaba los 20 FPS
  • Como la Game Boy real funciona a 60 FPS, había que mejorar el rendimiento aproximadamente 3 veces
• Se buscaron cuellos de botella con Chrome profiler
  • La GPU consumía alrededor del 73% del tiempo
  • tile_data.ml consumía 34%, oam_table.ml 18% y tile_map 8%
  • timer.ml y algunas funciones de Bigstringaf también consumían mucho tiempo
• La eliminación gradual de cuellos de botella elevó los FPS
  • Optimización de oam_table.ml: 14 FPS → 24 FPS
  • Optimización de tile_data.ml: 24 FPS → 35 FPS
  • Optimización de timer.ml: 35 FPS → 40 FPS
  • Optimización de tile_map.ml: 40 FPS → 50 FPS
  • Uso de Bigstringaf.unsafe_get en lugar de Bigstringaf.get: 50 FPS → 60 FPS
• Después se alcanzaron 60 FPS en navegador de PC, pero en smartphones se quedaba entre 20 y 40 FPS
• La salida JS del release build era más lenta que la del dev build y, con ayuda de discuss.ocaml.org, se confirmó que el inlining de js_of_ocaml era la causa de la degradación de rendimiento en JS
  • La discusión relacionada está en un post de discuss.ocaml.org
  • En la actualización del 12 de enero de 2022, el impacto negativo se abordó en ocsigen/js_of_ocaml#1220
• Tras desactivar el inlining, se alcanzaron 100 FPS en PC y 60 FPS en smartphones
• La optimización de rendimiento en JS también mejoró el rendimiento native, y la ejecución native funciona a alrededor de 1000 FPS

Benchmarks y límites de comparación

• Se implementó un headless benchmarking mode que ejecuta el emulador sin UI
• Se midieron los FPS en varios backends del compilador de OCaml
• Este benchmark es difícil de usar para comparar FPS con otros emuladores de Game Boy
  • El rendimiento de un emulador depende mucho de su precisión y del alcance de las funciones implementadas
  • Como CAMLBOY no implementa APU (Audio Processing Unit), no tiene sentido comparar FPS con emuladores que sí soportan APU

Experiencia usando OCaml

• El ecosistema de OCaml mejoró mucho respecto de unos 6 años antes, cuando se había usado previamente
  • Gracias a dune, la experiencia se acerca a poner archivos en directorios y dejar que el sistema de build se encargue
  • Con Merlin y OCamlformat, fue en general sencillo incorporar autocompletado, navegación de código y formateo automático
  • Usando setup-ocaml se pueden configurar build y pruebas en GitHub Actions
• En la implementación de CAMLBOY se usó mucho mutable state por razones de rendimiento
  • Muchos módulos tienen funciones de tipo t -> ... -> unit, lo que implica modificar algún mutable state
  • Aunque no es una implementación “funcional”, no se sintió que se perdieran las ventajas de OCaml
• Los puntos preferidos se acercan más a los tipos estáticos, variants, pattern matching, sistema de módulos y buena inferencia de tipos que a lo “funcional” en sí

Aspectos incómodos de OCaml

• Aunque el ecosistema mejoró, algunas áreas siguen siendo complejas o tienen poca documentación
  • En el proceso de resolver dependencias de forma reproducible, faltaban indicaciones claras en la documentación oficial de opam
  • Para encontrar los comandos necesarios, hubo que leer el código fuente de setup-ocaml
  • Resultó complejo el enfoque de tener que “publish” un paquete localmente y luego instalar el paquete publicado localmente
• El costo sintáctico de depender de abstracciones es alto
  • Para hacer que B dependa de la interfaz C_intf en lugar de la implementación concreta de C, hay que convertir B en un functor
  • Cuando B pasa a ser un functor, A ya no puede referenciar B.foo como antes, así que A también debe convertirse en un functor que recibe B_intf
  • Al convertir un módulo en functor, cambia no solo cómo ese módulo depende de otros módulos, sino también cómo otros módulos dependen de él
• Este problema apareció al intentar separar solo la parte Bus -> Cartridge en el grafo de dependencias Camlboy -> Bus -> Cartridge
• En OOP, aunque el constructor de la clase B se cambie para recibir una interfaz C_intf en lugar de la clase concreta C, el tipo de la clase B en sí no cambia
  • Sin embargo, OOP tiene costo de dynamic dispatch
  • Las funciones OOP de OCaml no son familiares para muchas personas, lo que puede limitar el público lector del código

Recursos de referencia

• Recursos sobre OCaml
  • Learn OCaml Workshop: material de workshop usado internamente en Jane Street, con un enfoque de aprendizaje que consiste en completar código OCaml con huecos y pruebas
  • Real World OCaml: material centrado en ejemplos prácticos, recomendado para quienes ya conocen la sintaxis básica de OCaml o tienen experiencia con otros lenguajes funcionales
• Recursos sobre Game Boy
  • The Ultimate Game Boy Talk: video que explica la arquitectura de Game Boy en aproximadamente 1 hora
  • gbops: tabla del conjunto de instrucciones de Game Boy
  • Game Boy CPU Manual: manual de CPU usado para implementar instrucciones; algunas partes, especialmente alrededor de register flags, son inexactas
  • Pandocs: wiki consultada para el comportamiento de módulos de hardware como GPU y timer
  • Imran Nazar’s blog: tutorial para implementar un emulador de Game Boy en JavaScript, usado para entender a grandes rasgos el alcance de la implementación