Criando um emulador de Game Boy em OCaml (2022)

• Para aplicar OCaml além do nível de exemplos, em um código de porte intermediário, foi criado o emulador de Game Boy CAMLBOY, com a meta de rodar no navegador e ter desempenho suficiente para jogar no smartphone
• A implementação é composta pelo método de catch up, que faz CPU, timer e GPU acompanharem os ciclos da CPU, por um bus responsável por rotear leituras e escritas por endereço, e por interfaces de acesso de 8 bits e 16 bits
• Para melhorar a testabilidade da CPU, a implementação do bus foi injetada com functor, e a confusão entre argumentos de instruções foi reduzida separando os tipos de 8 bits e 16 bits com GADT
• Os testes de integração combinaram ROMs de teste com ppx_expect para detectar regressões e permitir uma implementação exploratória, enquanto a UI no navegador foi feita com js_of_ocaml e Brr
• Depois de reduzir gargalos na GPU, no timer e em Bigstringaf com o profiler do Chrome, desativar o inlining do js_of_ocaml levou a 100 FPS no navegador do PC e 60 FPS no smartphone

---

Objetivos e escopo do CAMLBOY

• CAMLBOY é um emulador de Game Boy escrito em OCaml e executado no navegador
• A demo inclui várias ROMs homebrew, e Bouncing ball e Rocket Man Demo são recomendadas
• O objetivo é rodar a 60 FPS até mesmo em navegadores de smartphones modernos
• Depois, por meio de um PR, também passou a ser possível executar via WASM com js_of_ocaml
• O repositório está disponível em linoscope/CAMLBOY

Por que fazer um emulador de Game Boy em OCaml

• Mesmo após alguns meses estudando OCaml, ainda era possível escrever apenas exemplos simples, faltando experiência prática com a organização de código de porte intermediário ou maior e com o uso real de recursos avançados
• Um emulador de Game Boy tem características adequadas para um projeto de prática
  • a especificação é clara, então há pouca dúvida sobre o que implementar
  • é complexo o bastante para não terminar em poucos dias ou semanas
  • mas não é complexo demais a ponto de ser impossível concluir em alguns meses
  • há também uma ligação pessoal com o Game Boy
• O objetivo da implementação priorizava legibilidade e manutenção antes de desempenho, incluindo também execução no navegador e comparação por benchmark
  • compilar para JavaScript com js_of_ocaml para rodar no navegador
  • alcançar FPS jogável no navegador do smartphone
  • implementar benchmarks e comparar diferentes backends de compilação do OCaml

Estrutura do emulador e loop principal

• Os principais componentes do CAMLBOY se dividem em CPU, timer, GPU, bus, cartridge, controlador de interrupções, porta serial, joypad etc.
• O bus roteia leituras e escritas entre a CPU e vários módulos de hardware conforme o endereço
  • por exemplo, uma escrita no endereço 0xFFFF é encaminhada ao controlador de interrupções para ativar ou desativar interrupções
  • os módulos de hardware conectados ao bus implementam a interface Addressable_intf.S
  • o bus implementa a interface Word_addressable_intf.S
• No hardware real, CPU, timer e GPU compartilham o mesmo clock, mas no emulador em loop sequencial é necessária uma sincronização separada
• O loop principal alinha o progresso dos módulos usando o método de catch up
  • a CPU executa uma instrução e registra quantos ciclos consumiu
  • o timer avança pela mesma quantidade de ciclos consumidos pela CPU
  • a GPU também avança pela mesma quantidade de ciclos

Interfaces de leitura e escrita e implementação do bus

• Os módulos que suportam leitura e escrita de 8 bits compartilham a assinatura 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. incluem a mesma interface no formato include Addressable_intf.S with type t := t
• Como entre CPU e bus também são necessárias leituras e escritas de 16 bits, Word_addressable_intf.S inclui Addressable_intf.S e adiciona read_word e write_word
• O bus tem campos para módulos conectados como GPU, timer e RAM, e encaminha leituras e escritas ao módulo apropriado com base no endereço
  • leituras e escritas no endereço 0xC000 são roteadas para a RAM
  • o mapa completo de memória segue o Pandocs Memory Map
• read_word implementa leitura de 16 bits chamando read_byte duas vezes, e o hardware real também trata acessos de 16 bits como dois acessos de 8 bits

Registradores e melhora da testabilidade da CPU

• A CPU do Game Boy possui os registradores de 8 bits A, B, C, D, E, F, H, L
• Esses registradores de 8 bits também podem ser combinados em registradores de 16 bits AF, BC, DE, HL
• A implementação inicial da CPU era uma estrutura com registers, bus, pc etc. diretamente, e run_instruction fazia fetch, decode e execute
• Essa estrutura era difícil de testar
  • o bus dependia de muitos módulos, como GPU, timer e RAM
  • para criar uma CPU em testes unitários, era preciso preparar o bus e todos os módulos conectados
  • não era possível criar uma instância da CPU antes que o bus e todos os módulos conectados estivessem implementados
