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

Меня зовут Максим Кокряшкин, я занимаюсь разработкой языковых рантаймов в Tarantool. Это решение класса middleware, разрабатываемое VK Tech, сочетающее в себе базу данных in-memory и application-сервер. Как раз таки наш application-сервер, который позволяет писать логику и хранимые процедуры, работает на LuaJIT

Сначала про Lua

Lua — это легковесный мультипарадигменный язык программирования, который был изначально создан с прицелом на максимально простое обучение. Это деталь отчетливо заметна даже по количеству ключевых слов, которых в Lua всего 21 (для сравнения: в Python 3.9 их 36).

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

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

Из-за этих преимуществ Lua используется как встроенный интерпретатор во многих больших проектах, например OpenResty, Redis, Roblox ну и, конечно же, Tarantool.

Одна из отличительных особенностей Lua — это таблицы. Таблица — это такой всеобъемлющий контейнер для Lua, реализующийся через ассоциативный массив. Ключом в таблице может быть что угодно, кроме nil, а на значение ограничений нет.

Классов и объектов в Lua нет, но с помощью таблиц вы можете выразить эти сущности. Если вы знакомы с Python, то наверняка слышали про магические методы (они же dunder methods) у классов. К ним относятся методы вида eq, str, getitem и так далее. Переопределяя эти методы, вы можете менять поведение операторов. В Lua есть аналогичный механизм, который реализуется с помощью метатаблиц:

В данном примере при обращении по ключу width, которого в таблице w не существует, произойдет обращение к методу __index и вернется ранее заданное значение по умолчанию.

Теперь про LuaJIT

LuaJIT — это кросс-платформенный интерпретатор с JIT-компилятором, который публично разрабатывается Майком Поллом с 2005 года. Фактически он разрабатывается примерно с конца девяностых. LuaJIT реализует Lua 5.1 с некоторыми примесями 5.2 и своей специфики. Благодаря LuaJIT можно с уверенностью говорить, что Lua — один из наиболее быстрых интерпретируемых языков программирования. 

Из чего состоит LuaJIT? Естественно, как у любого интерпретатора, у него есть фронтенд, состоящий из лексера и парсера, есть runtime — это всё то, что в целом обеспечивает исполнение, но напрямую к нему не относится. Например, garbage collector, система типов, C API и так далее. Разумеется в LuaJIT есть непосредственный интерпретатор и JIT.

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

Runtime

Система типов

В виртуальной машине Lua всё хранится на виртуальном стеке. Все значения лежат в слотах, которые называются TValue, или Tagged Value. TValue — это хранилище, которое использует концепцию NaN tagging.

Если взглянуть на устройство числового типа double, то вы обнаружите, что он состоит из знакового бита, 11 бит экспоненты и 52 бит мантиссы. Стандарт IEEE 754 говорит нам, что NaN-ом будет считаться любое число типа double, у которого в экспоненте все биты установлены в 1, а самый старший бит мантиссы установлен в 1. 

У нас остается еще куча бит в мантиссе, которые не используются, то есть у NaN может быть множество значений. Мы этим воспользуемся: когда нужно хранить число, мы будем хранить его как double, а когда нужно хранить что-то более сложное, мы заполним единицами старшие 13 бит. То, что у нас осталось в верхней половине 64 бит, мы используем как тег, а всё остальное — для значения.

Но возникает проблема: на 32-битных платформах всё бы работало отлично, а на 64-битных платформах нам нужно как-то хранить указатели, которые могут быть куда длиннее, чем 32 бита. Что делать? 

Можно заметить, что тегов нужно не так много, по количеству нужных типов, которое легко помещается в 4-битный тег, что освобождает нам больше пространства под непосредственное значение. Полученных 47 бит уже хватает под любой объект в RAM на 64-битной системе. При этом есть, конечно, проблемы на некоторых новых ARM-процессорах, где адресуются 52 бита, но они решаются уже другими методами.

Стандартная библиотека

Очень часто у функций есть несколько ветвей внутри. Есть «счастливый путь», когда исполнение предельно простое и быстрое, а есть краевые случаи, где всё обрабатывается сложно и медленно.

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

Чтобы улучшить ситуацию, мы напишем «счастливый путь» прямо в цикл интерпретатора на ассемблере, а все «несчастливые» случаи вынесем отдельно и будем туда попадать туда через computed goto, когда что-то идёт не так. Вот так это выглядит для функции tonumber:

«Счастливый путь» здесь — на вход изначально пришло число, конверсия не нужна в принципе. Для всего остального исполнение будет выпадать в fallback.

Сборка мусора

Главной проблемой языков со stop-the-world GC является этот самый stop-the-world. Если целевое приложение должно быть интерактивным (это верно, например, для веб-сервера), то длительная сборка мусора крайне нежелательна. В случае с классическим двухцветным mark & sweep алгоритмом GC мы получаем длительную сборку мусора: пока алгоритм не проверит все объекты на достижимость, мы не можем пойти дальше и исполнить полезный пользовательский код.

Чтобы повысить интерактивность, нам надо научиться более равномерно распределять время работы фазы mark, то есть надо уметь прерывать эту фазу.

