JIT-компилятор как учебный проект в Академическом Университете
Около шестнадцати лет назад вышла первая версия Hotspot – реализация JVM, впоследствии ставшая стандартной виртуальной машиной, поставляемой в комплекте JRE от Sun.
Основным отличием этой реализации стал JIT-компилятор, благодаря которому заявления про медленную Джаву во-многих случаях стали совсем несостоятельными.
Сейчас почти все интерпретируемые платформы, такие как CLR, Python, Ruby, Perl, и даже замечательный язык программирования R, обзавелись своими реализациями JIT-трансляторов.
В рамках этой статьи я не планирую проливать свет на малоизвестные детали реализации промышленных JIT-компиляторов, скорее это будет совсем поверхностное ознакомление с азами и рассказ про учебный проект по соответствующей тематике.
Преимущества JIT-компиляции
Чтобы говорить о преимуществах сначала разберемся, с тем, что это такое. Начнем издалека, а именно с определения компилируемого языка.
Компилируемый язык программирования — язык программирования, исходный код которого преобразуется компилятором в машинный код конкретной архитектуры, например x86/ARM. Этот машинный код представляет собой последовательность команд, которая совсем понятна вашему процессору, и может быть исполнена им без посредника.
Интерпретируемые языки программирования отличаются тем, что исходники не преобразовываются в машинный код для непосредственного выполнения на ЦПУ, а исполняются с помощью специальной программы-интерпретатора.
Как промежуточный вариант, многие языки (Java, C#, Python) транслируются в машинно-независимый байт-код,
который все еще не может быть исполнен напрямую на ЦПУ, и чтобы его исполнить все еще необходим интерпретатор.
Почему интерпретация медленней? Ответ на этот вопрос, как ни странно не всем кажется очевидным, хотя он действительно очень простой: интерпретируя каждую команду по отдельности, мы затрачиваем дополнительные ресурсы на перевод семантики этой команды на язык процессора. Кроме того современные процессоры оптимизированы для выполнения последовательных команд (см. Конвейер), а интерпретатор чаще всего представляет собой огромный switch с кучей опций, загоняющий в тупик предсказатель переходов.
Вполне естественным решением всех этих проблем было бы лишь однажды перевести байт-код на язык процессора и передать его ЦПУ для исполнения. Так чаще всего и поступают, называя этот процесс Just-in-time-компиляцией (JIT). Кроме того, именно в течение этой фазы чаще всего проводятся различные оптимизации генерируемого кода.
Теперь перейдем к практике.
Постановка задачи
Курс “Виртуализация и виртуальные машины” в нашем университете читает Николай Иготти, принимавший участие в разработке самых разных классов ВМ: Hotspot, VirtualBox, NativeClient, и не понаслышке знающий детали их реализации. Благодаря чудесам современных технологий, чтобы узнать про это все подробней необязательно даже быть студентом Академического Университета, так как курс опубликован на лекториуме. Хотя нужно отметить, что это конечно немного не то, в силу интерактивности курса и работе с аудиторией на лекциях.
Типичная программа на языке mathvm:
Сложности
Казалось бы, что существенно сложного в том, чтобы просто перевести семантику несложных байт-код инструкций в соответствующие элементы набора инструкций x86?
Asmjit
Самый простой работающий пример использования Asmjit:
Я думаю у людей, знакомых с ассемблером, он не должен вызвать много вопросов. Единственное, о чем следует упомянуть – объект runtime, отвечающий за время жизни выделенной памяти. Она будет освобождена после вызова его деструктора (RAII).
Еще примеры использования можно подсмотреть в каталоге с тестами библиотеки или у меня в репозитории.
Отладка
Оптимизация
После трех дней активного программирования и отладки появился первый совершенно бесхитростный вариант JIT-транслятора, в котором все значения стека и переменных каждый раз бездумно сохранялись в память.
Даже такое решение дало прирост производительности примерно в шесть раз, с 6 FPS, которые получались с интерпретатором до 36 FPS.
Вообще в начале семестра, когда выяснились правила игры, у меня были наполеоновские планы: сделать все совсем по-взрослому – с переводом байткода в SSA и умным алгоритмом регистровой аллокации.
Но в связи с острой нехваткой времени и банальным малодушием все закончилось несколько прозаичней.
Распределение регистров
На всякий случай напомню, что один из наиболее критичных пунктов в плане производительности программы – эффективность использования имеющихся регистров ЦПУ.
Это связано с тем, что основная вычислительная деятельность может производиться только на них, а кроме того чтение/запись даже в память, находящуюся в L1-кэше, работает до двух раз дольше, чем аналогичные операции над регистрами.
Я воспользовался не самым сложным, но зато довольно действенным эвристическим решением: будем хранить в регистрах первые элементы стека виртуальной машины, 7 элементов для слотов общего назначения (строки/целые числа) и 14 для слотов для чисел с плавающей точкой.
Это решение кажется наиболее оправданным, так как наиболее горячими переменными в рамках работы функции действительно является именно низ стека, участвующий во всех вычислениях.
Кроме того, если использовать те же самые регистры, по которым раскладываются аргументы при вызове функций, то это в некоторых случаях позволяет сэкономить время в местах вызова.
В результате реализации этих идей, я получил ускорение на 9 FPS, таким образом достигнув 45 FPS, что не могло меня не радовать.
Peephole-оптимизации
Одним из простых классических подходов при генерации являются так называемые Peephole-оптимизации, идея которых заключается в поиске и замене определенных последовательностей инструкций на другие, более производительные.
Например из-за недостатка выразительности байт-кода mathvm, операторы сравнения вроде (x0
Java HotSpot JIT компилятор — устройство, мониторинг и настройка (часть 1)
AOT и JIT компиляторы
Процессоры могут исполнять только ограниченный набор инструкций — машинный код. Для исполнения программы процессором, она должна быть представлена в виде машинного кода.
Существуют компилируемые языки программирования, такие как C и C++. Программы, написанные на этих языках, распространяются в виде машинного кода. После того, как программа написана, специальный процесс — Ahead-of-Time (AOT) компилятор, обычно называемый просто компилятором, транслирует исходный код в машинный. Машинный код предназначен для выполнения на определенной модели процессора. Процессоры с общей архитектурой могут выполнять один и тот же код. Более поздние модели процессора как правило поддерживают инструкции предыдущих моделей, но не наоборот. Например, машинный код, использующий AVX инструкции процессоров Intel Sandy Bridge не может выполняться на более старых процессорах Intel. Существуют различные способы решения этой проблемы, например, вынесение критичных частей программы в библиотеку, имеющую версии под основные модели процессора. Но часто программы просто компилируются для относительно старых моделей процессоров и не используют преимущества новых наборов инструкций.
В противоположность компилируемым языкам программирования существуют интерпретируемые языки, такие как Perl и PHP. Один и тот же исходный код при таком подходе может быть запущен на любой платформе, для которой существует интерпретатор. Минусом этого подхода является то, что интерпретируемый код работает медленнее, чем машинный код, делающий тоже самое.
Язык Java предлагает другой подход, нечто среднее между компилируемыми и интерпретируемыми языками. Приложения на языке Java компилируются в промежуточный низкоуровневый код — байт-код (bytecode).
Название байт-код было выбрано потому, что для кодирования каждой операции используется ровно один байт. В Java 10 существует около 200 операций.
Байт-код затем исполняется JVM также как и программа на интерпретируемом языке. Но поскольку байт-код имеет строго определенный формат, JVM может компилировать его в машинный код прямо во время выполнения. Естественно, старые версии JVM не смогут сгенерировать машинный код, использующий новые наборы инструкций процессоров вышедших после них. С другой стороны, для того, чтобы ускорить Java-программу, ее даже не надо перекомпилировать. Достаточно запустить ее на более новой JVM.
HotSpot JIT компилятор
Единица скомпилированного кода называется nmethod (сокращение от native method).
Многоуровневая компиляция (tiered compilation)
На самом деле в HotSpot JVM существует не один, а два компилятора: C1 и C2. Другие их названия клиентский (client) и серверный (server). Исторически C1 использовался в GUI приложениях, а C2 в серверных. Отличаются компиляторы тем, как быстро они начинают компилировать код. C1 начинает компилировать код быстрее, в то время как C2 может генерировать более оптимизированный код.
Существует 5 уровней компиляции:
| Последовательность | Описание |
|---|---|
| 0-3-4 | Интерпретатор, уровень 3, уровень 4. Наиболее частый случай. |
| 0-2-3-4 | Случай, когда очередь уровня 4 (C2) переполнена. Код быстро компилируется на уровне 2. Как только профилирование этого кода завершится, он будет скомпилирован на уровне 3 и, наконец, на уровне 4. |
| 0-2-4 | Случай, когда очередь уровня 3 переполнена. Код может быть готов к компилированию на уровне 4 все еще ожидая своей очереди на уровне 3. Тогда он быстро компилируется на уровне 2 и затем на уровне 4. |
| 0-3-1 | Случай простых методов. Код сначала компилируется на уровне 3, где становится понятно, что метод очень простой и уровень 4 не сможет скомпилировать его оптимальней. Код компилируется на уровне 1. |
| 0-4 | Многоуровневая компиляция выключена. |
Code cache
Машинный код, скомпилированный JIT компилятором, хранится в области памяти называемой code cache. В ней также хранится машинный код самой виртуальной машины, например, код интерпретатора. Размер этой области памяти ограничен, и когда она заполняется, компиляция прекращается. В этом случае часть «горячих» методов так и продолжит выполняться интерпретатором. В случае переполнения JVM выводит следующее сообщение:
Другой способ узнать о переполнении этой области памяти — включить логирование работы компилятора (как это сделать обсуждается ниже).
Code cache настраивается также как и другие области памяти в JVM. Первоначальный размер задаётся параметром -XX:InitialCodeCacheSize. Максимальный размер задается параметром -XX:ReservedCodeCacheSize. По умолчанию начальный размер равен 2496 KB. Максимальный размер равен 48 MB при выключенной многоуровневой компиляции и 240 MB при включенной.
Начиная с Java 9 code cache разделен на 3 сегмента (суммарный размер по-прежнему ограничен пределами, описанными выше):
Мониторинг работы компилятора
Включить логирование процесса компиляции можно флагом -XX:+PrintCompilation (по умолчанию он выключен). При установке этого флага JVM будет выводить в стандартный поток вывода (STDOUT) сообщение каждый раз после компиляции метода или цикла. Большинство сообщений имеют следующий формат: timestamp compilation_id attributes tiered_level method_name size deopt.
Поле timestamp — это время со старта JVM.
Поле compilation_id — это внутренний ID задачи. Обычно он последовательно увеличивается в каждом сообщении, но иногда порядок может нарушаться. Это может произойти в случае, если существует несколько потоков компиляции работающих параллельно.
Поле attributes — это набор из пяти символов, несущих дополнительную информацию о скомпилированном коде. Если какой-то из атрибутов не применим, вместо него выводится пробел. Существуют следующие атрибуты:
Атрибут «b» означает, что компиляция произошла не в фоне, и не должен встречаться в современных версиях JVM.
Атрибут «n» означает, что скомпилированный метод является оберткой нативного метода.
Поле tiered_level содержит номер уровня, на котором был скомпилирован код или может быть пустым, если многоуровневая компиляция выключена.
Поле method_name содержит название скомпилированного метода или название метода, содержащего скомпилированный цикл.
Поле size содержит размер скомпилированного байт-кода, не размер полученного машинного кода. Размер указан в байтах.
Поле deopt появляется не в каждом сообщении, оно содержит название проведенной деоптимизации и может содержать такие сообщения как «made not entrant» и «made zombie».
Иногда в логе могут появиться записи вида: timestamp compile_id COMPILE SKIPPED: reason. Они означают, что при компиляции метода что-то пошло не так. Есть случаи, когда это ожидаемо:
Параметр -compiler выводит сводную информацию о работе компилятора (5003 — это ID процесса):
Эта команда также выводит количество методов, компиляция которых завершилась ошибкой и название последнего такого метода.
Планы на вторую часть
В следующей части мы рассмотрим пороговые значения счетчиков при которых JVM запускает компиляцию и как можно их поменять. Мы также рассмотрим как JVM выбирает количество потоков компилятора, как можно его поменять и в каких случаях стоит это делать. И наконец, кратко рассмотрим некоторые из оптимизаций выполняемых JIT компилятором.
Как реализованы JIT-компиляторы
В этой статье мы поговорим о подробностях реализации и работе разных JIT-компиляторов, а также о стратегиях оптимизации. Обсуждать будем достаточно подробно, однако многие важные концепции опустим. То есть в этой статье не будет достаточной информации, чтобы прийти к обоснованным заключениям при любых сравнениях реализаций и языков.
Чтобы получить базовое представление о JIT-компиляторах, почитайте эту статью.
Я часто буду описывать поведение оптимизации и утверждать, что она, вероятно, есть и в каком-нибудь другом компиляторе. Хотя я не всегда проверяю, есть ли эта оптимизация в другом JIT (иногда всё неоднозначно), но если знаю точно, то укажу на это. Я также приведу примеры кода, чтобы показать, где может быть применена оптимизация, но это не точно, ведь приоритет может быть отдан другой оптимизации. Могут быть и какие-то общие упрощения, но не больше, чем в большинстве подобных постов.
Основные вехи
(Мета)трассировка
LuaJIT использует так называемую трассировку (tracing). Pypy выполняет метатрассировку, то есть использует систему для генерирования интерпретаторов трассировки и JIT. Pypy и LuaJIT — это не образцовые реализации Python и Lua, а самостоятельные проекты. Я бы охарактеризовал LuaJIT как шокирующе быструю, и она сама себя описывает как одну из самых быстрых динамических языковых реализаций — и я этому безоговорочно верю.
Чтобы понять, когда начинать трассировку, цикл интерпретации ищет «горячие» циклы (концепция «горячего» кода универсальна для всех JIT-компиляторов!). Затем компилятор «трассирует» цикл, записывая исполняемые операции для компилирования хорошо оптимизированного машинного кода. В LuaJIT компиляция выполняется на основе трасс с промежуточным представлением, похожим на инструкции, которое уникально для LuaJIT.
Как трассировка реализована в Pypy
Pypy начинает трассировать функцию после 1619 исполнений и компилирует ещё после 1039 исполнений, то есть нужно около 3000 исполнений функции, чтобы она начала работать быстрее. Эти значения тщательно подбирались командой Pypy, и вообще в мире компиляторов многие константы подбираются продуманно.
Динамические языки затрудняют оптимизацию. Нижеприведённый код может быть статически удалён более строгим языком, потому что False всегда будет ложным. Однако в Python 2 этого нельзя гарантировать до момента исполнения.
Для любой разумной программы это условие всегда будет ложным. К сожалению, значение False может быть переопределено, и выражение будет в цикле, его могут переопределить где-то в другом месте. Поэтому Pypy может создать «защитника». Если защитник не справляется, JIT возвращается к циклу интерпретирования. Затем Pypy с помощью ещё одной константы (200), которая называется trace eagerness, решает, нужно ли компилировать остаток нового пути до конца цикла. Этот подпуть называется мостом (bridge).
Кроме того, Pypy предоставляет эти константы как аргументы, которые можно настраивать в ходе исполнения наряду с конфигурацией развёртки (unrolling), то есть расширения цикла, и инлайнинга! И вдобавок он предоставляет хуки, которые мы можем увидеть после завершения компилирования.
Погоди, ты же говорил про метатрассировку!
Идею метатрассировки можно описать как «напиши интерпретатор, и получи компилятор бесплатно!», или «преврати свой интерпретатор в JIT-компилятор!». Писать компилятор трудно, и если можно получить его бесплатно, то идея крутая. Pypy «содержит» интерпретатор и компилятор, но в нём нет явной реализации традиционного компилятора.
В Pypy есть инструмент RPython (созданный для Pypy). Это фреймворк для написания интерпретаторов. Его язык относится к разновидности Python и обеспечивает статическую типизацию. На этом языке и нужно писать интерпретатор. Язык не предназначен для программирования на типизированном Python, потому что не содержит стандартных библиотек или пакетов. Любая программа на RPython является корректной Python-программой. Код на RPython транспилируется в С, а затем компилируется. Таким образом, метакомпилятор на этом языке существует в виде скомпилированной программы на С.
Приставка «мета» в слове метатрассировка означает, что трассировка выполняется при исполнении интерпретатора, а не программы. Он ведёт себя более-менее как любой другой интерпретатор, но может отслеживать свои операции и предназначен для оптимизации трасс с помощью обновления своего пути прохождения. С дальнейшей трассировкой путь интерпретатора становится более оптимизированным. Хорошо оптимизированный интерпретатор идёт по специфическому пути. А используемый в этом пути машинный код, полученный при компилировании RPython, может использоваться в окончательной компиляции.
Короче, «компилятор» в Pypy компилирует ваш интерпретатор, поэтому Pypy иногда называют метакомпилятором. Он компилирует не столько программу, которую вы исполняете, сколько путь оптимизированного интерпретатора.
Если я запущу этот горячий цикл:
Трассы могут выглядеть так:
Но компилятор — не какой особенный отдельный модуль, он встроен в интерпретатор. Поэтому цикл интерпретации будет выглядеть так:
Введение в JVM
Я четыре месяца писал на языке TruffleRuby на основе Graal, и влюбился в него.
Hotspot (названа так потому, что ищет горячие точки) — это виртуальная машина, поставляемая со стандартными инсталляциями Java. В ней содержится несколько компиляторов для реализации многоуровневого компилирования. Кодовая база Hotspot в 250 000 строк открыта, в ней есть три сборщика мусора. Виртуалка отлично справляется с JIT-компиляцией, в некоторых бенчмарках она работает не хуже C++ impls (по этому поводу столько сра споров, погуглите). Хотя Hotspot не делает трассировку, она использует аналогичный подход: интерпретирует, профилирует, а затем компилирует. У этого подхода нет своего названия, он ближе всего к JIT на основе методов (оптимизация по методам), или к многоуровневому JIT.
Используемые в Hotspot стратегии вдохновили многих авторов последующих JIT-компиляторов, структур языковых виртуальных машин, и особенно Javascript-движков. Также Hotspot породила волну таких JVM-языков, как Scala, Kotlin, JRuby и Jython. JRuby и Jython — забавные реализации Ruby и Python, которые компилируют исходный код в JVM-байткод, который потом исполняет Hotspot. Все эти проекты относительно успешно ускоряют языки Python и Ruby (Ruby больше, чем Python) без реализации всего инструментария, как в случае с Pypy. Ещё Hotspot уникальна тем, что она является JIT для менее динамических языков (хотя технически она представляет собой JIT для JVM-байткода, а не для Java).
GraalVM — это JavaVM с частью кода на Java. Она может исполнять любой JVM-язык (Java, Scala, Kotlin и т.д.). На также поддерживает Native Image, чтобы работать с AOT-компилированным кодом через Substrate VM. Значительная доля Scala-сервисов Twitter работает на Graal, что говорит о качестве виртуальной машины, и кое в чём она лучше JVM, хотя и написана на Java.
И это ещё не всё! GraalVM также предоставляет Truffle: фреймворк для реализации языков с помощью создания AST-интерпретаторов (Abstract Syntax Tree). В Truffle нет явного шага, когда создается JVM-байткод, как в обычном языке JVM. Cкорее, Truffle просто воспользуется интерпретатором и будет общаться с Graal для создания машинного кода непосредственно с профилированием и так называемой частичной оценкой. Рассмотрение частичной оценки выходит за рамки статьи, если вкратце: этот метод исповедует философию метатрассировки «напиши интерпретатор, и получи компилятор бесплатно!», но подходит к ней иначе.
TruffleJS — Truffle-реализация Javascript, которая опережает движок V8 по ряду показателей, что действительно впечатляет, потому что V8 разрабатывался на много лет дольше, Google вложила в него кучу денег и сил, над ним работали офигенные специалисты. TruffleJS не «лучше» V8 (или любого другого JS-движка) по большинству критериев, но это знак надежды для Graal.
Неожиданно отличные стратегии JIT-компилирования
Интерпретирование C
По ряду причин поддерживать C-расширения трудно. Самая очевидная причина в том, что API разработан с учётом особенностей внутренней реализации. Более того, поддерживать С-расширения легче, когда интерпретатор написан на С, так что JRuby не может поддерживать С-расширения, но у него есть API для Java-расширений. В Pypy недавно появилась бета-версия поддержки С-расширений, хотя в её работоспособности я не уверен в связи с законом Хайрама. LuaJIT поддерживает С-расширения, в том числе и дополнительные фичи в своих С-расширениях (LuaJIT — просто офигенная штука!)
Graal решает эту проблему с помощью Sulong, движка, который на GraalVM исполняет LLVM-байткод, преобразуя его в язык Truffle. LLVM — это набор инструментов, и нам достаточно знать, что С можно скомпилировать в LLVM-байткод (у Julia тоже есть LLVM-бэкенд!). Это странно, но решение заключается в том, чтобы взять хороший компилируемые язык с более чем сорокалетней историей, и интерпретировать его! Конечно, он работает совсем не так быстро, как правильно скомпилированный С, но зато мы получаем несколько преимуществ.
LLVM-байткод уже довольно низкоуровневый, то есть применять JIT к этому промежуточному представлению не так неэффективно, как к С. Часть расходов нам возмещается тем, что байткод можно оптимизировать вместе с остальной частью Ruby-программы, а скомпилированную С-программу мы оптимизировать не сможем. Все эти удаления фрагментов памяти, инлайнинги, удаления мёртвых фрагментов кода и прочее можно применять к коду на С и Ruby, вместо того, чтобы вызывать бинарник на С из Ruby-кода. По некоторым параметрам С-расширения TruffleRuby работают быстрее С-расширений CRuby.
Чтобы эта система работала, вам следует знать, что Truffle является полностью независимым от языка, и накладные расходы на переключение между С, Java или любым другим языком внутри Graal будут минимальны.
Способность Graal работать с Sulong является частью их полиглот-возможностей, что обеспечивает высокую взаимозаменяемость языков. Это не только хорошо для компилятора, но ещё и доказывает возможность легко использовать несколько языков в одном «приложении».
Вернёмся к интерпретируемому коду, он быстрее
Мы знаем, что JIT содержат в себе интерпретатор и компилятор, и что для ускорения работы они переходят от интерпретатора к компилятору. Pypy создаёт мостики для обратного пути, хотя с точки зрения Graal и Hotspot это деоптимизация. Мы говорим не о совершенно разных понятиях, но под деоптимизацией понимается возврат к интерпретатору в качестве сознательной оптимизации, а не решение неизбежностей динамического языка. Hotspot и Graal активно используют деоптимизацию, особенно Graal, потому что у разработчиков есть жёсткий контроль над компиляцией, и им нужно ещё больше контроля над компилированием ради оптимизаций (по сравнению, скажем, с Pypy). Также деоптимизация используется в JS-движках, о чём я буду много рассказывать, поскольку от неё зависит работа JavaScript в Chrome и Node.js.
Чтобы быстро применить деоптимизацию, важно убедиться в максимально быстром переключении между компилятором и интерпретатором. При самой наивной реализации интерпретатор придётся «догонять» компилятор, чтобы выполнить деоптимизацию. Дополнительные сложности связаны с деоптимизацией асинхронных потоков. Graal создаёт набор фреймов и сопоставляет его со сгенерированным кодом, чтобы вернуться к интерпретатору. С помощью безопасных состояний (safepoints) можно сделать так, что Java-поток встанет на паузу и скажет: «Привет, сборщик мусора, мне нужно остановиться?», так что обработка потоков не требует больших накладных расходов. Получилось довольно грубо, но работает достаточно быстро, чтобы деоптимизация оказалась хорошей стратегией.
Аналогично примеру с мостиками в Pypy, деоптимизировать можно и партизанский патчинг (monkey patching) функций. Получается элегантнее, поскольку мы добавляем деоптимизирующий код не тогда, когда защитник терпит неудачу, а когда применяется партизанский патчинг.
Даже не посмотрев на скомпилированные инструкции, можно увидеть, как как эта деоптимизация уменьшает объём кода.
В TruffleRuby деоптимизируется только первый прогон конкретной операции, так что мы не тратим на это ресурсы при каждом переполнении операции.
WET-код — быстрый код. Инлайнинг и OSR
Ответ, друг мой, кроется в замещении в стеке (on-stack replacement, OSR). Инлайнинг — это мощная оптимизация компилятора (не только JIT), при которой функции перестают быть функциями, а содержимое передаётся в места вызова. JIT-компиляторы для увеличения скорости могут инлайнить с помощью изменения кода в ходе исполнения (компилируемые языки могут инлайнить только статически).
Инлайнинг невероятно эффективен! Я запустил вышеприведённый код с парой дополнительных нулей, и при отключённом инлайнинге он работал вчетверо медленнее.
Хотя эта статья посвящена JIT, инлайнинг эффективен и в компилируемых языках. Все LLVM-языки активно применяют инлайнинг, потому что и LLVM тоже будет это делать, хотя Julia инлайнит и без LLVM, это в её природе. JIT могут инлайнить с помощью эвристик, получаемых в ходе исполнения, и способны переключаться между режимами без инлайнинга и с инлайнингом посредством OSR.
Заметка о JIT и LLVM
LLVM предоставляет кучу инструментов, связанных с компилированием. Julia работает с LLVM (обратите внимание, что это большой инструментарий, и каждый язык использует его по-разному), также, как и Rust, Swift и Crystal. Достаточно сказать, что это большой и замечательный проект, который также поддерживает JIT, хотя в LLVM нет значимых встроенных динамических JIT. На четвёртом уровне компилирования JavaScriptCore какое-то время использовался LLVM-бэкенд, но его заменили меньше двух лет назад. С тех пор этот инструментарий не слишком хорошо подходит для динамических JIT, в основном потому, что он не предназначен для работы в условиях динамичности. В Pypy его пытались применить 5-6 раз, но остановились на JSC. При использовании LLVM возможности allocation sinking и перемещения кода (code motion) были ограничены. Также невозможно было использовать мощные JIT-возможности вроде range-inferencing (это как приведение типов, но с известным диапазоном значения). Но куда важнее, что с LLVM на компилирование тратится очень много ресурсов.
А если вместо промежуточного представления на основе инструкций у нас будет большой граф, который модифицирует себя?
Мы поговорили об LLVM-байткоде и о Python/Ruby/Java-байткоде в качестве промежуточного представления. Все они выглядят как некий язык в виде инструкций. В Hotspot, Graal и V8 применяется промежуточное представление «Sea of Nodes» (появилось в Hotspot), которое является более низкоуровневым AST. Это эффективное представление, потому что значительная часть профилирования основана на представлении об определённом пути, который редко используется (или пересекается в случае какого-то шаблона). Обратите внимание, что эти AST компиляторов отличаются от AST парсеров.
Обычно я придерживаюсь позиции «попробуйте сделать дома!», но рассматривать графы довольно трудно, хотя и очень интересно, а зачастую и крайне полезно для понимания работы компилятора. Я, например, не могу прочитать все графики не только из-за нехватки знаний, но и из-за пределов вычислительных возможностей моего мозга (параметры компилятора могут помочь избавиться от поведения, которое меня не интересует).
Ладно, давайте взглянем на JavaScript AST!
Так выглядит AST (я убрал некоторые маловажные строки):
Парсить такое сложно, но это похоже на AST парсера (верно не для всех программ). А следующее AST сгенерировано с помощью Acorn.js
А так выглядит AST той же программы, полученное с помощью Graal!
Выглядит куда проще. Красным обозначен поток управления, синим — поток данных, стрелками — направления. Обратите внимание, что хотя этот граф проще, чем AST из V8, это не означает, что Graal лучше упростил программу. Просто он сгенерирован на основе Java, который куда менее динамичен. Тот же граф Graal, сгенерированный из Ruby, будет ближе к первой версии.
Забавно, что AST в Graal будут меняться в зависимости от исполнения кода. Этот граф сгенерирован с отключённым OSR и инлайнигом, при многократном вызове функции со случайными параметрами, чтобы она не была оптимизирована. И дамп снабдит вас целой пачкой графов! В Graal для оптимизации программ применяется специализированное AST (V8 делает аналогичные оптимизации, но не на уровне AST). Когда сохраняешь в Graal графы, то получаешь больше десяти схем с разными уровнями оптимизации. При перезаписи нод они заменяют себя (специализируют) другими нодами.
Вышеприведённый граф — прекрасный пример специализации при динамически типизируемом языке (картинка взята из «One VM to Rule Them All», 2013). Причина существования этого процесса тесно связана с тем, как работает частичная оценка — всё дело в специализации.
Ура JIT скомпилировал код! Давай скомпилируем снова! И снова!
Выше я упоминал про «многоуровневость», давайте уже об этом поговорим. Идея простая: если мы ещё не готовы создавать полностью оптимизированный код, но интерпретация до сих пор обходится дорого, мы можем выполнить предварительную компиляцию, а затем финальную, когда будем готовы сгенерировать более оптимизированный код.
Hotspot — это многоуровневый JIT с двумя компиляторами: C1 и C2. C1 выполняет быструю компиляцию и запускает код, затем проводит полное профилирование, чтобы получить скомпилированный с помощью С2 код. Это может помочь решить многие проблемы с прогревом. Не оптимизированный скомпилированный код всё-равно быстрее интерпретации. Кроме того, С1 и С2 компилируют не весь код. Если функция выглядит достаточно просто, с большой вероятностью С2 нам не поможет и даже не будет запускаться (ещё и сэкономим время на профилировании!). Если С1 занят компилированием, тогда профилирование может продолжиться, работа С1 будет прервана и запущено компилирование с помощью С2.
В JavaScript Core уровней ещё больше! П сути, там три JIT. Интерпретатор JSC выполняет лёгкое профилирование, затем переходит к Baseline JIT, затем к DFG (Data Flow Graph) JIT, и наконец к FTL (Faster than Light) JIT. С таким количеством уровней смысл деоптимизации больше не ограничивается переходом от компилятора к интерпретатору, деоптимизация может выполняться начиная с DFG и заканчивая Baseline JIT (это не так в случае Hotspot C2->C1). Все деоптимизации и переходы на следующий уровень выполняются с помощью OSR (замещения в стеке).
Baseline JIT подключается примерно после 100 исполнений, а DFG JIT — примерно после 1000 (с некоторыми исключениями). Это означает, что JIT получает скомпилированный код гораздо быстрее, чем тот же Pypy (у которого это занимает около 3000 исполнений). Многоуровневость позволяет JIT пытаться соотнести длительность исполнения кода с длительностью его оптимизации. Есть куча уловок, какой вид оптимизации (инлайнинг, приведение типов и т.д.) исполнять на каждом из уровней, и поэтому такая стратегия является оптимальной.
