На протяжении более двух лет я много времени уделял разработке моего собственного эмулятора Game Boy, GameRoy. Я немало успел сделать. В эмуляторе был готов графический пользовательский интерфейс (с отладчиком и дизассемблером), сама программа прошла многочисленные тесты и могла сравниться с некоторыми наиболее точными эмуляторами. Я даже портировал её на Android!

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

Вновь вдохновившись JIT-компиляторами (например, такими, которые используются в Java, JavaScript и LuaJIT), постами Dolphin о разработке, а прежде всего вот этой статьёй в блоге Брука Гейслера о JIT-компиляторе для NES, я принялся за реализацию такого механизма у себя в эмуляторе.

Вот в чём заключался один момент в посте Гейслера, заинтриговавший меня: оказывается, не так просто обрабатывать прерывания в скомпилированном коде. При разработке JIT-компилятора Гейслер столкнулся с необходимостью выбирать между производительностью и точностью, когда решал, как будет обращаться с прерываниями в своём эмуляторе. В конечном счёте, он решил пожертвовать производительностью в пользу точности, но меня такой подход не устраивал.

Слегка поразмыслив, я нашёл решение этой проблемы, то есть способ добиться максимальной производительности без ущерба для точности.

В этой статье я опишу весь процесс, а также расскажу, из каких соображений я решил реализовывать JIT-компилятор у меня в эмуляторе, и как я решил проблему с обработкой прерываний.

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

Интерпретатор, помноженный на динамическую компиляцию

Задача эмулятора — воспроизвести поведение некоей компьютерной системы на программном уровне. Такая система, в том числе Game Boy, состоит из множества компонентов, каждый из которых требуется эмулировать. Среди них выделяется ЦП как наиболее важный, поскольку именно процессор отвечает непосредственно за выполнение инструкций той программы, которую вы собираетесь воспроизводить у себя в эмуляторе.

Существует два основных способа эмулировать ЦП (или любой программируемый компонент).

Элементарный интерпретатор

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

Что касается Game Boy, мы будем выполнять инструкции, считывая их байт за байтом (поскольку Game Boy — это 8-битная система) из того адреса в памяти, на который указывает счётчик команд (PC), причём значение PC увеличивается на единицу после каждой операции считывания. Для декодирования инструкции обычно нужен только первый байт этой инструкции. Поскольку в любом байте может содержаться не более 255 возможных значений, можно построить таблицу поиска. В ЦП Game Boy также есть инструкции с префиксом 0xCB, которые декодируются, начиная со второго байта, для работы с ними воспользуемся другой таблицей поиска.

Я реализую мой эмулятор на Rust, поэтому для декодирования инструкции могу воспользоваться оператором match. Каждая ветка match ведёт к функции, реализующей выполнение некоторой инструкции. Эта функция читает регистры или память либо записывает в них, а при необходимости и считывает из инструкций дополнительные байты (напр., при работе со значениями, подставляемыми в коде (immediate values), такими, как адрес инструкции перехода).

В очень упрощённом виде интерпретатор можно изобразить примерно так:

fn interpret_instruction(gb: &mut GameBoy) {
    let opcode = gb.read(gb.cpu.pc);
    gb.cpu.pc += 1;
    match opcode {
        0x00 => nop(gb),
        0x01 => load_bc_im16(gb),
        0x02 => load_bc_a(gb),
        0x03 => inc_bc(gb),
        0x04 => inc_b(gb),
        // Ещё 252 подобные ветки...
    }
}

// ...

// INC B 1:4 Z 0 H -
fn inc_b(gb: &mut GameBoy) {
    gb.cpu.b += 1;    // увеличиваем B на единицу
    gb.cpu.f &= 0x1F; // очищаем флаги Z, N, H 
    if gb.cpu.b == 0 { gb.cpu.f |= 0x80; }       // устанавливаем флаг Z в 0
    if gb.cpu.b & 0xF == 0 { gb.cpu.f |= 0x80; } // Устанавливаем флаг H в значение полупереноса
}

