Spiiin's blog

Устройство виртуальных машин для самых быстрых скриптовых языков — lua-jit и daScript.
Более развёрнутое продолжение беглой заметки daScript - скорость

Lua

По бенчмаркам языков lua находится высоко даже в режиме интерпретации.

Первые стадии трансформации текста скрипта — лексический и синтаксический анализ. Текст разбивается на отдельные лексемы/токены, которые затем собираются парсером во что-то, что можно интерпретировать. Чаще всего это или поток последовательных инструкций (байт код для интерпретатора) в случае с lua, или AST(дерево, которое будет обходить интерпретатор) в случае с daScript.

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

“Традиционный” подход к дизайну языков с байт-кодом — динамическая типизация, управление памятью с помощью подсчёта ссылок/garbage collector, небольшой набор базовых типов (примитивы + строки + массивы + функции/замыкания + таблицы, опционально - итераторы, корутины, исключения). Из таблиц (пары ключ-значения) можно построить объекты и “собрать” классы — некоторые ключи таблицы делаем зарезервированными, вызывая их для создания/удаления объектов, ссылки на родительскую таблицу, перегрузки операторов и т.п.

Возможные оптимизации:

• Так как чаще всего данные группируются в объекты (представленные таблицами) — то очень важна быстрая реализация этих хеш-таблиц, в чём lua традиционна считается хорошей.
• Nan-tagging — распространённая паковка базовых типов языка виртуальной машины в тип double. Возникает отчасти из желания хранить примитивные типы в той же форме, что и сложные — в динамически типизированном языке нужно где-то сохранить в том числе и тип аргумента, чтобы знать, как его интерпретировать, и при этом не хочется иметь оверхед для примитивных типов.

Отчасти из этой оптимизаций возникает ограничение на количество базовых типов языка — с точки зрения скриптового языка два класса будут иметь разные типы, но для интерпретатора виртуальной машины они оба будут представлены типом “таблица”, и отличаться только значением ключа “название класса”. Также любой вызов метода означает поиск его в таблице. Ещё один минус — требование “раскодировать” аргументы из запакованной формы при взаимодействии с нативным кодом, из-за чего замедляется передача управления в хост язык и обратно. Т.е. нельзя оптимизировать код, просто переносом мелких функций в хост-язык — необходимо переписывать сразу большие куски кода.

• Поиск частых паттернов в инструкциях. Optimizing invocation — пример слияния пары инструкций “получение метода класса + вызов метода”. В общем случае, метод может быть получен не для вызова, а для сохранения в переменную, но чаще всего вызывается напрямую, так что две инструкции, идущие подряд, можно “слить” в одну. В lua вроде не применяется, но повсеместно юзается в daScript, примеры приведу дальше. Оптимизация известна под названиями Instruction fusion или Super-instructions.

Tracing JIT

Основная сила lut-jit - just-in-time компиляция. Каждый раз, при вызовах функций и циклов (thermal function/cycle), интерпретатор подсчитывает количество таких вызовов, и таким образом, определяет “горячий” код. Алгоритм подсчёта (NLF region-selection) также умеет обнаруживать вложенные циклы и вызовы.

При достижении предельного количества вызовов, интерпретатор выполняет отмеченный участок кода с “трассированием”, то есть кроме выполнения инструкции дополнительно сохраняет её же в список инструкций — уже на другом байт-код языке (intermediate representation, спек).

После записи всех инструкций из IR генерируется машинный код, и следующий вызов этого участка кода уже приведёт к тому, чтобы будет вызвана нативная версия кода. Подмена способов вызова функции реализована с помощью патчинга оп-кодов байт-кода lua (call gates).

Генерация нативного машинного кода разрешена не на всех платформах/ОС (память для выполнения нативного кода защищена от записи), поэтому недоступна для части платформ. Также нативный код для различных архитектур отличается, поэтому добавление новой платформы может требовать написания отдельного генератора кода.

Список особенностей jit-компилятора lua:

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

Тривиальный пример, с неизвестными типами аргументов:

function foo(t, k)
    return t[k]
end

daScript

daScript серьёзно отличается от “традиционных” скриптовых языков.

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

Типизация немного усложняет изучение языка, но позволяет избавиться от огромного количества ошибок типов. Если рассмотреть синтетический пример на lua, то обнаружить фактические типы аргменутов t и k может быть сложно в цепочке вызовов, а проверить их корректность можно только в рантайме. Представьте, что foo ожидает в качестве t список из строк и выбирает из него первый элемент (допустим, сортированный список допустимых фраз персонажа игры). Список составляется и сортируется динамически. На каком-то этапе в ходе рефактора программист добавляет дополнительную функцию в цепочку вызовов, которая проверяет граничное условие (не то, чтобы это хороший код или пример, но подобную ошибку с подменой списка строкой встречал много раз):

function checkIfGameOver(t, k)
    if life <= 0 then 
        foo("game over!", k) //вместо foo(["game over!"], k)
    else
        foo(t, k)
    end
end

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

