Внутреннее устройство llst, часть 3. Магия JIT, или как ускорить виртуальную машину в 50 раз

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

Ранее мы познакомились с языком Smalltalk, а точнее с его микро реализацией Little Smalltalk. Разобрались с синтаксисом языка, форматом представления объектов в памяти и набором основных инструкций. Теперь мы вплотную подошли к вопросам взаимодействия Smalltalk и LLVM (ради этого и затевалась вся серия статей).

Сейчас у нас есть вся необходимая база знаний для того чтобы понять, что именно делается в нашем JIT компиляторе. В этой статье мы узнаем, как байт-коды Smalltalk преобразуются в IR код LLVM, как происходит компиляция и выполнение кода, и почему это работает быстрее, чем программная интерпретация. Самые нетерпеливые могут посмотреть шеллкасты (раз и два), с циферками и бегущими строчками (не забывайте про возможность скроллинга).

Введение

Как ТРИЗ, так и банальные соображения здравого смысла нам подсказывают, что:

• Быстрее всего можно сделать что-то доказав, что этого делать не нужно;
• Вместо того, чтобы делать что-то быстро, можно не пороть горячку, а попытаться сделать это заранее;
• Не надо делать дважды одну и ту же работу (особенно, если ее можно не делать вовсе).

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

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

Отличия виртуальной машины от реального процессора

Виртуальная машина Smalltalk является стек-ориентированной:

1. При выполнении операций, операнды складываются в стек;
2. Совершаемая операция снимает нужное количество операндов со стека;
3. Результат помещается обратно на вершину стека и может использоваться в качестве операнда для следующей операции.

Плюсы такого подхода заключаются в простоте кода виртуальной машины и легкости реализации серии вычислений. Конечно есть и недостатки, основным из которых является то, что приходится жонглировать значениями, помещая и вынимая их из стека, чтобы дать возможность машине произвести над ними некоторое действие. Судите сами: в описанном в прошлой статье примере (Collection>>sort:) мы многократно помещаем значения в стек только для того, чтобы тут же извлечь их обратно, скопировать в инстанцию класса Array, а затем опять положить объект на стек (этим занимается markArguments).

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

Однако с точки зрения современной процессорной архитектуры Smalltalk очень неудобен. Большая часть операций совершается с памятью. Принцип локальности не выдерживается (объекты все разбросаны по куче далеко друг от друга). Постоянно порождаются новые объекты, что приводит к сборке мусора и очередному перетасовыванию большого объема памяти. Все операции с памятью адресуются косвенно. Наконец, большое количество маленьких методов приводит к невозможности адекватного назначения регистров.

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

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

Стек значений JIT компилятора

Промежуточное представление кода в LLVM использует нотацию SSA. В данной нотации не существует переменных в привычном нам виде. Всё вычисление — есть граф. Каждому результату вычисления (узлу) можно присвоить имя, и использовать это имя в дальнейших вычислениях (связать два узла). Причем, однажды обозначенное имя поменять свое значение не может (повторное присваивание значения тому же имени не допускается). Имя относится только к той точке программы (и тем данным), где было объявлено. В тех местах, где все же приходится работать с памятью, используются инструкция alloca, которая выделяет область памяти запрашиваемого размера, а также инструкции load и store для чтения и записи соответственно.

Давайте еще раз обратим свое внимание на байт-коды Smalltalk, необходимые для инициализации переменной left из описанного ранее метода сортировки:

"left <- List new"
0023 PushLiteral 4
0024 MarkArguments 1
0025 SendMessage new
0026 AssignTemporary 0
0027 DoSpecial popTop

Другой пример, начало блока из того же метода:

0037     PushArgument 1             "criteria"
0038     PushTemporary 3            "x"
0039     PushTemporary 2            "mediane"
0040     MarkArguments 3
0041     SendMessage value:value:   "основное условие сортировки"
0042     DoSpecial branchIfFalse 52

И в том и другом случае видно, что совершается большое количество простых операций с памятью. Основные push инструкции могут быть преобразованы в пару ассмеблерных инструкций. Необходимо всего лишь скопировать указатель (а ведь мы работаем только с указателями на структуры объектов) из одной области памяти по смещению индекса переменной в другую область по смещению индекса вершины стека.

Реализация «в лоб» указанных выше идей в IR коде может выглядеть примерно так:

define void @pushValueToStack(%TContext* %context, i32 %index, %TObject* %value) {
    %stackPointer = getelementptr inbounds %TContext* %context, i32 0, i32 4
    %stack = load %TObjectArray** %stackPointer
    %stackObject = bitcast %TObjectArray* %stack to %TObject*
    call %TObject** @setObjectField(%TObject* %stackObject, i32 %index, %TObject* %value)
    ret void
}