Функция interpret_instruction вызывается в виде цикла и выполняет по одной инструкции за итерацию.

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

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

Но это не проблема как минимум в случае с GameBoy, тактовая частота процессора в котором едва превышает 1 МГц, тогда как вы, вероятно, можете эмулировать его на процессоре с тактовой частотой свыше 1 ГГц. Фактически, GameRoy может выполнять игры для Game Boy примерно в 60 раз быстрее, чем на оригинальной системе — и это на моём ноутбуке, где стоит процессор Intel i5-4200U с тактовой частотой 2,6 ГГц.

Даже если так, получается в 41 раз медленнее, чем теоретически можно было бы выполнять код на моём ЦП. Но компенсировать этот разрыв можно при помощи очень интересной техники, которая называется рекомпиляция.

Элементарный JIT-компилятор

Второй способ эмулировать ЦП — транслировать инструкции ЦП Game Boy в инструкции ЦП хоста, а затем их выполнять. Такой подход называется «рекомпиляция». Применительно к Game Boy, как и ко многим другим системам, невозможно заранее перекомпилировать код, содержащийся в программе (то есть не работает статическая рекомпиляция). Поэтому такую трансляцию приходится осуществлять во время выполнения, и в таком случае мы имеем дело с  динамической рекомпиляцией, она же JIT-компиляция (или просто JIT).

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

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

В упрощённом виде код компилятора будет выглядеть примерно так:

fn compile_instruction(ctx: &mut JitCompiler, gb: &GameBoy, code: &mut Vec<u8>) {
    let opcode = gb.read(ctx.curr_pc);
    match opcode {
        0x00 => nop(ctx, gb),
        0x01 => load_bc_im16(ctx, gb),
        0x02 => load_bc_a(ctx, gb),
        0x03 => inc_bc(ctx, gb),
        0x04 => inc_b(ctx, gb),
        // ещё примерно 252 такие ветки ...
    }
}

// ...

// INC B 1:4 Z 0 H -
fn inc_b(_: &mut JitCompiler, code: &mut Vec<u8>) {
    code.extend(&[
        0x0f, 0xb6, 0x47, 0x01, // movzx  eax,BYTE PTR [rdi+0x1] ; читаем F
        0x0f, 0xb6, 0x4f, 0x02, // movzx  ecx,BYTE PTR [rdi+0x2] ; читаем B
        0xfe, 0xc1,             // inc    cl                     ; увеличиваем B
        0x88, 0x4f, 0x02,       // mov    BYTE PTR [rdi+0x2],cl  ; пишем B
        0x24, 0x1f,             // and    al,0x1f                ; очищаем флаги Z, N, H 
        0x8d, 0x50, 0x80,       // lea    edx,[rax-0x80]         ; вычисляем флаги...
        0x0f, 0xb6, 0xc0,       // movzx  eax,al                 ; ...
        0x0f, 0xb6, 0xd2,       // movzx  edx,dl
        0x0f, 0x45, 0xd0,       // cmovne edx,eax
        0x8d, 0x42, 0x20,       // lea    eax,[rdx+0x20]
        0xf6, 0xc1, 0x0f,       // test   cl,0xf
        0x0f, 0xb6, 0xc0,       // movzx  eax,al
        0x0f, 0x45, 0xc2,       // cmovne eax,edx
        0x88, 0x47, 0x01,       // mov    BYTE PTR [rdi+0x1],al  ; пишем F
    ]);
}

Эта функция compile_instruction читает и декодирует инструкцию, а затем заносит в буфер машинный код, выполняющий эту инструкцию.

(Для любознательных: я получил этот ассемблерный/машинный код, просто реализовав инструкцию Rust, а потом дизассемблировав её с помощью objdump -d.)

Итак, чтобы создать JIT-компилятор, нужно всего лишь применить compile_instruction к последовательности инструкций, начиная с того адреса, на котором сейчас стоит счётчик команд. После этого код нужно записать на страницу памятью с правом исполнения (для этого можно воспользоваться специальным пакетом Rust, например memmap2), превратить её в указатель функции и вызвать! Вот и всё.

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

