Сравнение интерпретатора, обычного и JIT компиляторов

Рассказывает автор блога Nick Desaulniers


Интерпретаторы и компиляторы — программы, которые используются для трансляции или запуска других программ. Интерпретируемые программы пишутся на языках вроде JavaScript, Ruby, Python, PHP и Perl. Программы, которым требуется компиляция — на C, C++ и, в какой-то степени, Java и C#.

Перевод в машинный код перед запуском (AOT — Ahead-Of-Time) занимает дополнительное время, однако даёт выигрыш в скорости работы. С другой стороны, интерпретатор может приступать к работе без задержек. Между этими двумя мирами есть золотая середина — JIT (Just-In-Time) компиляция. Интерпретация, обычная и JIT компиляция — эти способы могут выглядеть совершенно разными, но, на самом деле, они поразительно похожи. В этой статье я докажу это, продемонстрировав программные коды всех троих (для языка Brainfuck). Каждый занимает примерно 100 строк кода на C и доступен на GitHub.

Немного о самом Brainfuck

Brainfuck — очень интересный (правда, сложный для чтения) полный по Тьюрингу язык. У него есть всего 8 операторов — > < + - . , [ ]. Всё просто, каждый оператор — это символ, посторонние символы игнорируются. В этой статье мы пропустим валидацию кода, сосредоточившиь на интерпретации и компиляции.

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

  • > < — сдвигают указатель на одну ячейку вправо или влево соответственно;
  • + - — увеличивают или уменьшают значение в ячейке на единицу;
  • . — выводит в виде символа значение ячейки, на которой находится указатель;
  • , — записывает в виде ASCII кода введённое значение в ячейку, на которой находится указатель;
  • [ — если значение текущей ячейки нулевое, перейти вперёд к оператору ] (с учётом вложенности);
  • ] — если значение текущей ячейки не нулевое, перейти назад к оператору [ (c учётом вложенности).

Интерпретатор

  • Инициализация массива и указателя:
  • Операторы перемещения указателя:
  • Инкремент и декремент:
  • Ввод и вывод:
  • Операторы цикла:

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

Компилятор

Примечание: нижеследующий код предполагает, что вы работаете с x86-64 ISA (Instruction Set Architecture – Архитектура набора команд) и UNIX ABI (Application Binary Interface – Двоичный интерфейс приложений).

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

  • Для начала подготовим память для нашего компилятора:
    Если бы мы выделили 30000 байтов, то результатом выполнения memset стал бы segfault, ведь нам нужно место под указатели. Подробнее о работе со стеком в ассемблере вы можете прочитать в моей предыдущей статье (англ.)
  • С операторами сдвига указателя (> <) и инкремента\декремента (+ -) всё просто:
  • Для вывода (.) нам нужно скопировать байт с места, на котором стоит указатель, в место для первого аргумента putchar. Однако putchar принимает в качестве аргумента int. В x86-64 есть инструкция, котрая нам нужна – movzXX, где первый X — начальный размер (b, w), а второй — конечный (w, l, q).
  • Со вводом (,) всё тоже просто — вызываем getchar, перемещаем первые восемь бит в ячейку, помеченную указателем.
  • Как и в прошлый раз, с операторами цикла ([ и ]) работы будет больше. Хорошим решением будет использовать прыжки к соответствующим меткам, но проблема в том, что имена меток должны быть уникальными. Я предлагаю следующее — у нас будет переменная, в которой будет хранится количество встреченых открывающих скобок, и стек, в который каждый раз, когда будет встречена открывающая скобка, будет записываться её номер. Когда же будет встречена закрывающая скобка — ей будет соответствовать индекс верхнего элемента стека. Вот, как это выглядит в коде:
    Таким образом, для соседствующих циклов ([][]) ассемблерный код будет следующим:
    …А для вложенных ([[]]) — следующим (обратите внимание на индексы):
  • В конце нам нужно высвободить ресурсы:

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

Разве не было бы великолепно, если был бы способ совместить быстродействие компилятора и удобство интерпретатора? Такой способ есть — JIT компиляция.

JIT компилятор

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

Ещё одна особенность заключается в том, что мы будем передавать адреса наших libc функций (memset, putchar и getchar) нашим JIT функциям прямо во время исполнения. Я имею в виду, что мы будем делать так:

Итак, приступим.

Наш «пролог» — операции для подготовки памяти — достаточно сложный, поэтому я буду расписывать его пошагово.

  • Начнём как обычно:
  • Теперь нам нужно сохранить указатели на наши функции:
  • Затем выделим 30 008 байт на стеке:
    Здесь мы столкнулись с числом больше байта. Где же в этой инструкции число 30 008? Оно в следующих четырёх байтах: 0x38, 0x75, 0x00, 0x00. Замечу, что если человек привык воспринимать числа в системе «Big Endian», в которой младшие разряды находятся справа, то здесь необходимо использовать «Little Endian». То есть, 0x38, 0x75, 0x00, 0x00 в «Little Endian» — это 0x00, 0x00, 0x75, 0x38 в «Big Endian», оба обозначают 7*16^3+5*16^2+3*16^1+8*16^0 или 30008 в десятичной системе.
  • Теперь подготавливаем и запускаем memset:
  • На этом этапе нам больше не нужен memset, поэтому его место (%r12) занимает указатель на текущую ячейку:

С «прологом» на этом всё.

  • Добавим «пролог» в наш динамический массив:
  • Теперь перебираем символы Brainfuck программы. С инкрементом и декрементом всё по-старому:
    Дополнительный блок кода ({ char opcodes...}) нужен из-за того, что в C\C++ мы не можем создавать переменные прямо внутри switch.
  • Сдвиги указателя:
  • Ввод и вывод:
  • Мы дошли до операторов цикла — это самая интересная часть. При написании компилятора мы оставили вычисление оффсетов (отступов) ассемблеру. Теперь нам придётся самим решать следующую проблему: на сколько байтов нам нужно перескочить вперёд, чтоб мы попали к закрывающей скобке, которую мы ещё не видели? Мы поступим следующим образом:
    Сейчас мы оставили оффсет пустым (четыре нулевых байта), но мы позже вернёмся к этому. Сейчас мы записываем в relocation_table текущий размер массива инструкций, а по совместительству — место последней встреченной открывающей скобки. Вся магия раскрывается, когда мы встретим закрывающую скобку. Сначала мы просто записываем незаконченные инструкции в динамический массив, как и в случае с открывающей скобкой:
    …Затем мы вычисляем оффсет:
    …А теперь записываем его вместо нулей (4 — не магическая константа, это количество байт, которые мы оставили пустыми):
  • Снова подчищаем за собой:
  • Теперь запускаем наши инструкции и чистим всё в последний раз:

Тесты, сравнение и заключение

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

  • Интерпретатор:
  • Компилятор:
  • JIT компилятор:

Или сравните исходники интерпретатора, обычного и JIT компиляторов.

Давайте теперь проверим их быстродействие. Одна из самых «тяжёлых» программ, которую я смог найти — вывод в консоль множества Мандельброта в виде ASCII арта.

Интерпретатор оказался гораздо медленнее остальных — это из-за того, что его переходы по [ ] выполняются за О(N), когда остальные имеют возможность выполнить прыжок за О(1). Интерпретатор просматривает исходник в поисках оператора, затем его выполняет, после чего снова возращается к файлу. Компиляторы сначала транслируют код, затем выполняют его, не смешивая.

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

Теперь он работает чуть-чуть дольше, чем JIT. Какой из этого можно сделать вывод? Если время компиляции невелико (как у Brainfuck) — стоит выбирать JIT компилятор. Однако, если вам необходимо выполнять массивные программы на настоящих языках, а время компиляции будет значительным — вы явно захотите потратить время на компиляцию лишь один раз, а значит — выберете обычный компилятор.

Перевод статьи «Interpreter, Compiler, JIT»