Около шестнадцати лет назад вышла первая версия Hotspot – реализация JVM, впоследствии ставшая стандартной виртуальной машиной, поставляемой в комплекте JRE от Sun.
Основным отличием этой реализации стал JIT-компилятор, благодаря которому заявления про медленную Джаву во-многих случаях стали совсем несостоятельными.
Сейчас почти все интерпретируемые платформы, такие как CLR, Python, Ruby, Perl, и даже замечательный язык программирования R, обзавелись своими реализациями JIT-трансляторов.
В рамках этой статьи я не планирую проливать свет на малоизвестные детали реализации промышленных JIT-компиляторов, скорее это будет совсем поверхностное ознакомление с азами и рассказ про учебный проект по соответствующей тематике.
Таким образом вам может быть интересно под катом, если:
- Вы принципиально не понимаете, что такое JIT-компилятор, или у вас есть легкое непонимание, чем такой подход существенно лучше интерпретации.
- Вы хотели бы написать простой JIT для своего интерпретируемого языка.
- Вы преподаете курс «Языки программирования и компиляторы», и не против сделать практическое задание для студентов еще интересней.
- Вам интересно, как нарисована эта картинка.
Преимущества JIT-компиляции
Чтобы говорить о преимуществах сначала разберемся, с тем, что это такое. Начнем издалека, а именно с определения компилируемого языка.
Компилируемый язык программирования — язык программирования, исходный код которого преобразуется компилятором в машинный код конкретной архитектуры, например x86/ARM. Этот машинный код представляет собой последовательность команд, которая совсем понятна вашему процессору, и может быть исполнена им без посредника.
Интерпретируемые языки программирования отличаются тем, что исходники не преобразовываются в машинный код для непосредственного выполнения на ЦПУ, а исполняются с помощью специальной программы-интерпретатора.
Как промежуточный вариант, многие языки (Java, C#, Python) транслируются в машинно-независимый байт-код,
который все еще не может быть исполнен напрямую на ЦПУ, и чтобы его исполнить все еще необходим интерпретатор.
Почему интерпретация медленней? Ответ на этот вопрос, как ни странно не всем кажется очевидным, хотя он действительно очень простой: интерпретируя каждую команду по отдельности, мы затрачиваем дополнительные ресурсы на перевод семантики этой команды на язык процессора. Кроме того современные процессоры оптимизированы для выполнения последовательных команд (см. Конвейер), а интерпретатор чаще всего представляет собой огромный switch с кучей опций, загоняющий в тупик предсказатель переходов.
Вполне естественным решением всех этих проблем было бы лишь однажды перевести байт-код на язык процессора и передать его ЦПУ для исполнения. Так чаще всего и поступают, называя этот процесс Just-in-time-компиляцией (JIT). Кроме того, именно в течение этой фазы чаще всего проводятся различные оптимизации генерируемого кода.
Теперь перейдем к практике.
Постановка задачи
Курс “Виртуализация и виртуальные машины” в нашем университете читает Николай Иготти, принимавший участие в разработке самых разных классов ВМ: Hotspot, VirtualBox, NativeClient, и не понаслышке знающий детали их реализации. Благодаря чудесам современных технологий, чтобы узнать про это все подробней необязательно даже быть студентом Академического Университета, так как курс опубликован на лекториуме. Хотя нужно отметить, что это конечно немного не то, в силу интерактивности курса и работе с аудиторией на лекциях.
В рамках курса для получения допуска к экзамену студентам было предложено написать свою реализацию простой стековой виртуальной машины-интерпретатора и транслятор в байт-код из C-подобного языка. На самом деле задание несколько проще, чем может показаться на первый взгляд – вместе с заданием выдается много готового кода на C++:
- Парсер в AST того самого языка программирования, который нужно транслировать. За это огромное спасибо! Обычно к шестому курсу студенты АУ успевают написать по шестнадцать различных парсеров, и писать еще один рекурсивный спуск совсем неинтересно.
- Список типов инструкций байт-кода в виде enum’а с подробными комментариями.
- Утилитные классы для работы с байт-кодом: его конструирование и работа с бинарным представлением.
Кодовое название у всего этого задания – mathvm, видимо в силу того, что основная цель языка программирования, как это часто бывает, что-нибудь посчитать.
Типичная программа на языке mathvm:
function int fib(int x) {
if (x <= 1) {
return x;
}
int r = fib(x - 1);
return r + fib(x - 2);
}
print(fib(35), 'n');
Основные возможности языка:
- Работа с типами данных: int, double, string, арифметика над ними.
- Стандартные управляющие конструкции: if, while, for, print.
- Возможность объявления функций внутри функций, как следствие наличие замыканий. Эта фича, хоть и вызвала множество вопросов при проектировании интерпретатора, однако, с учетом наличия инструкций для работы с замыканиями не стала камнем преткновения.
- Возможность декларации native-функций. То есть можно объявить функцию без тела с пометкой native и именем символа, который может быть загружен виртуальной машиной через dlsym с параметром RTLD_DEFAULT.
Например так:function void printfIDS(string format, int x1, double x2, string x3) native ‘printf’; printfIDS(‘%d %f %sn’, 1, 2, ‘abc’);
Мне кажется именно последний пункт делает задание намного веселей:
- Во-первых не сразу понятно, как можно передать в функцию заранее неизвестное множество аргументов, если в рантайме у вас есть указатель на функцию, сигнатура и вычисленные аргументы сохранены в определенное место в памяти. Более-менее ясно, что совсем кроссплатформенно это сделать не удастся, и как минимум нужно зафиксировать Calling conventions. Мы сошлись на соглашении о вызовах из System V ABI, использующегося в популярных unix-системах.
Но даже после этого не кажется очевидным, как наиболее безболезненно достичь цели.
Единственное, что приходило в голову – огромная, страшная ассемблерная вставка с кодом, который раскладывает аргументы по соответствующим регистрам и ячейкам стека. В результате я выбрал немного другое решение, которое опишу ниже. - Native-функции значительно расширяют возможности получаемого языка. Когда после нескольких дней угара интерпретатор и транслятор готовы, и вместо унылого численного интегрирования трапециями, на вашем детище запускается что-нибудь такое и рисует на экране крутую психоделическую анимацию (см. скриншот в начале статьи), это является приятным бонусом.
Внимательный читатель мог заметить, что в программе из последнего пункта зачем-то вычисляется количество отрисовываемых кадров в секунду (FPS). Этот показатель позволяет оценить производительность интерпретатора и позволяет таким образом привнести соревновательный дух в казавшийся кому-то скучным учебный процесс.
Студент, интерпретатор которого будет самым быстрым на этом и еще паре подобных бенчмарков, автоматически сдает экзамен, а кроме того получает любовь и уважение коллег. Надо отметить, что мы не первый поток, с которым играли в эту игру, и обычно для победы нужно было реализовать JIT-компилятор.
Сложности
Казалось бы, что существенно сложного в том, чтобы просто перевести семантику несложных байт-код инструкций в соответствующие элементы набора инструкций x86?
- Если бы у нас был компилируемый язык, то мы бы могли буквально сгенерировать текст на языке ассемблера, затем соответственно ассемблировать, получив в результате исполняемый файл.
Но в рамках JIT-трансляции разделять процесс на две эти фазы – непозволительная роскошь, и нужно как-то сразу научиться генерировать в памяти процесса ВМ машинный код. - Да и не любая область памяти подойдет для записи машинного кода. Точнее записать-то можно куда угодно, но вот передать исполнение можно только на область памяти, страницы которой отмечены как исполняемые. Кажется тут не обойтись простым malloc’ом.
- В идеале, конечно, чтобы получаемый машинный код работал как можно быстрее.
Asmjit
Для решения первых двух проблем вполне подходит Asmjit – библиотека с открытым исходным кодом, развиваемая по большей части одним человеком в течение последних нескольких лет, и используемая в других проектах автора, а также в JIT для скриптов на сервере GTA San Andreas MP.
Как несложно понять из названия, её основная миссия – создание удобного API для генерации машинного кода Just-in-time. Eё публичный интерфейс можно разделить на две части:
- X86Assembler – низкоуровневый интерфейс, который по сути позволяет делать три вещи:
- Инициировать выделение куска памяти с привилегиями на исполнение.
- Располагать в нем инструкции/данные последовательно и заводить метки для мест, куда существуют переходы из других участков кода.
Для работы с кодом в библиотеке есть набор классов-операндов: GpReg, XmmReg, Imm, Mem, а для каждой инструкции в классе есть одноименный метод, причем ровно с тем набором перегрузок, которые допустимы для данной инструкции. Например метод с сигнатурой mov(X86Mem &, X86Mem &) отсутствует, как и должно быть. - Получение указателя на начало заполненного куска памяти, который можно использовать, как указатель на функцию-точку входа.
- X86Compiler – высокоуровневая обертка над X86Assembler, инкапсулирующая
- Создание функций и работу с аргументами в соответствии с заданными calling conventions, как на стороне определения функции, так и в месте вызова (кстати наиболее простой способ реализовать native-функции).
- Регистровую аллокацию: можно определить переменные (GpVar или XmmVar), место для хранения которых компилятор выберет сам. Сразу оговорюсь, что не искал, и не в курсе насчет того, какой алгоритм аллокации используется. Единственное, что могу сказать – на простых экспериментах имеющиеся регистры использовались вполне разумно.
В своей реализации я использовал именно Assembler, подкупивший меня своей прозрачностью и более тонкой управляемостью.
Самый простой работающий пример использования Asmjit:
#include "asmjit/asmjit.h"
#include <iostream>
int main(int argc, char** argv) {
using namespace std;
using namespace asmjit;
using namespace asmjit::x86;
JitRuntime runtime; // RAII object
X86Assembler assembler(&runtime);
assembler.add(rdi, rsi); // add second argument to first
assembler.mov(rax, rdi); // mov result to return register
assembler.ret();
void * address = assembler.make();
cout << reinterpret_cast<int64_t (*) (int64_t, int64_t)>(address)(2, 2) << endl; // 4
return 0;
}
Я думаю у людей, знакомых с ассемблером, он не должен вызвать много вопросов. Единственное, о чем следует упомянуть – объект runtime, отвечающий за время жизни выделенной памяти. Она будет освобождена после вызова его деструктора (RAII).
Еще примеры использования можно подсмотреть в каталоге с тестами библиотеки или у меня в репозитории.
Отладка
Как ни странно отладка сгенерированного кода не отличается особыми извращениями.
Во-первых, если что-то пошло не так, можно вдумчиво посмотреть логи Asmjit. В логах можно увидеть полученный ассемблерный код и немножко комментариев, откуда он здесь появился.
В случае, если даже это вам не помогло, то в большинстве современных дебаггеров (gdb/VS) есть возможность работы в режиме отладки с дизассемблированием. То есть вы можете поставить брейкпойнт на место вызова сгенерированной функции, и Step Into переведет вас на экран с ассемблерным кодом, где можно почти как обычно пошагово отлаживать.
Важно
- В трех случаях из десяти через полчаса вы найдете ошибку не в компиляторе, а в самой интерпретируемой программе.
- К сожалению, так как Asmjit пока не слишком интенсивно используется, потенциально может содержать разной степени противности баги. Поэтому внимательно смотрите, что в логах именно то, что вы хотели. Хотя мне ничего не попадалось, моему одногруппнику не повезло: тот факт, что был сгенерирован невалидный код не было видно даже в логах, а только в дебаггере.
Оптимизация
После трех дней активного программирования и отладки появился первый совершенно бесхитростный вариант JIT-транслятора, в котором все значения стека и переменных каждый раз бездумно сохранялись в память.
Даже такое решение дало прирост производительности примерно в шесть раз, с 6 FPS, которые получались с интерпретатором до 36 FPS.
Вообще в начале семестра, когда выяснились правила игры, у меня были наполеоновские планы: сделать все совсем по-взрослому – с переводом байткода в SSA и умным алгоритмом регистровой аллокации.
Но в связи с острой нехваткой времени и банальным малодушием все закончилось несколько прозаичней.
Распределение регистров
На всякий случай напомню, что один из наиболее критичных пунктов в плане производительности программы – эффективность использования имеющихся регистров ЦПУ.
Это связано с тем, что основная вычислительная деятельность может производиться только на них, а кроме того чтение/запись даже в память, находящуюся в L1-кэше, работает до двух раз дольше, чем аналогичные операции над регистрами.
Я воспользовался не самым сложным, но зато довольно действенным эвристическим решением: будем хранить в регистрах первые элементы стека виртуальной машины, 7 элементов для слотов общего назначения (строки/целые числа) и 14 для слотов для чисел с плавающей точкой.
Это решение кажется наиболее оправданным, так как наиболее горячими переменными в рамках работы функции действительно является именно низ стека, участвующий во всех вычислениях.
Кроме того, если использовать те же самые регистры, по которым раскладываются аргументы при вызове функций, то это в некоторых случаях позволяет сэкономить время в местах вызова.
В результате реализации этих идей, я получил ускорение на 9 FPS, таким образом достигнув 45 FPS, что не могло меня не радовать.
Peephole-оптимизации
Одним из простых классических подходов при генерации являются так называемые Peephole-оптимизации, идея которых заключается в поиске и замене определенных последовательностей инструкций на другие, более производительные.
Например из-за недостатка выразительности байт-кода mathvm, операторы сравнения вроде (x0 <= x1) приходится описывать как-то так:
LOADIVAR_0
LOADIVAR_1
IF_CMPLE L1
ILOAD_0 // загрузка константы 0 на вершину стека
JA L2 // безусловный переход
L1:
ILOAD_1
L2:
...
Знатоки Instructions set’а x86, скажут, что такой код можно записать гораздо короче и без единого условного прыжка:
mov rdi, %(var0)
mov rsi, %(var1)
cmp rdi, rsi
setle al
movzx rax, al
Подобные конструкции встречаются и в других случаях: оператор отрицания, цикл for. Детектирование и исправление этих паттернов привело к ускорению на 4 FPS до 49 пунктов.
Оптимизация замыканий
Для обеспечания работы с замыканиями в прологе и эпилоге каждой функции я сохранял в специально выделенную область памяти вне стека адрес, где расположены переменные последнего вызова.
Кроме того нужно сохранять и восстанавливать предыдущий base pointer. На всю эту радость уходило до семи лишних инструкций на каждый вызов, в том числе активно работающих с памятью.
На деле же большинство функций не содержит внутри себя замыканий, и этих потерь можно избежать.
Поэтому я провел дополнительный анализ всего полученного байт-кода на предмет наличия замыканий и соответствующие избыточные инструкции были удалены, в результате чего мультик стал рисоваться еще на 3 FPS быстрее.
Inlining
Заключительный пункт истории про микрооптимизации – inlining или по-русски ”встраивание”. Метод, с помощью которого промышленные компиляторы борются с расходами на вызов маленьких функций: код вызываемой функции просто дублируется в месте вызова, без пролога/эпилога и прочих “лишних” инструкций. Правда надо отметить, что в настоящей жизни к решению о встраивании компиляторы подходят очень осторожно – размер получаемого машинного кода все-таки тоже является мерилом качества их работы.
Однако в моем случае, так как оценивается именно время работы, я решил попробовать встраивать все, что встраивается (нерекурсивные вызовы).
И вот здесь как ни странно оказалось легче работать на уровне трансляции AST в байт-код.
Полученный прирост на 2 FPS был уже не таким значительным, как в предыдущих случаях, но суммарные 53-54 FPS (почти девятикратное ускорение) не могут не радовать. Ускорение таких же порядков наблюдалось и на других доступных бенчмарках.
Что интересно, даже в моем простом JIT-трансляторе для получения пиковой производительности требовалось несколько итераций разогрева, хотя я совсем не запускал интерпретатор и сразу компилировал весь код.
Это иллюстрирует высказывания авторитетных людей про то, что warmup в бенчмарках нужен не только для того, чтобы все, что нужно, скомпилировалось, а еще и для устаканивания профиля программы.
Итоги
В результате моя реализация стала самой быстрой, однако связано это не столько с тем, что я самый хитрый, сколько с тем, что никто из соперников не сделал даже самую простую реализацию JIT’а.
Таким образом отсутствие хоть какой-то спортивной интриги немного омрачило победу.
Исходники моей реализации можно посмотреть в репозитории, в каталоге impl.
Заранее извиняюсь за качество кода, но это все-таки игрушечный проект, и поддерживать его дальше я не планирую.
Спасибо за внимание!
Автор: bintree
