Введение

Последние несколько месяцев я работал над проектом под названием CAMLBOY — эмулятором Game Boy, написанным на OCaml, который работает в браузере. Протестировать его можно на следующей странице демо:

Страница демо

Я добавил в демо несколько неофициальных ROM, поэтому в них можно поиграть (рекомендую Bouncing ball и Rocket Man Demo). Также можно поиграть в них в мобильном браузере, на современных смартфонах эмулятор работает с частотой 60 FPS.

Репозиторий

Репозиторий находится здесь:

https://github.com/linoscope/CAMLBOY

Зачем писать эмулятор Game Boy на OCaml?

Вы когда-нибудь испытывали подобное при изучении нового языка программирования?

• Вы можете писать простые фрагменты кода, но не знаете, как писать код среднего/большого масштаба. [Под этим понимается «код, который сложно разрабатывать без тестов, поэтому его нужно проектировать с учётом простоты тестирования». Тема написания легко тестируемого кода редко упоминается в ознакомительных книгах, но на практике она очень важна.]
• Вы изучили продвинутые особенности языка и обладаете приблизительным пониманием того, как они работают, но не знаете, как использовать их на практике. [Под «продвинутыми особенностями языка» в OCaml я подразумеваю функторы, GADT, первичные модули (first-class module) и т. п.]

Именно так я думал, когда несколько месяцев назад приступил к изучению OCaml. Я понимал основы языка благодаря чтению книг и реализации простых алгоритмов, но перечисленные выше два пункта не позволяли мне чувствовать, что я по-настоящему могу писать на OCaml. Я знал, что единственным способом выбраться из этой ситуации является практика, поэтому начал искать проект, над которым можно поработать.

Я выбрал в качестве проекта эмулятор Game Boy по следующим причинам:

• Он имеет чёткие спецификации, поэтому мне не нужно думать над тем, что реализовать.
• Он достаточно сложен, чтобы его нельзя было завершить за несколько дней или недель.
• Он не настолько сложен, чтобы его нельзя было реализовать за несколько месяцев.
• У меня сохранились тёплые воспоминания о том, как в детстве я играл на Game Boy.

Я поставил следующие задачи перед эмулятором:

• Писать код с упором на читаемость и удобство поддержки.
• Компилировать в JavaScript при помощи js_of_ocaml и запускать его в браузере.
• Достичь играбельного уровня FPS в браузере на смартфоне.
• Написать несколько бенчмарков и сравнить разные бэкенды компиляторов. [Эмуляторы — это довольно популярный бенчмарк для различных языков/сред выполнения. Например, эмулятор NES используется в мире Ruby для бенчмаркинга разных сред выполнения Ruby, а команда разработчиков Chrome, похоже, использовала эмулятор Game Boy для бенчмаркинга своего движка JS.]

Цель этой статьи

В этой статье я расскажу о процессе создания эмулятора Game Boy на OCaml.

Эта статья будет вам интересна, если вы хотите:

• Создать эмулятор Game Boy.
• Реализовать проект среднего размера на OCaml.
• Использовать на практике продвинутые возможности OCaml.

Мы рассмотрим следующие темы:

• Краткое описание архитектуры Game Boy.
• Как структурировать свой код, чтобы его можно было тестировать и использовать многократно.
• Как на практике использовать функторы, GADT и первичные модули.
• Как находить узкие места и повышать производительность.
• Общие рассуждения об OCaml.

Мы не будем рассматривать следующие темы:

• Основы синтаксиса OCaml
• Подробности архитектуры Game Boy

Информацию по этим темам можно найти в разделе «Рекомендуемые материалы».

Реализация

Схема архитектуры

Схематичная диаграмма CAMLBOY выглядит следующим образом [Учтите, что это схема моей реализации, а НЕ схема оборудования Game Boy. Кроме того, я не указал не реализованные пока компоненты, такие как APU (Audio Processing Unit).]:


Я буду объяснять подробности по мере необходимости, а вкратце система устроена так:

• ЦП/таймер/GPU работает с фиксированной частотой в соответствии с тактовым генератором.
• Шина находится между ЦП и разными аппаратными модулями, маршрутизируя чтение/запись данных на основании указанного адреса. Например, операции записи по адресу 0xFFFF передаются контроллеру прерываний и включают/отключают прерывания в зависимости от записанного значения.
• Подключенные к шине аппаратные модули реализуют интерфейс Addressable_intf.S (который я объясню ниже)
• Шина реализует интерфейс Word_addressable_intf.S (который я объясню ниже)
• Существуют различные типы картриджей.
• Таймер, GPU, последовательный порт и джойстик могут запрашивать прерывания. Контроллер прерываний уведомляет о запрошенном прерывании ЦП (подробное описание прерываний в статье отсутствует).