На этом можно считать, что основы JIT-компилятора продемонстрированы.

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

Оптимизации

Чем особенно хорош компилируемый код — так это тем, как удобно его оптимизировать. Например, одна из (немногих) оптимизаций, которые я внёс в мой эмулятор через JIT-компилятор заключается в том, что удалось пропустить ненужные вычисления флагов (эту идею я непосредственно позаимствовал из поста Брука Гейслера).

Если вы пытались вчитаться в ассемблерный код и понять, что он делает, то могли заметить: одна из четырёх инструкций используется для приращения значения регистра B, a остальные 10 обновляют условные флаги в регистре F. Но значение в F может быть затёрто следующими инструкциями прежде чем, к примеру, мы успеем прочитать его через инструкцию условного перехода. В таком сценарии обновление значения F никак не повлияет на ход эмуляции, поэтому, вычисляя его, мы тратим ресурсы впустую.

Если мы компилируем все эти инструкции вместе, то можем заметить развитие именно такого сценария и пропустить вычисление флага. В таком случае мы значительно сократим выдаваемый код!

// INC B 1:4 Z 0 H -
fn inc_b(ctx: &mut JitCompiler, code: &mut Vec<u8>) {
    if !ctx.flag_is_need {
        code.extend(&[0xfe, 0x47, 0x02]); // инкремент BYTE PTR [rdi+0x2]
        return;
    }

    code.extend(&[
        0x0f, 0xb6, 0x47, 0x01, // movzx  eax,BYTE PTR [rdi+0x1] ; читаем F
        0x0f, 0xb6, 0x4f, 0x02, // movzx  ecx,BYTE PTR [rdi+0x2] ; читаем B
        0xfe, 0xc1,             // inc    cl                     ; увеличиваем B
        0x88, 0x4f, 0x02,       // mov    BYTE PTR [rdi+0x2],cl  ; пишем B
        0x24, 0x1f,             // and    al,0x1f                ; очищаем флаги Z, N, H 
        0x8d, 0x50, 0x80,       // lea    edx,[rax-0x80]         ; вычисляем флаги...
        0x0f, 0xb6, 0xc0,       // movzx  eax,al                 ; ...
        0x0f, 0xb6, 0xd2,       // movzx  edx,dl
        0x0f, 0x45, 0xd0,       // cmovne edx,eax
        0x8d, 0x42, 0x20,       // lea    eax,[rdx+0x20]
        0xf6, 0xc1, 0x0f,       // test   cl,0xf
        0x0f, 0xb6, 0xc0,       // movzx  eax,al
        0x0f, 0x45, 0xc2,       // cmovne eax,edx
        0x88, 0x47, 0x01,       // mov    BYTE PTR [rdi+0x1],al  ; пишем F
    ]);
}

Фантастика! Оптимизированная версия получилась в 14 раз меньше неоптимизированной!

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

Но мой эмулятор (как минимум, пока) рассчитан только на работу с машинным кодом для архитектуры x86-64. Поэтому я воздержусь от использования каких-либо подобных инструментов.

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

Прерывания

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

В Game Boy существует множество источников прерываний, инициируемых различными компонентами. Поэтому для обработки прерываний эти компоненты также нужно обновлять.

Если же вы хотите сделать достаточно точный эмулятор, то обновлять компоненты и проверять наличие прерываний придётся перед каждой инструкцией. Более того, если вы стремитесь добиться точности до единого цикла, то компоненты также потребуется обновлять перед каждым обращением к памяти. Это можно сделать, например, при помощи функции tick.

Наш интерпретатор примет примерно следующий вид:

