OCamlでGame Boyエミュレータを作る（2022）

• OCamlをサンプルレベルを超えて中規模コードに適用するため、Game BoyエミュレータCAMLBOYを作成し、ブラウザ実行とスマートフォンで遊べる性能を目標にした
• 実装は、CPUサイクルに合わせてCPU・timer・GPUを追従させるcatch up method、アドレスごとの読み書きルーティングを担うbus、8ビット・16ビットアクセス用インターフェースで構成される
• CPUのテスト容易性を高めるため、bus実装をfunctorで注入し、命令引数の取り違えはGADTで8ビット・16ビット型を分離して減らした
• 統合テストではtest ROMとppx_expectを組み合わせて回帰を検出し、探索的な実装を可能にし、ブラウザUIはjs_of_ocamlとBrrで実装した
• Chrome profilerでGPU・timer・Bigstringafのボトルネックを削減した後、js_of_ocamlのインライン展開を無効化して、PCブラウザで100 FPS、スマートフォンで60 FPSに到達した

---

CAMLBOYの目標と範囲

• CAMLBOYはOCamlで書かれたGame Boyエミュレータで、ブラウザ上で動作する
• デモには複数のhomebrew ROMが含まれており、Bouncing ballとRocket Man Demoが推奨されている
• 最新のスマートフォンブラウザでも60 FPSで動作することを目標とした
• その後、PRによりjs_of_ocamlベースのWASM実行も可能になった
• リポジトリはlinoscope/CAMLBOYで公開されている

なぜGame BoyエミュレータをOCamlで作ったのか

• OCamlを数か月勉強した後でも、単純なサンプルは書けたが、中規模以上のコード構成や高度な機能を実戦で使う感覚が不足していた
• Game Boyエミュレータは練習プロジェクトとして適切な条件を備えていた
  • 仕様が明確で、何を実装するか悩む余地が少ない
  • 数日や数週間で終わらない程度には複雑である
  • 数か月以内に完成できないほど過剰に複雑ではない
  • Game Boyに個人的な思い出がある
• 実装目標は性能より先に可読性と保守性を重視しつつ、ブラウザ実行とベンチマーク比較まで含めた
  • js_of_ocamlでJavaScriptにコンパイルしてブラウザで実行
  • スマートフォンブラウザで遊べるFPSを達成
  • ベンチマークを実装し、複数のOCamlコンパイラバックエンドを比較

エミュレータ構造とメインループ

• CAMLBOYの主要構成はCPU、timer、GPU、bus、cartridge、interrupt controller、serial port、joypadなどに分かれる
• busはCPUと複数のハードウェアモジュールの間で、アドレスに応じて読み書きをルーティングする
  • たとえば0xFFFFアドレスへの書き込みはinterrupt controllerに渡され、割り込みを有効化または無効化する
  • busに接続されるハードウェアモジュールはAddressable_intf.Sインターフェースを実装する
  • busはWord_addressable_intf.Sインターフェースを実装する
• 実機ではCPU、timer、GPUが同じクロックを共有するが、エミュレータは逐次実行ループなので別途同期が必要になる
• メインループはcatch up methodで各モジュールの進行量を揃える
  • CPUが命令を1つ実行し、消費したサイクル数を記録する
  • timerをCPUが消費したサイクル数だけ進める
  • GPUも同じサイクル数だけ進める

読み書きインターフェースとbus実装

• 8ビット読み書きをサポートするモジュールは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などはinclude Addressable_intf.S with type t := tの形で同じインターフェースを含む
• CPUとbusの間では16ビット読み書きも必要なため、Word_addressable_intf.SがAddressable_intf.Sを含み、read_word、write_wordを追加する
• busはGPU、timer、RAMなど接続されたモジュールをフィールドに持ち、アドレスを基準に適切なモジュールへ読み書きを渡す
  • 0xC000アドレスの読み書きはRAMにルーティングされる
  • 全体のメモリマップはPandocs Memory Mapを参照
• read_wordはread_byteを2回呼び出して16ビット読み取りを実装しており、実機でも16ビットアクセスは8ビットアクセス2回で処理される

レジスタとCPUのテスト容易性改善

• Game Boy CPUは8ビットレジスタA、B、C、D、E、F、H、Lを持つ
• 8ビットレジスタは組み合わせて16ビットレジスタAF、BC、DE、HLとしても使われる
• 初期のCPU実装はregisters、bus、pcなどを直接持つ構造で、run_instructionでfetch、decode、executeを行っていた
• この構造はテストしにくかった
  • busがGPU、timer、RAMなど多くのモジュールに依存している
  • 単体テストでCPUを生成するにはbusと接続モジュールをすべて用意する必要がある
  • busとすべての接続モジュールが実装される前はCPUインスタンスを作れない