• A CPU foi reimplementada como functor para abstrair a implementação concreta do bus
  • a implementação recebe o bus no formato module Make (Bus : Word_addressable_intf.S)
  • nos testes, a CPU é instanciada com um Mock_bus baseado em um único array de bytes
  • com isso, os testes unitários da CPU puderam usar uma implementação mock em vez do bus real

Conjunto de instruções e uso de GADT

• O conjunto de instruções do Game Boy tem instruções que recebem argumentos de 8 bits e instruções que recebem argumentos de 16 bits
  • ADD8 A, 0x12 soma o registrador de 8 bits A com um valor imediato de 8 bits
  • ADD16 AF, 0x1234 soma o registrador de 16 bits AF com um valor imediato de 16 bits
• A primeira tentativa representava os argumentos com variants como Immediate8, Immediate16, R, RR
• Na abordagem com variant, era difícil definir um único tipo de retorno para read_arg
  • R r retorna uint8
  • RR rr retorna uint16
  • dentro da mesma expressão match, os tipos de retorno eram diferentes
• Os tipos de argumentos foram redefinidos com GADT
  • Immediate8 : uint8 -> uint8 arg
  • Immediate16 : uint16 -> uint16 arg
  • R : Registers.r -> uint8 arg
  • RR : Registers.rr -> uint16 arg
• Nessa estrutura, o tipo de retorno varia de acordo com o tipo do argumento, como em read_arg : type a. a Instruction.arg -> a
  • ADD8 recebe apenas uint8 arg * uint8 arg
  • ADD16 recebe apenas uint16 arg * uint16 arg
  • a confusão entre argumentos de instruções de 8 bits e 16 bits é reduzida no nível do tipo

Cartridge e módulos de primeira classe

• Um cartridge de Game Boy não contém apenas ROM simples; dependendo do tipo, pode incluir hardware adicional
• O cartridge do tipo ROM_ONLY contém apenas a ROM que armazena os dados e o código do jogo
  • Tetris é usado como exemplo
• O cartridge do tipo MBC3 inclui, além da ROM, RAM independente e timer
  • Pokémon Red é usado como exemplo
• Como os recursos variam por tipo de cartridge, cada um foi implementado em um módulo separado
• Para escolher em tempo de execução o módulo adequado ao tipo de cartridge, foram usados módulos de primeira classe
  • Detect_cartridge.f foi projetado para receber os bytes da ROM e retornar algo no formato (module Cartridge_intf.S)

Testes de integração com ROMs de teste e ppx_expect

• Uma ROM de teste é um programa que verifica funcionalidades específicas do emulador
  • verificar o funcionamento de instruções aritméticas básicas
  • verificar suporte ao tipo de cartridge MBC1
• Diferentemente de uma ROM de jogo comum, a ROM de teste informa a faixa da funcionalidade que falhou e pode rodar mesmo sem alguns recursos essenciais, o que a torna útil no desenvolvimento do emulador
• As ROMs de teste geralmente exibem os resultados na tela
  • mooneye test ROMs mostram dump de registradores e informações de falha de assertion quando ocorre erro
  • também existem ROMs de teste como blargg test roms, que enviam o resultado em ASCII pela porta serial
• Os testes de integração usam ppx_expect
  • M.run_test_rom_and_print_framebuffer executa a ROM e imprime o estado final da tela em caracteres ASCII
  • a string de saída é comparada com o valor esperado dentro de [%expect{|...|}]
  • a explicação de ppx_expect pode ser vista no texto da Jane Street
• Essa configuração de testes detecta regressões mesmo em mudanças grandes no código e permite um fluxo de programação exploratória
  • encontrar uma ROM de teste para validar um novo recurso
  • configurar um teste com ppx_expect
  • commitar a saída com falha
  • implementar o recurso
  • verificar se o resultado do teste muda para Test OK

Compilação para JavaScript e UI no navegador

• Graças ao js_of_ocaml, a compilação para JavaScript não foi difícil
• Foi necessário apenas um único commit para fazer o emulador funcionar no navegador
• A implementação da UI no navegador usou Brr
• O Brr mapeia objetos JS para módulos OCaml, e não para objetos OCaml
  • a API de navegador embutida no js_of_ocaml mapeia objetos JS para objetos OCaml, então exige conhecimento do sistema de objetos do OCaml
  • usar Brr reduz essa carga relacionada ao modelo de objetos do OCaml

Processo de otimização de desempenho

• A execução inicial no navegador funcionava, mas era lenta demais para jogar
  • cerca de 20 FPS no navegador do PC
  • como o Game Boy real opera a 60 FPS, era necessário melhorar o desempenho em cerca de 3 vezes
• O profiler do Chrome foi usado para encontrar gargalos
  • a GPU consumia cerca de 73% do tempo
  • tile_data.ml consumia 34%, oam_table.ml 18% e tile_map 8%
  • timer.ml e algumas funções de Bigstringaf também consumiam muito tempo