define %TObject** @setObjectField(%TObject* %object, i32 %index, %TObject* %value) {
    %fieldPointer = call %TObject** @getObjectFieldPtr(%TObject* %object, i32 %index)
    store %TObject* %value, %TObject** %fieldPointer
    ret %TObject** %fieldPointer
}

define %TObject** @getObjectFieldPtr(%TObject* %object, i32 %index) {
    %fields = getelementptr inbounds %TObject* %object, i32 0, i32 2
    %fieldPointer = getelementptr inbounds [0 x %TObject*]* %fields, i32 0, i32 %index
    ret %TObject** %fieldPointer
}

Да, она будет работать и, преобразованная в нативный код, будет быстрее, нежели аналогичная ей реализация для интерпретатора. Но итоговая производительность такой JIT VM будет на удивление низкой. Все дело в том, что сами операции работы с памятью никуда не делись. Мы просто перенесли их в низкоуровневый код, избавившись от «обертки» программной VM.

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

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

Нотация SSA позволяет сделать это напрямую, минуя стек. Всё, что нам надо сделать, это «запомнить», какие объекты мы подготовили к помещению в массив аргументов, а затем скопировать их сразу по месту будущего использования. Поскольку доступ к запомненным значениям также будет осуществляться последовательно по принципу LIFO, для хранения ссылок разумно использовать стек. Этот стек значений существует и используется только во время компиляции. Выполняться будет уже сформированный, «правильный» код.

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

Таким образом, получаем следующий алгоритм оптимизированной посылки сообщения:

1. Вместо проталкивания объекта на стек контекста (push) производим загрузку значения из памяти в переменную (load) и кладем ее в стек значений компилятора;
2. Обрабатывая инструкцию markArguments, мы создаем объект аргументов, а затем последовательно вынимаем элементы из стека значений и записываем (store) их подряд в слоты созданного массива аргументов;
3. Вызываем заглушку-обработчик sendMessage.

Получается, что вместо четырех операций с памятью (load значения, store значения в стек, load значения из стека и store в поле массива аргументов) мы оставили только две (load значения и store в массив).

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

Методы и функции

По мере своей работы виртуальная машина создает для каждого метода из образа его JIT версию. Она является функциональным эквивалентом метода, но реализуется уже в нативных инструкциях процессора. JIT функции создаются при первой посылке сообщения, которое еще не посылалось ранее. Например, при посылке сообщения List>>sort: сперва будет найден обработчик сообщения, которым является метод Collection>>sort: (поскольку класс List не имеет метода sort:, но унаследован от Collection). Затем виртуальная машина попробует найти JIT функцию с тем же именем и не найдет ее. Будет вызыван JIT компилятор, который по телу метода Collection>>sort: создаст эквивалентную ему функцию. Затем эта функция будет вызвана с теми же параметрами, что предназначались обычному сообщению. При следующей посылке компилятор вызываться не будет, а будет взята уже имеющаяся версия метода.

Посылка сообщений

Как мы помним из прошлой статьи, для посылки сообщения виртуальной машине требуется:

1. Снять значения со стека и создать массив аргументов (делается отдельным шагом в markArguments);
2. Найти метод в иерархии, который будет обрабатывать сообщение;
3. Сформировать объект контекста и заполнить поля;
4. Переключиться на выполнение нового контекста.

На данном этапе повлиять на процедуру поиска метода-адресата мы не можем, поскольку виртуальная машина не располагает информацией о типах объектов. Если говорить точнее, то эта информация доступна только на момент вызова и ее нельзя использовать для прогноза будущего типа объектов. Поэтому механизм поиска сообщения остается прежним и вызывается с помощью системной функции sendMessage(), зарегистрированной в модуле. Эта функция позволяет из JIT кода обратиться к программной VM и попросить ее найти адресата сообщения. Затем управление передается JIT версии найденного метода.

Программная VM все объекты создает только в куче, поскольку другой памяти у нее нет. В случае JIT VM мы можем существенно сократить издержки памяти путем размещения некоторых объектов на стеке. Такими объектами являются:

• Массив аргументов;
• Объект контекста;
• Массив временных переменных.

Время жизни этих объектов не меньше времени исполнения самого метода (поскольку на них всегда есть ссылки из активных контекстов), поэтому их можно разместить на стеке. При выходе из метода стек сворачивается до предыдущего фрейма, автоматически освобождая занятую память. Строго говоря, скорость выделения памяти на стеке и в куче примерно одинаковая. И там и там требуется лишь сдвинуть указатель на размер выделяемой памяти и вернуть получившееся значение. А в случае с кучей это может привести к необходимости сборки мусора, которая уже занимает значительное время. Чем чаще такое происходит, тем эффективнее будет работать стековый вариант.