Основной цикл

Основной цикл отвечает за изменение тактируемых аппаратных модулей (выделенных красным цветом) синхронизированным образом.


В реальном оборудовании ЦП/таймер/GPU имеют один аппаратный тактовый генератор, поэтому естественным образом работают в синхронизированном состоянии. В отличие от него, эмулятор — это всего лишь цикл последовательного исполнения, поэтому нам нужно придумать способ воссоздания синхронизации между этими компонентами. Для этого я реализовал в основном цикле следующие этапы:

1. ЦП выполняет одну команду и отслеживает количество потреблённых в результате этого тактов.
2. Таймер продвигается вперёд на количество тактов, потреблённых ЦП.
3. Продвигаем вперёд GPU на количество тактов, потреблённых ЦП.

Иногда такую систему называют catch up method, потому что она заставляет таймер и GPU «догонять» ЦП. Вот её реализация:

(* camlboy.ml *)
let run_instruction t =
  let mcycles = Cpu.run_instruction t.cpu in
  Timer.run t.timer ~mcycles;
  Gpu.run t.gpu ~mcycles

Интерфейс для чтения/записи данных

Мы рассмотрим некоторые базовые интерфейсы, использованные в эмуляторе.

Интерфейс для чтения/записи 8-битных данных

Сначала давайте рассмотрим интерфейс для чтения/записи 8-битных данных, показанный на рисунке ниже красными линиями.


Шина (Bus) может считывать и записывать 8-битные данные из различных аппаратных модулей, например, GPU и RAM. Так как мы будем реализовывать множество модулей, умеющих считывать и записывать 8-битные данные, то нам бы хотелось, чтобы их интерфейс в чём-то был общим.

В ООП мы можем:

1. Написать интерфейс (public interface A {...} в Java).
2. Реализовать его (implements A в Java).

В OCaml мы можем:

1. Написать сигнатуру (module type S = sig ... end).
2. Подключить её (include S with type t := t ).

В соответствии с этими шагами мы задаём сигнатуру Addressable_intf.S следующим образом [uint8 и uint16 в коде — это не встроенные типы OCaml, а типы из отдельного модуля unsigned int (units.mli, units.ml).]:

(* addressable_intf.mli *)
module type S = sig
  type t
  (* reads 8-bit data from address addr *)
  val read_byte : t -> uint16 -> uint8
  (* writes 8-bit data to address addr *)
  val write_byte : t -> addr:uint16 -> data:uint8 -> unit
  (* returns true if it accepts reads/writes from addr and returns false if it can not *)
  val accepts : t -> uint16 -> bool
end

Затем мы подключаем Addressable_intf.S в файлах интерфейсов модулей, обеспечивающих 8-битные чтение/запись. Например файл интерфейса модуля RAM ram.mli выглядит так:

(* ram.mli *)
type t
...
include Addressable_intf.S with type t := t

Аналогично Addressable_intf.S подключают gpu.mli, joypad.mli, timer.mli и т. п.

Примечание

Возможно, следует объяснить with type t := t в приведённом выше коде. В целом, A with type t := s заменяет t в сигнатуре A на s. То есть include Addressable_intfS with type t := t означает:

заменить тип t в Addressable_intfS на тип t в Ram, а затем include («расширить» его здесь).

Иными словами, вышеприведённый ram.mli аналогичен следующему:

(* ram.mli *)
type t
...
(* include Addressable_intf.S with type t := t will be "expanded" as the following *)
val read_byte : t -> uint16 -> uint8
val write_byte : t -> addr:uint16 -> data:uint8 -> unit
val accepts : t -> uint16 -> bool

Интерфейс для чтения/записи 16-битных данных

Далее давайте рассмотрим интерфейс чтения/записи 16-битных данных, показанный на схеме ниже красной линией.


Между ЦП и шиной в дополнение к 8-битным данным могут также считываться/записываться 16-битные данные. Чтобы выразить это было бы здорово, если бы мы каким-то образом могли «расширить» интерфейс для чтения/записи 8-битных данных (Addressable_intf.S) функциями чтения/записи 16-битных данных.

В OOP мы можем

1. Выполнить наследование интерфейса (extends A в Java).

В OCaml мы можем

1. Подключить сигнатуру (include A with type t := t ).

Следовательно, чтобы дополнить Addressable_intf.S 16-битным чтением/записью, мы можем

1. Задать сигнатуру Word_addressable_intf.S.
2. Подключить Addressable_intf.S
3. Добавить дополнительные функции (read_word и write_word)