LuaJIT использует инкрементальный трехцветный GC, который позволяет делать ровно это. В трехцветном GC у нас появляются «серые» объекты — те, в достижимости которых мы уже убедились, но еще не успели пройти по их собственным ссылкам на другие объекты. То есть серые объекты фактически образуют очередь для просмотра. Это означает, что мы можем прерывать фазу mark для исполнения пользовательского приложения, а затем снова ее возобновлять, продолжая с «серых» объектов.

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

Цикл интерпретатора обычно выглядит примерно вот так:

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

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

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

Интерпретатор в LuaJIT написан на ассемблере. Это позволяет сделать следующее:

Плюсы очевидны:

• Сохраняется фиксированное распределение регистров для всех инструкций.

• Можно держать всё в регистрах для быстрых путей. Спиллинг можно делать только для медленных путей.

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

Ассемблер, на котором написан LuaJIT, — это DynASM.

DynASM — это макроассемблер, который генерирует код на C. Он был создан специально для LuaJIT Майком Поллом. Основное его преимущество заключается в том, что вы можете свободно смешивать макросы ассемблера с кодом на C. Это, в отличие от обычного ассемблера, очень удобно, потому что у вас остаются все возможности ассемблера, но при этом вы можете обращаться к C-структурам без мучений с взятием оффсетов и адресов полей.

Код на DynASM компилируется в обычный машинный код. В результате получается бинарный файл, который содержит в себе весь интерпретатор и работает очень быстро.

JIT

Как работает JIT? Виртуальная машина исполняет какой-то код, и в какой-то момент участок кода становится «горячим». После этого горячий участок компилируется в эффективный машинный код и связывается с виртуальной машиной. Для внешнего наблюдателя всё выглядит так, будто код исполняется в виртуальной машине, хотя на самом деле исполняется эффективная трасса.

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

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

Здесь на помощь приходит концепция трассирующего JIT-компилятора. В LuaJIT используется именно такой подход. Представьте, что у вас есть код с переменной a, которая выполняется и достигает ветвления. Мы спрашиваем, является ли a числом. Допустим, да, и идем в соответствующую ветку. Эти ограничения порождают так называемые гарды. Мы можем эффективно скомпилировать этот путь и проверять, что условия на входные данные соблюдены. Если условия не соблюдены, происходит деоптимизация, и мы возвращаемся в виртуальную машину.

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

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

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

Когда обнаружен горячий участок, код исполняется следующим образом: для каждой инструкции байт-кода записываются соответствующие операции на уровне IR (intermediate representation). Такое исполнение продолжается до тех пор, пока не будет достигнут логический конец, либо до возникновения ошибки.

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

Хотя это и звучит ужасно, на самом деле, если путь действительно «горячий», то в какой-то момент он всё-таки запишется, пусть мы и потеряем некоторую производительность в моменте.

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

local sum = 0

for i = 1, 4 do

sum = sum + i

end

Bytecode:

---- TRACE 1 start

0011  ADDVV    0   0   4

0012  FORL     1 => 0011

IR:

---- TRACE 1 IR

0001    int SLOAD  #3    I

0002    u8  XLOAD  [0x101004521]  V

0003    int BAND   0002  +12

0004 >  int EQ     0003  +0

0005 >  int SLOAD  #2    T

0006 >+ int ADDOV  0005  0001

0007  + int ADD    0001  +1

0008 >  int LE     0007  +4

0009 ------ LOOP ------------

0010    u8  XLOAD  [0x101004521]  V

0011    int BAND   0010  +12

0012 >  int EQ     0011  +0

0013 >+ int ADDOV  0007  0006

0014  + int ADD    0007  +1

0015 >  int LE     0014  +4

0016    int PHI    0007  0014

0017    int PHI    0006  0013

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

• General

  • Control-Flow Specialization

  • Hash Key Specialization

  • Fast Function Inlining

  • Bytecode Patching

• Fold Engine

  • Constant Folding

  • Algebraic Simplifications

  • Strength Reduction

  • Reassociation

• Common Subexpression Elimination

• Array Bounds Check Elimination

  • Scalar Evolution Analysis

• Narrowing

  • Narrowing of Integer Conversions

  • Narrowing of Arithmetic Operators

  • Predictive Narrowing of Induction Variables

• Elimination of Overflow Checks

• Memory Access Optimizations

  • Alias Analysis

  • Escape Analysis

  • Index Reassociation

  • Load Forwarding, Store Forwarding

  • Dead-Store Elimination

  • Read-Modify-Write Simplifications

• Loop Optimizations

  • Dead-Code Elimination

  • Loop-Invariant Hoisting via Synthetic Unrolling

  • PHI Elimination

  • Unstable Loop Unrolling

• FP Value Splitting and Soft-Float Calls

• Allocation Sinking and Store Sinking

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

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

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

На примере ниже видно пример кода на Lua и его упрощенный IR. Снапшот отражен строкой, начинающейся со слова SNAP. В квадратных скобках видно три «слота», последний из которых соответствует переменной x. Эти «слоты» соответствуют слотам виртуального стека. Соответственно, в примере ниже переменная x будет переложена из регистра в третий слот стека виртуальной машины.

Производительность

Благодаря всем этим техникам LuaJIT значительно опережает референсную реализацию Lua по производительности, что отчетливо видно на наборе бенчмарков из The Computer Language Benchmarks Game. Тем не менее до C всё еще далеко, что связано с фундаментальными ограничениями интерпретируемых динамически типизированных языков программирования.

Вступайте в чат сообщества Tarantool и подписывайтесь на наш канал в Telegram.