fn interpret_instruction(gb: &mut GameBoy) {
    if gb.interrupts_enabled & gb.interrupts_flags != 0 {
        // здесь мы записываем в стек и переставляем счётчик команд на обработчик прерываний
        handle_interrupt(gb);
    }

    let opcode = gb.read(gb.cpu.pc);
    gb.cpu.pc += 1;
    tick(gb, 4); // на каждое обращение к памяти уходит 4 цикла
    match opcode {
        // ...
        0x36 => ld_hl_im8(gb),
    }
}

fn tick(gb: &mut GameBoy, cycles: u64) {
    gb.clock_count += cycles;

    gb.update_timer(clock_count);
    gb.update_ppu(clock_count);
    gb.update_sound_controller(clock_count);
    gb.update_serial(clock_count);
}

// LD (HL),d8 2:12 - - - -
fn ld_hl_im8(gb: &mut GameBoy) {
    let value = gb.read(gb.cpu.pc);
    gb.cpu.pc += 1;
    tick(gb, 4);

    let address = gb.cpu.h as u16 * 0x100 + gb.cpu.l as u16;
    gb.write(address, value);
    tick(gb, 4);
}

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

Но обработка прерываний — это проблема для JIT-компилятора. Если постоянно проверять, не появились ли новые прерывания, то мы не только получим значительные издержки, но и лишимся возможности применять многие оптимизации, которые хотели бы сделать, например пропускать расчёты. Дело в том, что код постоянно должен быть готов к ветвлению с переходом на обработчик прерываний.

Можете попробовать проверять прерывания всего лишь раз в 10 инструкций или примерно так; для большинства игр (но не для всех) этого должно хватить. Но в моём эмуляторе я стремлюсь к максимальной точности. Суть JIT-компилятора — определить, можно ли её добиться, не жертвуя производительностью.

И я догадался, как это сделать: оценивать, когда произойдёт следующее прерывание.

Оценка следующего прерывания

Вот как работает JIT-компилятор в GameRoy: зная адрес регистра, по которому сейчас находится счётчик команд, и зная банк, который в данный момент отображается на этот адрес, компилятор создаёт блок инструкций, начиная с этого адреса. Затем этот блок компилируется в машинный код и сохраняется в кэше.

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

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

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

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

К счастью, в случае с компонентами для Game Boy можно оценить момент следующего прерывания в пределах константного времени. Но реализовать такое оценивание всё равно непросто, так как возникает множество пограничных случаев. Благодаря тому, что я проделал обширное фаззинговое тестирование, я в достаточной степени уверен, что всё реализовал правильно.

Если вы хотите сами посмотреть, как выглядит реализация — вот ссылки на таймер, на физический процессор и на последовательные операции. Фаззинг-тесты находятся внизу того же файла, если вы захотите и их посмотреть.

Ленивое обновление

На этом проблема с прерываниями решена! Но нам по-прежнему требуется обновлять компоненты. К счастью, обновлять компоненты нам придётся только перед обращением к тому адресу в памяти, на который отображается компонент, или непосредственно перед срабатыванием прерывания. Поэтому мы можем просто обновить компоненты в функции обращения к памяти, прямо перед операцией чтения из памяти или записи в память и перед тем, как будем проверять прерывания в интерпретаторе.

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

Хороший пример — реализация физического процессора. Физический процессор — это компонент, отвечающий за преобразование тайловой карты и информации о спрайтах в экранные пиксели. Конечный результат рендеринга не составляет труда эмулировать, если входные данные не меняются. Но, поскольку необходимо учитывать, что в процессе рендеринга ЦП всё-таки может менять входные данные, приходится эмулировать сложное внутреннее устройство физического процессора.

Правда, при ленивом обновлении физического процессора мы можем быть уверены, что с момента последнего обновления никаких изменений не произошло. Благодаря этому мы не связываемся с большинством сложных деталей физического процессора, а лишь эмулируем конечный результат рендеринга — и получается гораздо быстрее.

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

Функция draw_scan_line отображает линию развёртки экрана в окончательном виде, не эмулируя всего того, что происходит внутри физического процессора. Посчитав, видим, что при эмуляции физического процессора получаем ускорение почти в 10 раз, а общая скорость эмулятора возрастает в четыре раза.