В результате мы получим следующее определение:

(* word_addressable_intf.ml *)
(** Interface that provide 16-bit read/write in addition to 8-bit read/write *)
module type S = sig
  type t
  include Addressable_intf.S with type t := t
  (* 16-bit reads/writes *)
  val read_word : t -> uint16 -> uint16
  val write_word : t -> addr:uint16 -> data:uint16 -> unit
end

Шина

Давайте рассмотрим реализацию шины, выделенной на схеме ниже красной рамкой.


Шина располагается между ЦП и различными аппаратными модулями и маршрутизирует операции чтения/записи данных на основании переданного адреса. Например, шина направляет чтение/запись по адресу 0xC000 в RAM. Полную схему памяти можно найти здесь.

При помощи реализованной выше Word_addressable_intf.S мы можем определить интерфейс модуля шины (bus.mli) следующим образом.

(* bus.mli *)
type t
val create :
  gpu:Gpu.t ->
  timer:Timer.t ->
  wram:Ram.t ->
  ... ->
  t
include Word_addressable_intf.S with type t := t

Затем мы можем реализовать шину (bus.ml) как это показано ниже:

(* bus.ml *)
type t = {
  gpu   : Gpu.t;
  timer : Timer.t;
  wram  : Ram.t;
  ...
}

(* takes the modules connected to the bus as its argument *)
let create ~gpu ~timer ~wram ... = {
  gpu;
  timer;
  wram;
  ...
}

let read_byte t addr =
  (* routes the data read to the appropriate module based on the given address *)
  match addr with
  | _ when Gpu.accepts t.gpu addr ->
    Gpu.read_byte t.gpu addr
  | _ when Timer.accepts t.timer addr ->
    Timer.read_byte t.timer addr
  | _ when Ram.accepts t.wram addr ->
    Ram.read_byte t.wram addr
  | ...

let read_word t addr =
  (* The read_word function archives 16-bit reads by calling read_byte twice.
     The actual hardware also achieves 16-bit read/write by conducting 8-bit read/write twice. *)
  let lo = Uint8.to_int (read_byte t addr) in
  let hi = Uint8.to_int (read_byte t Uint16.(succ addr)) in
  (hi lsl 8) + lo |> Uint16.of_int

Регистры

Давайте рассмотрим реализацию регистров, на схеме ниже показанных красной рамкой.


В ЦП консоли Game Boy есть восемь 8-битных регистров, A, B, C, D, E, F, H и L. Эти 8-битные регистры можно комбинировать и использовать в качестве 16-битных регистров AF, BC, DE и HL. Ниже показан интерфейс модуля Registers (реализация пропущена):

(* registers.mli *)

type t
(* identifiers of the 8-bit registers *)
type r = A | B | C | D | E | F | H | L
(* identifiers for the 16-bit registers *)
type rr = AF | BC | DE | HL

...

(* read/write functions for the above registers *)
val read_r   : t ->  r -> uint8
val write_r  : t ->  r -> uint8 -> unit
val read_rr  : t -> rr -> uint16
val write_rr : t -> rr -> uint16 -> unit

ЦП

Далее мы рассмотрим реализацию ЦП, показанного на схеме ниже красной рамкой.

Моя первоначальная реализация ЦП

Ниже показана моя первая реализация ЦП. Подробности функции execute здесь опущены, подробнее мы поговорим о них, когда будем реализовывать набор команд.