Статистика

Идеальный конечный результат JIT компилятора можно представить так:

• Все задействованные методы Smalltalk преобразованы в функции
• Каждая посылка сообщения преобразована в прямой вызов функции (а не заглушки поиска)
• Раз есть прямые вызовы, то код блоков и мелких функций встроен по месту своего использования минуя посылки

Основной проблемой на пути достижения ИКР является неопределенность типа объекта от вызова к вызову. Рассмотрим еще раз уже известный нам метод Collection>>sort:

sort: criteria | left right mediane |
    (self size < 32)
        ifTrue: [ ^ self insertSort: criteria ].

    mediane <- self popFirst.

    left  <- List new.
    right <- List new.
    self do: [ :x |
        (criteria value: x value: mediane)
            ifTrue:  [ left  add: x ]
            ifFalse: [ right add: x ] ].

    left  <- left  sort: criteria.
    right <- right sort: criteria.

    right add: mediane.
    ^ left appendList: right

Что можно сказать о типах используемых переменных? Без контекста выполнения и вызывающего кода ничего определенного сказать нельзя. Это одновременно и сильная и слабая сторона Smalltalk. Сильная, потому что этот код будет работать одинаково эффективно, вне зависимости от класса потомка. Он одинаково отсортирует и список, и массив. Слабая, так как мы не можем на этапе компиляции делать оптимизации, опираясь на знание типов объектов.

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

Постулируя, что иерархия классов не меняется по ходу работы программы, мы сможем вместо условий вставлять прямые вызовы. К сожалению, суровая реальность и тут преподносит нам сюрприз. К примеру, после собрали статистику мы получили следующие результаты: из 10 последовательных вызовов 10 раз переменная оказалась класса String. Но это совершенно не означает, что так будет и в следующий раз. Проходя по коллекции объектов, мы можем встретить самые разнообразные классы. Наконец, даже метод, прежде возвращавший инстанцию String, может внезапно вернуть nil, просто потому что так сложились звезды были заданы параметры.

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

Вывод типов

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

Например, глядя на описанный выше метод Collection>>sort:, внимательный читатель может заметить, что переменные left и right всегда инициализируются инстанциями класса List. Виртуальная машина сможет это понять из следующих соображений:

1. Переменная left инициализируется результатом выражения List new
2. В выражение List new не принимает параметров и имеет фиксированный объект действия (List)
3. Посылка сообщения #new объекту List обрабатывается методом List>>new
4. Метод List>>new возвращает результат выражения super new
5. В текущем контексте это будет List super то есть Collection
6. Посылка сообщения #new объекту Collection обрабатывается методом Object>>new
7. Метод Object>>new содержит примитив 7, который всегда возвращает объект известного класса (аксиома)

Дальше выражения сворачиваются в обратном порядке, что приводит к утверждению: «Переменная left инициализируется объектом класса List».

Зная класс переменных left и right, остаток метода также может быть оптимизирован. Операции #add:, #sort: и #appendList: компилируются с использованием прямых вызовов методов без дополнительных условий.

На самом деле доскональный вывод типов нам желателен, но не обязателен. Достаточно знать, что тип переменной от вызова к вызову не меняется. А какой именно он будет, мы узнаем при первой фактической посылке сообщения. Всё вместе позволит исключить проверки типов при выполнении программы, уменьшить объем кода и развязать руки оптимизатору.

Компиляция

Тем, кто дочитал до этого момента, но имеет слабое представление о том, что же такое LLVM, я советую почитать многочисленные и довольно неплохие посты на хабре, либо статьи Hacker’s introduction to LLVM и LLVM Language Reference Manual. На английском, разумеется.

Итак, LLVM принимает на вход IR представление, записанное в виде цепочек инструкций. Инструкции организованы в неделимые сущности, называмые базовыми блоками (basic block). Особенностью такого блока является то, что у него есть только один вход и один выход. Это сделано намеренно, для удобства работы. Внутри блока могут располагаться любые инструкции, кроме тех, что передают управление. То есть, условные переходы, инструкции возврата, выброса и отлова исключений не могут находиться в середине блока (вызовы функций допустимы, если они не бросают исключений). Если такое все же необходимо, то блок в этом месте делится на два, так, чтобы проблемная инструкция (в терминологии LLVM она называется терминатором) стояла в хвосте первой половины. Таким образом, вся функция состоит из набора базовых блоков и переходов между ними (сами инструкции перехода оперируют не адресами, а идентификаторами блоков, куда нужно передать управление).

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