Здесь стоит отметить, что до оптимизации лишь 14% всего времени тратилось на ЦП. Таким образом, эмуляция ЦП едва ли является самым узким местом в нашем проекте, и JIT-компилятор значительного ускорения не даст. Но после внесённых оптимизаций на эмуляцию ЦП уходит 63% времени, поэтому для JIT открывается пространство, позволяющее блеснуть.

Подробнее о компиляторе

Выше я предоставил лишь упрощённую и минимально работоспособную версию JIT-компилятора. Но в фактической реализации придётся подумать и о многих других деталях.

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

В настоящий момент блоки — это просто линейные последовательности инструкций, но мы вполне можем расширить трассировку блока до прослеживания веток и потенциально компилировать за раз большие участки программы. Правда, в данном случае предложенное мной кэширование блоков слишком далеко от идеала (об этом я расскажу в разделе «Что осталось сделать»).

Здесь важно отметить, что я отслеживаю блоки только в случаях, когда счётчик команд указывает на адрес в ROM-памяти (диапазон от 0x0000 до 0xFFFF). Если указатель направлен за пределы этого диапазона, например в RAM, я просто откатываюсь к работе с интерпретатором. Таким образом мне не приходится иметь дело с самоизменяемым кодом, который является общей проблемой для динамических рекомпиляторов. Кроме того, в играх обычно не так много кода выполняется в RAM, так что невелика потеря.

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

Закончив трассировку блока, компилятор делает из него функцию. Он выдаёт машинный код для пролога функции (выравнивает стек, помещает в него регистры, т.д.), а затем выдаёт машинный код для каждой инструкции.

Инструкции, обновляющие регистры, будут работать подобно той, которую я привёл выше в качестве примера. Они просто загружают регистры из памяти, выполняют операцию и сохраняют регистры обратно. Значительно эффективнее было бы как можно дольше держать память Game Boy в регистрах x86-64, но я эту возможность до сих пор не реализовал.

Инструкции, которые могут ветвиться, проверяют, находится ли искомый адрес внутри блока, и если так — выдают переход к адресу внутри блока. В данном случае для выдачи пакетов используется вспомогательный пакет dynasm. Если искомый адрес не находится в блоке, то инструкция просто выдаёт пролог для блока (выталкивает регистры и вызывает ret).

Инструкции, читающие память или записывающие в неё выдают вызовы, направляемые к функциям Rust, обрабатывающим доступ к памяти. Таким образом, мне удаётся обрабатывать случаи, в которых может меняться состояние эмулятора, например, при ленивом обновлении компонентов. Но обращение к памяти по явно указанному адресу может выдаваться встроенным в функцию, если это возможно.

Ещё один важный момент: операция записи в память может спровоцировать прерывание или, как минимум, повлиять на хронометраж выполнения. Таким образом, после каждой операции записи компилятору приходится лишний раз проверять, не было ли прерываний и при необходимости выходить из функции. То же касается и переключения банков: при записи в ROM может смениться банк, за выполнением которого мы застали программу. Поэтому нужно проверить, не произошло ли такого изменения, и если да — выйти из блока.

Кроме того, поскольку операции записи могут провоцировать прерывания, а при прерываниях могут происходить операции чтения флагов, каждая запись также вредит оптимизациям, действующим на уровне инструкций — например, пропускать вычисление флагов, о чём я упоминал выше.

Поскольку теперь в блоке повсюду присутствует множество прерываний, при каждой проверке мы всего лишь должны убедиться, что следующее прерывание не произойдёт ранее следующей проверки прерываний. Это касается и первичной проверки, выполняемой перед входом в блок.

Закончив выдачу блока, компилятор перемещает буфер с машинным кодом в исполняемую область памяти и сохраняет его в HashMap, который отображает (bank, address)на блок. Теперь, как только эмулятору снова потребуется выполнить этот блок, он просто берёт его из HashMap (или компилирует его, если пока он там отсутствует).