(* cpu.mli *)
type t
val create : bus:Bus.t -> registers:Registers.t -> ... -> t
val run_instruction : t -> int (* returns the # of cycles consumed *)

(* cpu.ml *)
type t = {
  registers  : Registers.t;
  bus        : Bus.t;
  mutable pc : uint16; (* Program counter *)
  ...
}

(* Initializes the CPU by passing it's dependencies *)
let create ~bus ~registers ... = {
    bus;
    registers;
    ...
}

(* Omitted for now. *)
let execute t inst = ...

(* Fetches, decodes, and executes an instruction *)
let run_instruction t =
  ...
  let inst = Fetch_and_decode.f t.bus ~pc:t.pc in
  execute t inst

Проблема первоначальной реализации ЦП

Приведённая выше реализация ЦП работает, но имеет одну проблему — её сложно тестировать. Это становится понятным из показанной ниже схемы:


Обратите внимание, что шина имеет множество зависимостей от разных модулей. Эти зависимости усложняют создание экземпляра ЦП в юнит-тестах. Кроме того, невозможно создать экземпляр ЦП, пока мы не реализуем шину и все подключенные модули, что может произойти на достаточно позднем этапе процесса разработки.

Чтобы ЦП был тестируемым, нам нужно абстрагировать реализацию шины от ЦП. Сделав это, мы можем заменить шину заглушкой, как это показано ниже:


В OCaml можно обеспечить такую абстракцию реализации при помощи функторов.

Использование функторов для повышения тестируемости

Я заново реализовал ЦП при помощи подобных функторов:

(* cpu.mli *)

(* We can now "inject" different implementations of the Bus via this functor argument *)
module Make (Bus : Word_addressable_intf.S) : sig
  type t
  ...
end

(* cpu.ml *)

module Make (Bus : Word_addressable_intf.S) = struct
  type t = {
    registers  : Registers.t;
    bus        : Bus.t;
    mutable pc : uint16; (* Program counter *)
    ...
  }
  ...
end

Благодаря этим изменениям мы можем использовать имитацию реализации шины для создания экземпляра ЦП в юнит-тестах:

(* test_cpu.ml *)
...
(* Mock_bus is a simple implementation of `Word_addressable_intf.S`
   which is implemented using a single byte array. *)
module Cpu = Cpu.Make(Mock_bus)
let cpu = Cpu.create ~bus:(Mock_bus.create ~size:0xFF) ...
...

Набор команд

Теперь давайте закодируем набор команд Game Boy на OCaml.

Набор команд Game Boy состоит из

• 8-битных команд: получают в качестве аргументов 8-битные значения (8-битные регистры, 8-битные непосредственные значения, и т. п.).
• 16-битных команд: получают в качестве аргументов 16-битные значения (16-битные регистры, 16-битные непосредственные значения, и т. п.).

Например, существует две версии сложения, показанные ниже:

# 8-bit version
# Adds the 8-bit `A` register and `0x12`, then stores the result in the `A` register
ADD8 A, 0x12
# 16-bit version
# adds the 16-bit `AF` register and `0x1234`, then stores the result in the `AF` register
ADD16 AF, 0x1234

Как же нам определить такой набор команд на OCaml?

Определяем набор команд при помощи вариантов

В качестве первой попытки я представил команды и их аргументы в виде вариантов, как показано ниже:

(* instruction.ml *)

(* Instruction arguments definied using variants *)
type arg =
  | Immediate8  of uint8   (*  8-bit value *)
  | Immediate16 of uint16 (* 16-bit value *)
  | R           of Registers.r      (*  8-bit register *)
  | RR          of Registers.rr    (* 16-bit register *)
  | ...

(* Instructions *)
type t =
  | ADD8  of arg * arg (*  8-bit version of ADD *)
  | ADD16 of arg * arg (* 16-bit version of ADD *)
  | ...

Но вскоре заметил, что такое решение не работает.

Проблема определения при помощи вариантов

Почему это решение не работает? Проблема возникает, когда мы пытаемся «потребить» набор команд в функции execute:

(* cpu.ml *)

(* Takes a single instruction and executes it. *)
let execute t (inst : Instruction.t) =
  ...
  let read_arg = function
    (* fetch values stored in the given argument *)
    | Immidiate8  x -> x
    | Immediate16 x -> x
    | R  r          -> Registers.read_r r
    | RR rr         -> Registers.read_rr rr
    | ...
  in
  match inst with
  | Add8 (x, y) ->
    (* Fetches the value stored in the arguments x and y adds them. *)
    let sum = Uint8.add (read_arg x) (read_arg y) in
    ...
  | Add16 (x, y) ->
    let sum = Uint16.add (read_arg x) (read_arg y) in
    ...

let run_instruction t =
  ...
  let inst = Fetch_and_decode.f t.bus ~pc:t.pc in
  execute t inst

Я извлёк функцию read_arg, чтобы понять, в чём заключается проблема. Обратите внимание, что возвращаемое значение всей функции нельзя определить уникальным образом. Так получилось, потому что возвращаемый тип сопоставимого выражения изменяется в зависимости от того, с каким конструктором он сопоставляется, о чём сказано в комментариях.

  (* What is the type of the return value? *)
  let read_arg : Instruction.arg -> ??? = function
    ...
    | R r  ->
      (* fetches the value of 8-bit register. *)
      (* returns uint8 in this case. *)
      Registers.read_r r
    | RR r ->
      (* fetches the value of 16-bit register. *)
      (* returns uint16 in this case. *)
      Registers.read_rr r
  in

В этот момент я вспомнил о GADT (Generalized Algebraic Data Type) — функции языка, которую я изучал раньше, но так и не освоил полностью.

На помощь приходят GADT

Ниже представлен заново определённый при помощи GADT набор команд. Обратите внимание, что определение типа arg отличается от предыдущего определения при помощи вариантов.

(* instruction.ml *)

(* Instruction arguments definied using GADTs *)
type _ arg =
  | Immediate8  : uint8        -> uint8  arg
  | Immediate16 : uint16       -> uint16 arg
  | R           : Registers.r  -> uint8  arg
  | RR          : Registers.rr -> uint16 arg
  | ...

(* Instructions *)
type t =
  | ADD8  of uint8 arg * uint8 arg
  | ADD16 of uint16 arg * uint16 arg
  | ...

Чтобы понять смысл этого определения, давайте рассмотрим третью строку типа arg:

  | R : Registers.r -> uint8  arg

Тип аргумента конструктора (Registers.r в Registers.r -> uint8 arg) имеет ту же функциональность, что и of Registers.r в определении при помощи вариантов. Он изменяет тип получаемого значения в сопоставлении паттернов на основании конструктора.

В показанной ниже конструкции сопоставления обратите внимание на то, что тип значения, получаемый в конструкции сопоставления (тип r и rr) отличается от сопоставляемого конструктора. Это возможно, потому что тип аргумента конструктора отличается.

let read_arg = function
  ...
  | R   r -> .. (* type of r is Registers.r *)
  | RR rr -> .. (* type of rr is Registers.rr *)
  ...

Тогда что обозначает возвращаемый тип конструктора (uint8 arg in Registers.r -> uint8 arg)? Похоже, в определении на основе вариантов ему ничто не соответствует. На самом деле он меняет тип возвращаемого значения в сопоставлении паттернов на основании конструктора.

Взгляните на показанную ниже конструкцию сопоставления. Обратите внимание, что тип возвращаемого значения в конструкции сопоставления отличается в зависимости от сопоставляемого конструктора. Это возможно, потому что возвращаемый тип конструктора отличается.

let read_arg = function
  ..
  | R   r -> Registers.read_r r   (* returns uint8 *)
  | RR rr -> Registers.read_rr rr (* returns uint16 *)
  ...

Подведём итог: варианты могут параметризировать тип значений, получаемых в конструкции сопоставления, а GATD могут также параметризировать тип возвращаемого значения в конструкции сопоставления. В этом смысле GADT более «обобщены», чем варианты; наверно, отсюда и название “Generalized” Algebraic Data Type.

Благодаря новому определённому Instruction.arg, в котором используются GADT, мы можем написать следующую execute. Тип 'a Instruction.arg -> 'a в read_arg показывает, что возвращаемый тип изменяется в зависимости от типа конкретного конструктора.

let execute t (inst : Instruction.t) =
  ...
  let read_arg : type a. a Instruction.arg -> a = fun arg ->
    match arg with
    | Immediate8  n -> n
    | Immediate16 n -> n
    | ...
  in
  match inst with
  | Add8 (x, y) ->
    let sum = Uint8.add (read_arg x) (read_arg y) in
    ...
  | Add16 (x, y) ->
    let sum = Uint16.add (read_arg x) (read_arg y) in
    ...

Для справки вот полный набор команд, заданный при помощи GADT:

Картриджи

Теперь мы рассмотрим реализацию картриджей, выделенную на схеме красной рамкой.


Вы можете думать, что картриджи для Game Boy — это просто ROM (память только для чтения), в которой хранятся данные/код игры, но это не так. Во многих картриджах для Game Boy содержатся аппаратные компоненты, расширяющие ограниченную функциональность Game Boy. Например, в картриджах типа ROM_ONLY (в частности, Tetris) содержится только ROM, где хранятся данные/код игры, а в картриджах типа MBC3 (в частности, Pokémon Red) в дополнение к ROM содержится независимая RAM и таймеры.

Так как каждый картридж имеет собственную функциональность, мы реализуем каждый тип картриджа как отдельные модули. Следовательно, нам нужен механизм для выбора модуля во время выполнения согласно типу картриджа.

Для подобного «выбора модулей во время выполнения» полезны первичные модули (first-class modules). Как показано ниже, можно написать Detect_cartridge.f, возвращающую первичный модуль на основании типа картриджа. В посте мы пропустим её реализацию.

(* detect_cartridge.mli *)
val f : rom_bytes:Bigstringaf.t -> (module Cartridge_intf.S)

Интеграционное тестирование

Я использовал тестовые ROM и ppx_expect для выявления регрессий и обеспечения возможности исследовательского программирования.

Что такое тестовые ROM

Тестовые ROM — это программы, тестирующие определённую функциональность эмулятора. Например, есть тестовые ROM, которые:

• Тестируют, правильно ли работают простейшие арифметические команды.
• Тестируют, адекватно ли поддерживается тип картриджа MBC1.

Такие тестовые ROM чрезвычайно полезны при разработке эмуляторов, поскольку, в отличие от игровых ROM, они

• Дают понять, какой конкретно аспект эмулятора даёт сбой.
• Запускаются, даже если отсутствует какая-то базовая функциональность эмулятора.

Тестовые ROM обычно выводят результаты теста на дисплей [Некоторые тестовые ROM, например, blargg test roms, выводят результаты тестов в последовательный порт в виде символов ASCII. Это позволяет тестировать эмулятор ещё даже до реализации GPU.]. Например, результаты работы mooneye test ROMs выглядят так, как показано на изображениях ниже. Текст, отображаемый в случае сбоя — это дамп регистров и информация о сбое проверочного утверждения.

Подготовка тестов

Ниже показан пример интеграционного теста, реализованного с помощью тестового ROM и ppx_expect. Вот что происходит:

1. M.run_test_rom_and_print_framebuffer запускает ROM и выводит окончательное состояние на экран в виде символов ASCII.
2. Выведенная строка сопоставляется с ... в [%expect{|...|}].

Подробности о ppx_expect можно найти в этой статье.

let%expect_test "bits_mode.gb" =
  M.run_test_rom_and_print_framebuffer "mbc1/bits_mode.gb";

  [%expect{|
    008:-#######-----------------------------------###---#---#----------------------------------------------------------------------------------------------------------
    009:----#-----####-----###-----#--------------#---#--#--#-----------------------------------------------------------------------------------------------------------
    010:----#----#----#---#-------####------------#---#--#-#------------------------------------------------------------------------------------------------------------
    011:----#----######----##------#--------------#---#--###------------------------------------------------------------------------------------------------------------
    012:----#----#-----------#-----#--------------#---#--#--#-----------------------------------------------------------------------------------------------------------
    013:----#-----####----###------##--------------###---#---#---------------------------------------------------------------------------------------------------------- |}]

Эти интеграционные тесты придали мне уверенности при внесении крупных изменений в код, потому что тестовый комплект будет выявлять регрессии.

Исследовательское программирование

Более того, эти интеграционные тесты позволили мне реализовать эмулятор в стиле исследовательского программирования. Когда мне нужно было реализовать новую функциональность, я

1. Находил тестовый ROM, проверяющий эту функциональность.
2. Создавал тесты ppx_expect, запускающие тестовый ROM.
3. Выполнял тесты и коммитил выводимую информацию сбоев.
4. Реализовывал функциональность.
5. Проверял, перешёл ли тест в состояние «Test OK».

Компиляция в JavaScript

Компиляция в JavaScript оказалась на удивление простой благодаря js_of_ocaml. Мне удалось заставить эмулятор работать в браузере всего одним коммитом.

При реализации браузерного UI я использовал библиотеку Brr. Удобство Brr заключается в том, что она сопоставляет объекты JS с модулями OCaml, в отличие от встроенного браузерного API js_of_ocaml, который сопоставляет объекты JS с объектами OCaml, требуя определённых знаний об «O» в OCaml.

Оптимизация

Хоть мне удалось заставить его работать в браузере, возникла одна проблема — эмулятор был неиграбельно медленным. Ниже показано, как он выглядел на этом этапе в браузере на PC, работая с частотой примерно 20 FPS. Реальный Game Boy работает с 60 FPS, поэтому нам нужно было улучшить производительность втрое.


И так начался мой путь оптимизации.

Поиск узких мест при помощи профилировщика

Первым делом я воспользовался профилировщиком Chrome для поиска узких мест [Возможность применения профилировщика Chrome стала приятным побочным эффектом компиляции в JS.]. Вот результаты:


На графике видно, что GPU потребляет примерно 73% времени, а tile_data.ml, oam_table.ml и tile_map тратят, соответственно 34%, 18% и 8% времени.

Аналогично я выяснил, что много времени тратят timer.ml и некоторые функции Bigstringaf.

Устранение узких мест

Теперь, когда я знал, где находятся узкие места, я начал работать над их устранением. Так как в этой статье не рассматриваются те части, которых коснулись изменения, я просто перечислю оптимизации и их результаты.

• Оптимизирован oam_table.ml (коммит):
  
  • 14fps -> 24fps
• Оптимизирован tile_data.ml (коммит):
  
  • 24fps -> 35fps
• Оптимизирован timer.ml (коммит):
  
  • 35fps -> 40fps
• Оптимизирован tile_map.ml (коммит):
  • 40fps -> 50fps
• Использована Bigstringaf.unsafe_get вместо Bigstringaf.get (коммит):
  
  • 50fps -> 60fps

Отключение встраивания

На этом этапе эмулятор работал с частотой 60 FPS в браузере на моём PC, но только с 20-40 FPS на телефоне. Я понял, что вывод JS из релизной сборки был медленнее, чем вывод JS из тестовой сборки. Благодаря помощи пользователей discuss.ocaml.org выяснилось, что встраивание js_of_ocaml замедляло работу JS (вероятно, потому, что эмулятор содержит длинные функции, а движок JS не выполняет JIT-компиляцию, когда функция слишком длинная).

После отключения встраивания мне удалось достичь 100 FPS на моём PC и 60 FPS на моём телефоне. Ниже показана gif эмулятора, работающего с 100 FPS в браузере на PC. (Дополнение: отрицательное воздействие встраивания рассматривается в ocsigen/js_of_ocaml#1220)


Примечание: оптимизация скорости JS также повысила и нативную производительность. Ниже показан эмулятор, работающий примерно с частотой 1000 FPS в нативной среде.

Бенчмарки

Я реализовал безголовый режим бенчмаркинга для запуска эмулятора без UI. После замера FPS в различных бэкендах компиляторов OCaml результат был таким [Помните, что мы не можем использовать этот бенчмарк для сравнения FPS с другими эмуляторами Game Boy, потому что производительность эмулятора сильно зависит от того, насколько он точен и какую функциональность имеет. Например, в CALMBOY не реализован APU (Audio Processing Unit), поэтому нет никакого смысла сравнивать его FPS с эмуляторами, имеющими поддержку APU.]:

Заключительные выводы

Размышления о разработке эмуляторов

Мне кажется, разработка эмуляторов похожа на соревновательное программирование. Оба процесса заключаются в итерациях следующих этапов:

• Чтение спецификации — формулировка задачи в соревновательном программировании и руководства/вики-страницы в разработке эмуляторов.
• Реализация в соответствии со спецификацией.
• Проверка соответствия реализации и спецификации — отправка онлайн-судье в соревновательном программировании и запуск тестовых ROM в разработке эмуляторов.

В прошлом я рекомендовал соревновательное программирование людям (типа меня), желающим кодить, но с трудом способных придумать, что же реализовать. В будущем я буду рекомендовать таким людям и разработку эмуляторов.

Что мне понравилось в OCaml

Экосистема

Экосистема OCaml значительно улучшилась с тех времён, когда я соприкасался с OCaml (примерно шесть лет назад). Вот некоторые примеры:

• Благодаря dune мы теперь можем просто закинуть файлы в папку, а всё остальное может сделать система сборки, что в современных языках программирования становится нормой.
• Благодаря ПО наподобие Merlin и OCamlformat добавление автодополнения, навигации по коду и автоматического форматирования стало практически беспроблемным.
• Благодаря setup-ocaml мы можем настраивать сборки с действиями Github и тестировать код простым коммитом одного файла.

Если вы пробовали работать с OCaml несколько лет назад, но забросили его из-за экосистемы, то рекомендую дать ему ещё один шанс.

Чтобы быть полезным, необязательно быть «функциональным»

Функциональным языком часто называют такой язык, который «поддерживает стиль программирования, имеющий минимальное количество побочных эффектов», но меня всегда напрягало это выражение «побочные эффекты». Я не говорю, что определение ошибочно, просто я не считаю, что сами по себе побочные эффекты являются серьёзной проблемой. Открытое изменяемое состояние — это плохо, но разве недостаточно просто спрятать его за абстракцией?

На самом деле. в реализации CAMLBOY по причинам производительности есть куча изменяемых состояний. Многие модули имеют функции с типом t -> ... -> unit, обозначающим модификацию какого-то изменяемого состояния. И хотя это «нефункциональная» реализация, мне никогда не казалось, что я упускаю преимущества OCaml.

Возможно, я люблю не столько «функциональные» языки, сколько языки со статической типизацией, вариантами, сопоставлением паттернов, системой модулей и хорошим выводом типов.

Что мне не нравится в OCaml

Экосистема

Хотя экосистема значительно улучшилась, некоторые вещи кажутся сложными или плохо задокументированными. Например, у меня возникали трудности с воспроизводимым устранением зависимостей, потому что в официальном документе opam отсутствуют чёткие инструкции. В результате для поиска необходимых команд я прочитал исходники setup-ocaml, и найденные команды показались мне немного сложными (нужно «опубликовать» пакет локально, а затем установить локально опубликованный пакет). Было бы очень здорово, если бы существовала одна команда, устраняющая зависимости и собирающая код воспроизводимым образом.

Синтаксическая цена зависимости от абстракций

OCaml имеет высокую цену «зависимости от абстракций». Я покажу это на примере.

Допустим, у нас есть модули A, B и C с зависимостью A -> B -> C (A ссылается на B, который ссылается на C), как показано ниже.

module A = struct .. B.foo () .. end
module B = struct .. C.bar () .. end
module C = struct .. end

Допустим, мы хотим разорвать прописанную в коде зависимость между B и C. Иными словами, мы хотим сделать так, чтобы B зависел от интерфейса C, а не от конкретной реализации C. Например, это может пригодиться, если вы хотите заменить C на имитацию реализации в юнит-тесте B. Это можно сделать следующим образом:

1. Извлечь интерфейс C в сигнатуру C_intf
2. Определить B как функтор, получающий в качестве аргумента C_int

Результат этих изменений должен выглядеть так, как показано ниже. Обратите внимание, что B теперь является функтором, получающим модуль, удовлетворяющим интерфейсу C с именем C_intf.

module A              = struct .. B.foo () .. end
module B (C : C_intf) = struct .. C.bar () .. end
module C              = struct .. end

Но этот код не скомпилируется, потому что B, на который ссылается A, теперь является функтором, а не модулем. Следовательно, нам нужно повторить описанные выше шаги и абстрагировать B из A следующим образом:

module A (B : B_intf)          = struct .. B.foo () .. end
module B (C : C_intf) : B_intf = struct .. C.bar () .. end
module C                       = struct .. end

Давайте подробно посмотрим, что здесь произошло. Каждый из модулей имеет два типа зависимостей:

• (а) Как модуль зависит от других модулей
• (б) Как от модуля зависят другие модули

Мотивация преобразования модуля в функтор заключается в изменении (а), однако преобразование модуля в функтор также меняет и (б). Иными словами, преобразвание модуля в функтор не только меняет то, как модуль зависит от других модулей, но и то, как от него зависят другие модули.

Проблема будет серьёзнее, если множество модулей зависит от B или если граф зависимостей более глубокий.

Стоит заметить, что этого не произойдёт в парадигме ООП. Изменение конструктора класса B так, чтобы он получал интерфейс C_intf вместо конкретного класса C, не изменит тип самого класса B [Однако в ООП придётся расплачиваться динамической диспетчеризацией, которая в некоторых случаях может быть проблемой. Также, несмотря на поддержку ООП в OCaml, его использование может помешать читателям кода, потому что многие люди (в том числе и я) незнакомы с ООП-аспектом OCaml.].

Работая над CAMLBOY, я столкнулся с этой проблемой, когда пытался сделать реализацию картриджа переключаемой во время выполнения (у меня был граф зависимости Camlboy -> Bus -> Cartridge и я хотел только разъединить часть с Bus -> Cartridge).

Рекомендуемые материалы

Про OCaml

• Learn OCaml Workshop
  
  • Крайне рекомендую этот материал воркшопа, использованный в Jane Street. Он состоит из из кода OCaml с дырами и тестами, требующими для прохождения заполнения дыр, поэтому вы можете эффективно изучать OCaml на практике. Во второй части книги рассматриваются довольно сложные программы, например, Snake and Lumines, поэтому вы можете научиться тому, как эффективно разделять модули, как использовать систему сборки и т. п.
• Real World OCaml
  
  • Рекомендую эту книгу, если вы знаете базовый синтаксис OCaml или имеете опыт работы с другими функциональными языками. В нём излагаются знания, необходимые для создания «реальных» программ на OCaml с практическими примерами.

Про Game Boy

• The Ultimate Game Boy Talk
  
  • Отличное видео, в котором всего за час объясняется вся архитектура Game Boy. В процессе разработки я просмотрел его бесчисленное количество раз.
• gbops
  
  • Таблица с набором команд Game Boy. Здесь изложена информация, необходимая для декодирования команд.
• Game Boy CPU Manual
  
  • Руководство по ЦП. Я использовал это руководство для реализации команд. Стоит заметить, что некоторые части (особенно касающиеся флагов регистров) ошибочны.
• Pandocs
  
  • Вики с подробностями того, как должен работать каждый аппаратный модуль. Я постоянно обращался к этой вики при реализации GPU, таймера и т. п.
• Блог Имрана Назара
  
  • Туториал о том, как реализовать эмулятор Game Boy на JavaScript. Я прочитал его, чтобы иметь приблизительное понимание того, что нужно реализовать.