• CPUをfunctorとして再実装し、busの具体実装を抽象化した
  • module Make (Bus : Word_addressable_intf.S)の形でbus実装を注入する
  • テストでは単一のbyte arrayベースのMock_busでCPUをインスタンス化する
  • この変更により、CPU単体テストでは実際のbusの代わりにmock実装を使えるようになった

命令セットとGADTの利用

• Game Boy命令セットには8ビット引数を取る命令と16ビット引数を取る命令がある
  • ADD8 A, 0x12は8ビットレジスタAと8ビット即値を加算する
  • ADD16 AF, 0x1234は16ビットレジスタAFと16ビット即値を加算する
• 最初の試みはImmediate8、Immediate16、R、RRのようなvariantで引数を表現する方式だった
• variant方式ではread_argの返り値型を1つに定めにくかった
  • R rはuint8を返す
  • RR rrはuint16を返す
  • 同じmatch式の中で返り値型が異なる
• GADTを使って引数型を再定義した
  • Immediate8 : uint8 -> uint8 arg
  • Immediate16 : uint16 -> uint16 arg
  • R : Registers.r -> uint8 arg
  • RR : Registers.rr -> uint16 arg
• この構造ではread_arg : type a. a Instruction.arg -> aのように、引数の型に応じて返り値型が変わる
  • ADD8はuint8 arg * uint8 argだけを受け取る
  • ADD16はuint16 arg * uint16 argだけを受け取る
  • 8ビット・16ビット命令引数の取り違えを型レベルで減らせる

cartridgeとファーストクラスモジュール

• Game Boyのcartridgeは単なるROMだけではなく、種類によって追加ハードウェアを含むことがある
• ROM_ONLYタイプのcartridgeはゲームデータとコードを保存するROMだけを含む
  • 例としてTetrisが使われる
• MBC3タイプのcartridgeはROMに加えて独立したRAMとtimerを含む
  • 例としてPokémon Redが使われる
• cartridgeタイプごとに機能が異なるため、それぞれ別モジュールとして実装した
• 実行時にcartridgeタイプに合ったモジュールを選ぶため、ファーストクラスモジュールを使った
  • Detect_cartridge.fはROM byteを受け取り、(module Cartridge_intf.S)を返す形で設計されている

test ROMとppx_expectベースの統合テスト

• test ROMはエミュレータの特定機能を検証するプログラムである
  • 基本的な算術命令の動作確認
  • MBC1 cartridgeタイプのサポート確認
• test ROMは通常のゲームROMと異なり、失敗した機能の範囲を知らせ、一部の中核機能がなくても実行できるため、エミュレータ開発に有用である
• test ROMは通常、テスト結果を画面に出力する
  • mooneye test ROMsは失敗時にレジスタダンプとassertion失敗情報を表示する
  • blargg test romsのようにserial portへASCII結果を出力するtest ROMもある
• 統合テストではppx_expectを使う
  • M.run_test_rom_and_print_framebufferがROMを実行し、最終画面状態をASCII文字で出力する
  • 出力文字列を[%expect{|...|}]内の期待値と比較する
  • ppx_expectの説明はJane Streetの記事を参照
• このテスト構成は大きなコード変更でも回帰を検出し、探索的プログラミングの流れを可能にする
  • 新機能を検証するtest ROMを探す
  • ppx_expectテストを設定する
  • 失敗した出力をコミットする
  • 機能を実装する
  • テスト結果がTest OK状態に変わるか確認する

JavaScriptコンパイルとブラウザUI

• js_of_ocamlのおかげで、JavaScriptへのコンパイル自体は難しくなかった
• ブラウザでエミュレータを動かすには単一コミットが必要だった
• ブラウザUIの実装にはBrrを使った
• BrrはJSオブジェクトをOCamlオブジェクトではなくOCamlモジュールにマッピングする
  • js_of_ocaml内蔵のブラウザAPIはJSオブジェクトをOCamlオブジェクトにマッピングするため、OCamlのオブジェクト知識が必要になる
  • Brrを使うことでOCamlオブジェクトモデルへの負担を減らせる

性能最適化の過程

• 初期のブラウザ実行は動作したものの、遊ぶのが難しいほど遅かった
  • PCブラウザでは約20 FPSだった
  • 実際のGame Boyは60 FPSで動作するため、性能を約3倍改善する必要があった
• Chrome profilerでボトルネックを特定した
  • GPUが約73%の時間を消費していた
  • tile_data.mlが34%、oam_table.mlが18%、tile_mapが8%を消費していた
  • timer.mlと一部のBigstringaf関数も多くの時間を消費していた