Представление в виде AST, а не байт-кода, упрощает генерацию и анализ кода, например — с ним работают макросы, а также упрощается написание тулзов, анализирующих код.

На уровне AST намного удобнее проводить оптимизации, в этот момент интерпретатор иметь достаточно много информации о коде. daScript позволяет изучить код на каждом шаге оптимизации. Простейший пример:

После стадии CONST_FOLDING можно увидеть, что AST “свернулся” до:

После оптимизаций daScript не интерпретирует AST и не генерирует байт-код. Вместо этого генерируется дерево симуляции. На этом этапе также происходит оптимизация — AST ноды “отбрасывают” ненужную для симуляции информацию, например, информацию о типах (она больше не нужна, типы известны и статически проверены на уровне AST), и умеют генерировать более оптимизированные частные случаи (симуляция simulate-ноды из ast-ноды ifThenElse, ветка //good old if - дефолтный вариант, остальные — оптимизированные).

Базовый класс нод simulate-ноды

struct SimNode {
    SimNode ( const LineInfo & at ) : debugInfo(at) {}
    virtual SimNode * copyNode ( Context & context, NodeAllocator * code );
    virtual vec4f eval ( Context & ) = 0;
    virtual SimNode * visit ( SimVisitor & vis );
    virtual char *      evalPtr ( Context & context );
    virtual bool        evalBool ( Context & context );
    virtual float       evalFloat ( Context & context );
    virtual double      evalDouble ( Context & context );
    virtual int32_t     evalInt ( Context & context );
    virtual uint32_t    evalUInt ( Context & context );
    virtual int64_t     evalInt64 ( Context & context );
    virtual uint64_t    evalUInt64 ( Context & context );
    LineInfo debugInfo;
    virtual bool rtti_node_isSourceBase() const { return false;  }
    virtual bool rtti_node_isBlock() const { return false; }
    virtual bool rtti_node_isInstrument() const { return false; }
    virtual bool rtti_node_isInstrumentFunction() const { return false; }
    virtual bool rtti_node_isJit() const { return false; }
  protected:
    virtual ~SimNode() {}
};

Сравнение дерева симуляции и байт-код представления:

• Ноды лежат в памяти плоско в линейном аллокаторе, как и байт-код
• Обход дерева не требует интерпретации. Т.е. 1) не нужно сопоставлять байт-коду функцию, и 2) связь между нодами осуществляется по указателям, а не байт-кодом команд передачи управления/через регистры/стек
• Типы данных хранятся также, как и в нативном коде, нет кодирования/декодирования аргументов, результатов
• Нет ограничения на количество типов нод, когда bind-ится функция, то создаётся кастомная нода, за счёт чего вызов функций быстрый

С таким дизайном возможны оптимизации добавлением частных случаев новых типов нод:

• Упомянутые выше уникальные типы нод для вызова функции
• Специализированные версии нод для отдельных типов для чуть более быстрой математики, конкретных специализаций контейнеров (SimPolicy)
• Из-за того, что можно не экономить на типах нод, можно в полную силу использовать fusion нескольких нод в одну специализированную

Цена большого количества специализированных версий нод — увеличение размера бинарника приложения, поэтому уровень “сплава” нескольких нод в одну регулируется через дефайн DAS_FUSION. 0 - не включать fusion-движок, 1 - “нормальный” уровень слияния, 2 - максимальное количество специализированных нод.

Пример работы fusion-движка:

Если изменить значение optimize=true, можно увидеть разницу в количестве нод:

// неоптимизированная версия, 6 нод
(Return (Add_TT<int> (Ref2Value_TT<int> (GetArgumentRef #0)) (Ref2Value_TT<int> (GetArgumentRef #1))))

// оптимизированная версия, 2 ноды
(Return (AddArgArg_TT<int> #0 #1))

Резюмируя — на скорость в режиме симуляции тут влияют:

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

В сумме это позволяет в режиме интерпретации (без jit, и aot) обогнать самые быстрые интерпретаторы байт-кода с jit-компиляцией.

Опционально ещё:

• возможность с помощью макросов обработать AST и изменить семантику объявлений для более оптимального расположения в памяти
• переопределить для своих типов кастомный simulate для генерации кастомного быстрого кода для их обработки

daJIT

Кроме режима интерпретации, daScript тоже немного умеет jit-титься:
dasXbyak - для x84/x64 (приостановлен, можно допилить при наличии энтузиазма)
dasLLVM - для всего что может llvm (пока на начальной стадии, перспективнее)
jit-компиляция разрешена на PC/Unix/Mac/Web, запрещена на телефонах и консолях (везде, где разрешен запуск только подписанного кода)

А также хорошо AoT транспилироваться в C++-код. Перегонка “руками”:
daScript.exe -aot test.das test.das.cpp
или на уровне cmake сборки, настройки AoT кастомизируется на уровне отдельных модулей, функций и типов.
daScript in imaginery world - немного про прирост скорости от AoT-прекомпиляции. В отличие от jit, этим можно воспользоваться на всех платформах.