Результаты

В сущности, JIT-компилятор реализуется ради повышения производительности эмулятора. Итак, насколько мне удалось ускорить работу эмулятора?

Сначала давайте сравним скорость интерпретатора и JIT-компилятора. Для этого я погонял в эмуляторе две разные игры и измерил, сколько процессорного времени уходит на выполнение каждой игры в течение 100 секунд. Первая игра — The Legend of Zelda: Link’s Awakening, вторая — Tobu Tobu Girl. В обеих играх есть красивая анимация на экране-заставке, по которой удобно судить о скорости эмулятора.

Эмулятор смог воспроизвести Tobu Tobu Girl более чем в 100 раз быстрее, чем реальная система! Однако, сравнив две реализации, можем увидеть, что в случае с Tobu Tobu Girl JIT-компилятор справляется с выполнением программы примерно на 40% процентов быстрее, и в случае с Zelda на 30% быстрее. Не столь серьёзное ускорение, какое я ожидал увидеть, но всё равно очень значительное.

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

На приведённой круговой диаграмме видно, что значительная доля времени тратится на эмуляцию физического процессора. Как видим, в Zelda гораздо меньше возможностей оптимизировать физический процессор — следовательно, за работой с этим процессором приходится проводить больше времени. Именно поэтому игра выполняется гораздо медленнее и ускорение получается меньше.

Если отдельно рассматривать секторы интерпретатора (синий) и JIT (красный), можно грубо оценить, что JIT-компилятор работает примерно вчетверо быстрее интерпретатора. Правда, значительное количество времени всё равно тратится просто на запрашивание блока в HashMap. Причём, даже при работе с JIT-компилятором какое-то время затрачивается на работу с интерпретатором.

Можно исследовать ещё один аспект: сравнить наш эмулятор с другими имеющимися. Я выбрал 5 относительно популярных эмуляторов, отличающихся высокой точностью: SameBoy, BGB, Beaten Dying Moon, Emulicious и Gambatte-Speedrun.

Чтобы составить впечатление, насколько точен каждый эмулятор, можно просто протестировать их в GBEmulatorShootout и просмотреть результаты. Обратите внимание: эти тесты затрагивают версии Game Boy DMG, GBC и SGB, но GameRoy эмулирует только DMG, поэтому, очевидно, он немного уступает остальным.

Эти эмуляторы выполнялись на Windows, с применяемым по умолчанию GUI, сконфигурированным для эмуляции DMG. Причём там включён «турбо-режим» или «быстрая перемотка вперёд», или как его ещё называют. Поскольку работа идёт через GUI, измерения основаны на записи видео, а заставка проматывается всего два-три раза, поэтому результаты не слишком точные. Но, надеюсь, они вполне хороши, чтобы сравнить эмуляторы друг с другом.

Чтобы измерить производительность каждого из эмуляторов, я, как и в прошлый раз, прогнал две игры и измерил, сколько времени уходит на воспроизведение анимации на экране-заставке каждой игры. Видео я записывал при помощи OBS Studio. Экран-заставку Tobu Tobu Girl я прогонял три раза, а экран-заставку Zelda — два раза.

Здесь важно отметить, что и BGB, и Gambatte (как минимум — эти два, насчёт остальных я не уверен, но, возможно, там ситуация схожая) действуют оптимизации, пропускающие некоторые кадры с ЖК-экрана. Такую функцию я пока не реализовал. В BGB эту оптимизацию можно отключить, поэтому я включил её в бенчмарки, чтобы получилось более прямое сравнение производительности. В Gambatte такую оптимизацию отключить невозможно.

Вот результаты:

Исходя из этих результатов (и если игнорировать эмуляторы, в которых применяется оптимизация путём пропуска кадров и, соответственно, бенчмарки получаются не такими строгими), могу утверждать, что GameRoy — самый быстрый эмулятор!