Первой проблемой оказывается то, что байт-коды метода записаны слитно, одним массивом. Естественно, там нет никаких базовых блоков, а все адреса переходов записаны в системе смещений относительно начала массива. Поэтому первое, что нам нужно, это построить соответствие между смещениями в инструкциях перехода и базовыми блоками. Сейчас это делается предварительным проходом по байт-кодам (метод scanForBranches из MethodCompiler.cpp)

Имея на руках «рыбу» будущих блоков метода, мы начинаем «набивать» ее инструкциями. Сама набивка происходит последовательно. Мы идем с начала метода, транслируя инструкции Smalltalk в соответствующие им операции в IR коде. Напомню, что push инструкции не кодируются непосредственно: вместо этого мы кладем в стек значений структуру TDeferredValue (см. также TStackValue), описывающую необходимое отложенное действие. Затем, когда в коде мы наткнемся на операцию, снимающую такое значение со стека, мы выполняем отложенное действие и получаем фактическое имя, которое уже можно использовать. В простых случаях, коих большинство, действия откладываются всего на пару инструкций, поэтому фактическое положение операции в коде не меняется. По сути происходит логическое связывание двух мест в коде, без необходимости введения промежуточных значений (или использования стека контекста). Как именно будет реализована передача значения в настоящем коде, решает уже LLVM.

Например, если в байт-кодах у нас было:

"left <- List new"
0023 PushLiteral 4
0024 MarkArguments 1
0025 SendMessage new
0026 AssignTemporary 0
0027 DoSpecial popTop

…то при компиляции этого куска, последовательность действий будет такой:

1. Создаем отложенную операцию «положить четвертый литерал в стек».
2. Инструкция markArguments требует снятия значения со стека. Это приводит к выполнению отложенной операции: создаем имя lit0, к которому привязываем операцию чтения четвертого элемента из массива литералов. Это имя кладем в стек значений текущего базового блока.
3. Создаем массив из одного элемента, связываем его с именем args0. При наполнении массива снимаем одно значение со стека. При снятии значения мы видим, что локальный стек значений не пуст, поэтому берем значение из него (это будет lit0). Таким образом, имеем: args0[0] = lit0.
4. Вставляем вызов функции sendMessage, передавая в качестве параметров оформленный ранее массив аргументов args0. Результат посылки сообщения кладем в стек значений (так же в виде отложенного действия, но несколько другого типа).
5. Получаем имя temp0, связанное с нулевой ячейкой массива временных переменных. Кодируем операцию записи вершины стека в temp0.
6. Просто снимаем значение со стека значений и выбрасываем (popTop).

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

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

У нас же даже массив аргументов не создается на куче, а располагается в реальном стеке вызовов потока. Поэтому и аллокация, и заполнение массива происходит быстро. Самое главное, что LLVM, оперируя IR, вольна делать все виды оптимизаций, которые мы не видим напрямую, но которые она посчитает уместными.

Например, может получиться так, что одно и то же значение temp используется два раза подряд. Тогда вместо повторного чтения значения, LLVM может использовать предыдущее имя (если это не повлияет на результат). И таких мелочей набирается целая куча.

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

Все операции push совершаются над локальным стеком значений текущего базового блока. Операции взятия значения со стека могут быть нелокальными. В этом случае значение снимается с блока выше по иерархии переходов. Например: существует два базовых блока X и Y. Блок X состоит из операций pushTemporary 0 и branch <Y>, где <Y> соответствует смещению первой инструкции из блока Y. Допустим, в блоке Y первой идёт инструкция markArguments 1, которой необходимо снять значение со стека. Как мы понимаем, на момент обработки блока Y такого значения в локальном стеке блока не будет. Поэтому компилятор заглянет дальше по иерархии и обнаружит, что блок Y вызывается из блока X, у которого стек не пуст. Поэтому значение будет взято оттуда.

Если же в блок Y можно попасть из нескольких блоков X₁..X_n, то компилятор вынужден будет создать φ-функцию, которая агрегирует значения из нескольких блоков в рамках нотации SSA. Входами этой функции будут заданы значения из стеков каждого из вышестоящих блоков X_i, результатом функции будет считаться один из входов в зависимости от того, из какого блока пришло управление. Операции совершаются рекурсивно до тех пор, пока все значения не будут обработаны.

Более подробно этот момент можно изучить, прочитав исходник метода MethodCompiler::TJitContext::popValue() и документ JITCompilation.txt в репозитории.

Заключение

Собственно говоря, это всё, что можно рассказать о компиляции «на пальцах». Поначалу я хотел привести еще листинги скомпилированных методов, но потом решил, что захламлять и без того длинную статью будет неуважением к читателям. Ведь один только метод Collection>>sort: в выводе занимает полтыщи строк, а методов там участвует больше десятка. К тому же, подобный вывод для бенчмарков есть в шеллкастах, приведенных в начале статьи.

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

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

Автор: Halt

Источник