• A eliminação dos gargalos elevou o FPS passo a passo
  • otimização de oam_table.ml: 14 FPS → 24 FPS
  • otimização de tile_data.ml: 24 FPS → 35 FPS
  • otimização de timer.ml: 35 FPS → 40 FPS
  • otimização de tile_map.ml: 40 FPS → 50 FPS
  • uso de Bigstringaf.unsafe_get no lugar de Bigstringaf.get: 50 FPS → 60 FPS
• Depois disso, o navegador do PC chegou a 60 FPS, mas no smartphone ainda ficava entre 20 e 40 FPS
• A saída JS da build release era mais lenta que a da build dev e, com ajuda da discuss.ocaml.org, identificou-se que o inlining do js_of_ocaml era a causa da queda de desempenho em JS
  • a discussão relacionada está no post do discuss.ocaml.org
  • em uma atualização de 12 de janeiro de 2022, o impacto negativo foi tratado em ocsigen/js_of_ocaml#1220
• Após desativar o inlining, foram alcançados 100 FPS no PC e 60 FPS no smartphone
• A otimização de desempenho em JS também melhorou o desempenho nativo, que chegou a cerca de 1000 FPS

Benchmark e limitações de comparação

• Foi implementado um modo de benchmark headless para executar o emulador sem UI
• O FPS foi medido em vários backends de compilação do OCaml
• Esse benchmark não é muito adequado para comparar FPS com outros emuladores de Game Boy
  • o desempenho de um emulador depende fortemente da precisão e do escopo dos recursos implementados
  • como o CAMLBOY não implementa a APU (Audio Processing Unit), comparar FPS com emuladores que suportam APU não faz muito sentido

Experiência usando OCaml

• O ecossistema OCaml melhorou bastante em relação a cerca de 6 anos antes, quando havia sido usado anteriormente
  • com dune, a experiência ficou mais próxima de simplesmente colocar arquivos em diretórios e deixar o sistema de build cuidar do resto
  • com Merlin e OCamlformat, autocompletar, navegação de código e formatação automática passaram a ser relativamente fáceis de adotar
  • com setup-ocaml, é possível configurar build e testes no GitHub Actions
• A implementação do CAMLBOY usou bastante estado mutável por razões de desempenho
  • muitos módulos têm funções do tipo t -> ... -> unit, o que significa modificar algum estado mutável
  • mesmo com uma implementação pouco “funcional”, não houve sensação de perder as vantagens do OCaml
• O ponto de preferência está menos no “funcional” em si e mais em tipagem estática, variants, pattern matching, sistema de módulos e boa inferência de tipos

Pontos desconfortáveis no OCaml

• Embora o ecossistema tenha melhorado, algumas áreas ainda são complexas ou pouco documentadas
  • faltava orientação clara na documentação oficial do opam sobre como resolver dependências de forma reproduzível
  • foi preciso ler o código-fonte do setup-ocaml para encontrar os comandos necessários
  • o processo de “publicar” um pacote localmente e depois instalar esse pacote publicado localmente pareceu complicado
• O custo sintático de depender de abstrações é alto
  • para fazer B depender da interface C_intf em vez da implementação concreta C, é preciso transformar B em functor
  • quando B vira functor, A já não pode referenciar B.foo como antes, então A também precisa virar um functor que recebe B_intf
  • ao transformar um módulo em functor, muda não só a forma como ele depende de outros módulos, mas também a forma como outros módulos dependem dele
• Esse problema apareceu ao tentar isolar apenas a parte Bus -> Cartridge no grafo de dependências Camlboy -> Bus -> Cartridge
• Em OOP, mesmo que o construtor da classe B passe a receber a interface C_intf em vez da classe concreta C, o tipo da própria classe B não muda
  • em compensação, OOP tem o custo de dynamic dispatch
  • além disso, os recursos de OOP do OCaml são pouco familiares para muita gente, o que pode limitar o público leitor do código

Materiais de referência

• Materiais sobre OCaml
  • Learn OCaml Workshop: material de workshop usado internamente na Jane Street, em que se aprende preenchendo lacunas em código OCaml e testes
  • Real World OCaml: material recomendado para quem já conhece a sintaxe básica de OCaml ou tem experiência com outras linguagens funcionais, com foco em exemplos práticos
• Materiais sobre Game Boy
  • The Ultimate Game Boy Talk: vídeo que explica a estrutura do Game Boy em cerca de 1 hora
  • gbops: tabela do conjunto de instruções do Game Boy
  • Game Boy CPU Manual: manual de CPU usado na implementação das instruções, embora algumas partes, especialmente em torno das flags de registrador, sejam imprecisas
  • Pandocs: wiki usada como referência para o funcionamento de módulos de hardware como GPU e timer
  • Imran Nazar’s blog: tutorial de implementação de um emulador de Game Boy em JavaScript, usado para estimar aproximadamente o escopo do trabalho