Интересно, что даже интерпретируемая версия моего эмулятора быстрее других эмуляторов выполняет Tobu Tobu Girl. Наверное, дело в оптимизации физического процессора, достигаемой путём ленивых обновлений и оценки того, когда наступит следующее прерывание. Делаю такой вывод, так как Legend of Zelda всё равно сравнима по скорости с той же игрой в других эмуляторах, то есть на эту игру не столь влияет оптимизация физического процессора.

Но Gambatte и BGB (в обоих применяется оптимизация через пропуск кадров) значительно обгоняют GameRoy. BGB получается более чем впятеро быстрее неоптимизированной версии (которая ближе по скорости к той моей версии GameRoy, что работает через интерпретатор и с оптимизированным физическим процессором — в ней я добился четырёхкратного ускорения). Такая версия BGB более чем в два раза обгоняет GameRoy.

Если бы и мне удалось сделать оптимизацию с пропуском кадров, вплоть до того, чтобы как-нибудь совсем исключить любые траты времени в физическом процессоре, то мой эмулятор ускорился бы ещё вдвое по сравнению с современным состоянием — но даже тогда он не обставил бы BGB. Поэтому, может быть, я немного преувеличиваю, называя GameRoy самым быстрым эмулятором.

Что осталось сделать

Возможно, сейчас я выжал максимум из динамической рекомпиляции как средства для ускорения эмуляции Game Boy (единственный подобный проект, который мне известен — JitBoy), но моя реализация всё равно ещё далека от совершенства.

Во-первых, я не применяю некоторые напрашивающиеся оптимизации. Например, я не держу регистры x64 заполненными (то есть не держу в них регистры Game Boy). Вместо этого я загружаю их на каждой инструкции и сохраняю в памяти. Единственный регистр, который я оптимизировал — тот, в котором содержится счётчик команд. Поскольку я знаю значение этого регистра уже во время компиляции, я обновляю его только при выходе из блока.

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

Но я, пожалуй, не буду внедрять эти оптимизации, как минимум – напрямую. Вместо этого я  планирую написать для компилятора новую серверную часть при помощи Cranelift, так как этот инструмент, вероятно, позволит автоматически обрабатывать эти оптимизации — и не только. Ранее я уже немного экспериментировал с этим инструментом и, как мне кажется, он работает довольно хорошо. Кроме того, с его помощью я портировал JIT-компилятор для работы на Android.

Ещё один источник неэффективности в моём JIT-компиляторе связан с избыточными перекомпиляциями. В настоящее время я делаю целый блок для каждой входной точки (bank, address), даже если тот же самый адрес уже находится в центре другого блока. Это означает, что многие блоки взаимно перекрываются, из-за чего без необходимости увеличивается время компиляции и сильнее расходуется память.

Не знаю, насколько это серьёзная проблема (чтобы это проверить, потребуется кое-какое профилирование), но её можно было бы исправить, включив в HashMap ключ для адреса каждой инструкции в блоке, а прелюдию блока перенеся голую функцию Rust. После этого переходим в середину блока.

Правда, при этом возникли бы некоторые осложнения. Например, HashMap чрезмерно заполнился бы ключами, а мы должны были бы гарантировать, что можно напрямую перейти к каждой скомпилированной инструкции. Последний момент особенно сложно оптимизировать, однако, возможно, мне ещё просто нужно побольше об этом поразмыслить.

Заключение

Вот и всё! Мне не удалось добиться такого значительного ускорения, на которое я рассчитывал, но всё равно, я смог написать самый быстрый эмулятор в своей категории, пусть сгенерированный код и далеко не оптимален.

Я бы хотел поблагодарить Брука Гейслера за его статью “Experiments In NES JIT Compilation”, которая и вдохновила меня на эти эксперименты. Там же я взял несколько полезных ссылок о том, как реализовать JIT-компилятор, например, серию Эли Бендерского «Adventures In JIT Compilation». Его проект я в качестве самостоятельного упражнения повторно реализовал на Rust.

Если вы хотите посмотреть на GameRoy, приглашаю вас взглянуть на него в моём репозитории на GitHub.