Что такое jit компиляторы

JIT для начинающих

Предпосылка

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

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

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

С чего мы начнём

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

Их делает особенными то, что они работают не до запуска кода (как, например, gcc, clang и другие), а «Just-In-Time» (то есть прямо перед выполнением скомпилированного кода).

Чтобы начать разработку собственного JIT-компилятора, нам нужно выбрать язык ввода для него. Учитывая Top Github Languages for 2013 ( статья написана в 2013 году, — прим. пер.), JavaScript кажется хорошим кандидатом для реализации его ограниченного подмножества с упрощенной семантикой. Более того, мы будем реализовывать JIT-компилятор в самом JavaScript. Вы можете назвать его META-META!

Наш компилятор будет принимать исходный код JavaScript в качестве входных данных и производить (и сразу же запускать) машинный код для очень популярной платформы X64. Хотя для людей работать с текстовым представлением довольно удобно, разработчики компилятора обычно стремятся создавать несколько промежуточных представлений (Intermediate Representations или сокращённо IR) до создания окончательного машинного кода.

Поскольку мы пишем упрощенный компилятор, для нас достаточно одного IR, и для этого я выбрал aбстрактное синтаксическое дерево (AST).

Например, этот код: obj.method(42) будет производить следующий AST (используя esprima.parse(«. «) ):

Машинный код

Подведем итог: у нас есть исходный код JavaScript ( сделано), его AST ( сделано), и мы хотим получить машинный код для него.

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

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

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

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

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

Генерация кода

Полная реализация JavaScript — довольно сложная задача, поэтому на данный момент мы реализуем только упрощенный арифметический движок (который должен быть таким же забавным, как добраться до полной реализации позже!).

Самый лучший и самый простой способ сделать это: обойти AST с помощью поиска в глубину, создавая машинный код для каждого узла. Вы могли бы задаться вопросом, как вы можете генерировать машинный код в таком ограниченном в прямой работе с памятью языке, как JavaScript. Вот где я собираюсь познакомить вас с jit.js.

Это модуль для node.js (фактически, дополнение на C++), способный генерировать и выполнять машинный код, используя сходный с ассемблером синтаксис:

Давайте напишем это

Мы будем поддерживать:

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

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

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

Источник

Как работать с JIT

В некоторых внутренних системах для быстрого поиска по большому битовому массиву мы в Badoo используем JIT. Это очень интересная и не самая известная тема. И, чтобы исправить такую досадную ситуацию, я перевел полезную статью Элая Бендерски о том, что такое JIT и как его использовать.

Раньше я уже публиковал вводную статью по libjit для программистов, которые уже знакомы с JIT. Хотя бы немного. В том посте я совсем коротко описал JIT, а в этом сделаю полный обзор JIT и дополню его примерами, код в которых не требует никаких дополнительных библиотек.

Определение JIT

JIT – это акроним от “Just In Time” или, если переводить на русский, “на лету”. Это нам ни о чем не говорит и звучит так, будто к программированию не имеет никакого отношения. Мне кажется, это описание JIT больше всего похоже на правду:

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

Но откуда произошло это название? К счастью, Джон Айкок из университета Калгари написал очень интересную статью под названием “Краткая история JIT”, в которой рассматривает JIT-техники с исторической точки зрения. Судя по статье, первое упоминание кодогенерации и исполнения кода во время работы программы появилось в 1960 году в статье про LISP, написанной McCarthy. В более поздних работах (например, статья Томсона от 1968 года про регулярные выражения) этот подход совсем очевиден (регулярные выражения компилируются в машинный код и исполняются на лету).

Сам же термин JIT впервые появился в книгах по Java Джеймса Гослинга. Айкок говорит, что Гослинг перенял этот термин из области промышленного производства и начал его использовать в ранних 90-х. Если вам интересны подробности, то прочитайте статью Айкока. А теперь давайте посмотрим, как все описанное выше работает на практике.

JIT: сгенерируйте машинный код и запустите его

Мне кажется, что JIT проще понять, если сразу разделить его на две фазы:

Первая фаза – это 99% всей сложности JIT. Но в то же время это самая банальная часть процесса: это именно то, что делает обычный компилятор. Широко известные компиляторы, такие как gcc и clang/llvm, транслируют исходники из C/C++ в машинный код. Дальше машинный код обычно сохраняется в файл, но нет смысла не оставлять его в памяти (на самом деле и в gcc, и в clang/llvm есть готовые возможности для сохранения кода в памяти для использования его в JIT). Но в этой статье я хотел бы сфокусироваться на второй фазе.

Выполнение сгенерированного кода

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

Я надеюсь, всем понятно, что машинный код – это просто данные, набор байтов. Как вот это, например:

Для кого-то эти три байта – просто три байта, а для кого-то – бинарное представление валидного x86-64 кода:

Поместить этот машинный код в память очень легко. Но как сделать его исполняемым и, собственно, исполнить?

Посмотрим на код

Дальше в этой статье будут примеры кода для POSIX-совместимой UNIX операционной системы (а именно Linux). На других ОС (таких как Windows) код будет отличаться в деталях, но не в подходе. У всех современных ОС есть удобные API для того, чтобы сделать то же самое.

Без лишних предисловий посмотрим, как динамически создать функцию в памяти и выполнить ее. Эта функция специально сделана очень простой. В C она выглядит так:

Вот первая попытка (полный исходник вместе с Makefile доступен в репозитории):

Три основных этапа, которые выполняет этот код:

Прошу заметить, что третий этап возможен только тогда, когда кусок памяти с машинным кодом имеет права на исполнение. Без нужных прав вызов функции привел бы к ошибке ОС (скорее всего, ошибке сегментирования). Это произойдет, если, например, мы выделим m обычным вызовом malloc, который выделяет RW память, но не X.

Отвлечемся на минутку: heap, malloc и mmap

Так что называть память, полученную от mmap “памятью из кучи”, не ошибка, по моему мнению, и я собираюсь и дальше использовать это название.

Заботимся о безопасности

У кода выше есть серьезная уязвимость. Причина в блоке RWX-памяти, который он выделяет – рай для эксплоитов. Давайте будем чуть более ответственными. Вот немного измененный код:

Что насчет malloc?

Подводя итоги

Эта статья начиналась с общего обзора JIT, того, что мы вообще подразумеваем, когда говорим “JIT”, и закончилась примерами кода, который демонстрирует, как динамически выполнять кусок машинного кода из памяти. Техники, представленные в статье – это примерно то, как делается JIT в настоящих JIT-системах (LLVM или libjit). Остается всего лишь “простая” часть генерации машинного кода из какого-либо другого представления.

LLVM содержит в себе полноценный компилятор, так что он может транслировать C и C++-код (через LLVM IR) в машинный код на лету и исполнять его. Libjit работает на гораздо более низком уровне: он может служить бэкендом для компилятора. Моя вводная статья по libjit демонстрирует, как генерировать и выполнять нетривиальный код с помощью этой библиотеки. Но JIT – это гораздо более общий концепт. Создавать код на лету можно для структур данных, регулярных выражений и даже для доступа к C из виртуальных машин различных языков. Я покопался в архивах своего блога и нашел упоминание о JIT в статье восьмилетней давности. Она о Perl-коде, который генерирует другой Perl-код на лету (из XML-файла с описанием), но идея та же самая.

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

Источник

Как реализованы 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 пытаться соотнести длительность исполнения кода с длительностью его оптимизации. Есть куча уловок, какой вид оптимизации (инлайнинг, приведение типов и т.д.) исполнять на каждом из уровней, и поэтому такая стратегия является оптимальной.

Источник