• ボトルネック除去により段階的にFPSが向上した
  • oam_table.mlの最適化: 14 FPS → 24 FPS
  • tile_data.mlの最適化: 24 FPS → 35 FPS
  • timer.mlの最適化: 35 FPS → 40 FPS
  • tile_map.mlの最適化: 40 FPS → 50 FPS
  • Bigstringaf.getの代わりにBigstringaf.unsafe_getを使用: 50 FPS → 60 FPS
• その後PCブラウザでは60 FPSに到達したが、スマートフォンでは20〜40 FPSにとどまった
• release buildのJS出力はdev buildより遅く、discuss.ocaml.orgの助けでjs_of_ocamlのインライン展開がJS性能低下の原因だと確認された
  • 関連議論はdiscuss.ocaml.orgの記事にある
  • 2022年1月12日の更新で、この悪影響はocsigen/js_of_ocaml#1220で扱われた
• インライン展開を無効化した後、PCで100 FPS、スマートフォンで60 FPSを達成した
• JS性能の最適化はnative性能も改善し、native実行では約1000 FPSで動作した

ベンチマークと比較の制限

• UIなしでエミュレータを実行するheadless benchmarking modeを実装した
• 複数のOCamlコンパイラバックエンドでFPSを測定した
• このベンチマークは他のGame BoyエミュレータとFPSを比較する用途には使いにくい
  • エミュレータ性能は正確性と実装機能の範囲に大きく左右される
  • CAMLBOYはAPU(Audio Processing Unit)を実装していないため、APU対応エミュレータとFPSを比較しても意味がない

OCaml使用経験

• OCamlエコシステムは以前使っていた約6年前と比べて大きく改善していた
  • duneのおかげで、ファイルをディレクトリに入れればビルドシステムが処理してくれる感覚に近づいた
  • MerlinとOCamlformatにより、自動補完、コード探索、自動整形の導入が概ね容易になった
  • setup-ocamlを使えばGitHub Actionsでビルドとテストを設定できる
• CAMLBOY実装では性能上の理由からmutable stateを多用した
  • 多くのモジュールがt -> ... -> unit型の関数を持ち、これは何らかのmutable stateの変更を意味する
  • 非「関数型」な実装でもOCamlの利点を失ったとは感じなかった
• 好みのポイントは「関数型」そのものより、静的型付け、variant、pattern matching、モジュールシステム、優れた型推論に近い

OCamlで不便だった点

• エコシステムは改善したが、一部の領域は依然として複雑だったり文書が不足していた
  • 再現可能な形で依存関係を解決する過程で、公式opamドキュメントには明確な案内が不足していた
  • 必要なコマンドを探すためにsetup-ocamlのソースを読んだ
  • ローカルにパッケージを「publish」した後、そのローカルpublish済みパッケージをインストールする方式は複雑に感じられた
• 抽象化依存の文法的コストが高い
  • BがCの具体実装ではなくC_intfインターフェースに依存するようにするには、Bをfunctorに変える必要がある
  • Bがfunctorになると、Aは従来のようにB.fooを参照できなくなり、AもB_intfを受け取るfunctorに変える必要がある
  • モジュールをfunctorに変えると、そのモジュールが他モジュールに依存する方法だけでなく、他モジュールがそのモジュールに依存する方法も変わってしまう
• この問題はCamlboy -> Bus -> Cartridge依存グラフで、Bus -> Cartridge部分だけを分離しようとしたときに発生した
• OOPではclass Bのコンストラクタが具体class Cの代わりにinterface C_intfを受け取るように変更しても、class B自体の型は変わらない
  • ただしOOPにはdynamic dispatchのコストがある
  • OCamlのOOP機能は慣れていない人も多く、コードの読者層を狭める可能性がある

参考資料

• OCaml関連資料
  • Learn OCaml Workshop: Jane Street社内で使われたワークショップ資料で、穴埋めのあるOCamlコードとテストを埋めながら学ぶ方式
  • Real World OCaml: OCamlの基本文法を知っている人、または他の関数型言語の経験がある人に勧められる実践的なサンプル中心の資料
• Game Boy関連資料
  • The Ultimate Game Boy Talk: Game Boyの構造を約1時間で説明する動画
  • gbops: Game Boy命令セット表
  • Game Boy CPU Manual: 命令実装に使ったCPUマニュアルだが、一部、特にregister flag周辺は不正確である
  • Pandocs: GPU、timerなどのハードウェアモジュール動作を参照したwiki
  • Imran Nazar’s blog: JavaScriptでGame Boyエミュレータを実装するチュートリアルで、実装範囲の大まかな把握に使われた