CS Notes

compilation

8 min read

Компиляция

Предпосылки: Токенизация и парсинг; стек (LIFO — кладём и забираем с вершины).

← Токенизация и парсинг | Исполнение →

Код прошёл два превращения: текст → токены → AST. Дерево зафиксировало смысл программы — какие вызовы, какие аргументы, какая вложенность. Но AST — это древовидная структура, где для каждого действия нужно спуститься по ветвям, найти нужные узлы, вернуться обратно. Для выполнения это неудобно.

Ruby 1.8 так и делал: обходил дерево и выполнял каждый узел. С Ruby 1.9 появился третий шаг — компиляция: дерево переводится в плоскую последовательность инструкций для виртуальной машины YARV (Yet Another Ruby Virtual Machine). Плоский список команд виртуальная машина выполняет гораздо быстрее, чем обход дерева.

flowchart LR
    T["текст"] --> Tok["токены"] --> AST --> Comp["<b>компиляция</b>"] --> YARV["инструкции YARV"] --> Exec["исполнение"]

Компиляция Ruby похожа на компиляцию в других языках: компилятор C переводит код в машинный язык, компилятор Java — в байткод JVM, компилятор Ruby — в байткод YARV. Разница в том, что компилятор Ruby запускается автоматически при каждом запуске программы — вы его не вызываете отдельно. Независимо от того, какой парсер построил дерево — Prism или parse.y — компилятор переводит AST в одинаковые инструкции YARV (у каждого парсера свой путь компиляции, но результат один).

Компиляция происходит пофайлово в момент загрузки. Когда вы запускаете ruby script.rb, Ruby целиком парсит и компилирует script.rb — включая тела всех def внутри — и только потом начинает выполнять инструкции. Если при выполнении встречается require 'other', Ruby приостанавливается, загружает, компилирует и выполняет other.rb, после чего возвращается к основному скрипту. Не «все файлы проекта заранее» и не «метод при первом вызове» — каждый файл компилируется целиком в тот момент, когда Ruby до него добирается.

Стековая машина

Прежде чем разбирать компиляцию, нужно понять, как устроена YARV — иначе непонятно, во что компилятор переводит код.

YARV — стековая машина. Это значит, что все вычисления происходят через стек значений. Инструкции либо кладут значения на стек, либо забирают значения со стека и оставляют результат. Никаких имён переменных, никаких скобок — только «положи» и «возьми».

Как выглядит вычисление 2 + 2 на стековой машине:

putobject 2       стек: [2]
putobject 2       стек: [2, 2]
opt_plus          стек: [4]

putobject 2 кладёт число 2 на стек. Второй putobject 2 кладёт ещё одну двойку. opt_plus забирает два верхних значения, складывает их и кладёт результат 4 обратно. На стеке остаётся одно число — результат. YARV — стековая машина: операнды кладутся на стек, инструкция забирает с вершины. В отличие от физических процессоров, где операнды хранятся в регистрах.

На самом деле YARV использует два стека: стек значений (то, что мы только что видели — операнды и результаты инструкций) и стек фреймов (по одному фрейму на каждый вызов метода или блока — в нём хранятся локальные переменные, self, точка возврата). Физически оба стека живут в одном непрерывном куске памяти: стек значений растёт снизу вверх, стек фреймов — сверху вниз, навстречу друг другу:

низкие адреса                                        высокие адреса
┌──────────────────────┬──────────────────┬──────────────────────┐
│  стек значений  →→→  │  свободное место │  ←←←  стек фреймов   │
└──────────────────────┴──────────────────┴──────────────────────┘

Когда свободное место заканчивается — стеки встречаются — Ruby бросает SystemStackError. Это и есть stack overflow: чаще всего его вызывает бесконечная рекурсия, где каждый вызов добавляет новый фрейм сверху, пока место не кончится.

Компиляция вызова метода

Возьмём puts 2+2. AST для этого кода (из предыдущей заметки) выглядит так: вызов функции puts, аргумент — вызов метода + на числе 2 с аргументом 2.

Компилятор обходит дерево и для каждого вызова метода генерирует инструкции по одному и тому же паттерну:

  1. Положи получателя (объект, у которого вызывается метод)
  2. Положи аргументы
  3. Выполни вызов

Для puts 2+2 компилятор начинает с внешнего вызова — puts. Получатель puts — текущий self (мы на верхнем уровне программы). Аргумент — результат 2+2. Но 2+2 — это тоже вызов метода: 2.+(2). Компилятор рекурсивно спускается по AST и применяет тот же паттерн.

Результат — плоская последовательность инструкций:

putself                  # получатель puts (текущий self)
putobject 2              # получатель метода + (число 2)
putobject 2              # аргумент метода + (число 2)
opt_plus                 # вызов 2+2 → результат 4 на стеке
opt_send_without_block   # вызов puts(4)
leave                    # конец программы

Стековая машина и рекурсивная компиляция идеально сочетаются: когда компилятор заканчивает компиляцию 2+2, результат остаётся на стеке — ровно там, где он нужен как аргумент для puts. Компилятору не нужно «передавать» значение — стек сам это обеспечивает.

opt_plus и opt_send_without_block — оптимизированные версии инструкции send. Об этом — чуть дальше.

Scope: каждый блок — отдельная программа

У каждой области видимости (scope) — метода, блока, лямбды — свои локальные переменные. Это значит, каждая из них нуждается в собственной таблице переменных и собственном наборе инструкций. Ruby представляет каждую область видимости как независимую единицу компиляции — ISeq.

Теперь скомпилируем 10.times do |n| puts n end. Здесь появляется блок, и это меняет картину: Ruby компилирует каждую область видимости (scope) — метод, блок, лямбду, класс, модуль — в отдельный набор инструкций.

Для 10.times do |n| puts n end Ruby создаёт два фрагмента:

Фрагмент 1 — основная программа:

putobject 10                    # получатель times
send :times, block: <block>    # вызов с блоком
leave

Фрагмент 2 — блок do |n| puts n end:

putself                         # получатель puts
getlocal n                      # аргумент puts (параметр блока)
opt_send_without_block :puts    # вызов puts(n)
leave

Инструкция send :times содержит ссылку на блок — второй фрагмент. Когда times будет вызывать блок на каждой итерации, YARV переключится на выполнение инструкций второго фрагмента.

Каждый такой фрагмент называется ISeq — instruction sequence (rb_iseq_t в исходниках). Это самостоятельная единица: свои инструкции, свои переменные, своя таблица локальных переменных. Если бы внутри блока был ещё один блок — Ruby создал бы третий фрагмент.

ISeq живёт в памяти как Ruby-объект. По умолчанию на диск он не сохраняется — при каждом запуске Ruby компилирует заново. Но ISeq можно сериализовать (RubyVM::InstructionSequence#to_binary) и загрузить обратно (load_from_binary) — этим пользуется Bootsnap, чтобы при повторном запуске Rails-приложения не перекомпилировать все файлы. Когда def определяет метод, ISeq прикрепляется к записи метода в таблице методов класса. Как VM потом исполняет эти инструкции — в следующей заметке.

Таблица локальных переменных

Инструкции YARV не знают имён переменных — только числовые индексы. getlocal n на самом деле выглядит как getlocal_WC_0 0 — «возьми локальную переменную с индексом 0». Чтобы понять, какая переменная скрывается за каким индексом, каждый фрагмент инструкций хранит таблицу локальных переменных (local table).

Для блока do |n| puts n end таблица содержит одну запись:

local table (size: 1, argc: 1)
[1] n <Arg>

n — параметр блока, помеченный <Arg>. Индекс 1 — по нему инструкция getlocal находит значение n.

Таблица становится интереснее для методов со сложными аргументами. Возьмём:

def complex_formula(a, b, *args, c)
  a + b + args.size + c
end

Local table:

[4] a <Arg>    [3] b <Arg>    [2] args <Rest>    [1] c <Post>

Ruby помечает разные типы аргументов: <Arg> — обычный, <Rest> — массив, собранный через splat *, <Post> — аргумент, стоящий после splat. Есть и другие пометки: <Opt=0> для аргументов со значением по умолчанию, <Block> для блока, переданного через &.

Таблица локальных переменных — своего рода «легенда» к инструкциям. Без неё числовые индексы в getlocal и setlocal были бы бессмысленными.

Оптимизация инструкций

В примере puts 2+2 вместо send :+ стоит opt_plus, а вместо send :puts — opt_send_without_block. Это результат оптимизации: после компиляции Ruby проходит по инструкциям и заменяет вызовы часто используемых методов специализированными инструкциями.

opt_plus работает быстрее send :+, потому что для стандартных числовых типов она выполняет сложение напрямую, без полного поиска метода в таблице. Если метод + переопределён (например, вы определили свой + на каком-то классе), YARV обнаружит это и вернётся к обычному вызову через send.

Помимо opt_plus, Ruby использует opt_minus, opt_mult, opt_size, opt_length, opt_send_without_block (для вызовов без блока) и другие — для операций, которые встречаются в коде чаще всего.

Инструменты: RubyVM::InstructionSequence

RubyVM::InstructionSequence позволяет скомпилировать код и посмотреть результат:

puts RubyVM::InstructionSequence.compile('puts 2+2').disasm
== disasm: #<ISeq:<compiled>@<compiled>:1 (1,0)-(1,8)>
0000 putself                                                          (   1)
0001 putobject                              2
0003 putobject                              2
0005 opt_plus                               <calldata!mid:+, argc:1, ARGS_SIMPLE>
0007 opt_send_without_block                 <calldata!mid:puts, argc:1, FCALL|ARGS_SIMPLE>
0009 leave

Числа слева — позиции инструкций в массиве байткода. calldata содержит метаданные вызова: mid:+ — имя метода, argc:1 — один аргумент, FCALL — вызов функции (без явного получателя), ARGS_SIMPLE — простые аргументы.

Для 10.times do |n| puts n end в выводе будет два фрагмента — основная программа и блок:

code = <<~RUBY
  10.times do |n|
    puts n
  end
RUBY
puts RubyVM::InstructionSequence.compile(code).disasm
== disasm: #<ISeq:<compiled>@<compiled>:1 (1,0)-(3,3)>
0000 putobject                              10                        (   1)
0002 send                                   <calldata!mid:times, argc:0>, block in <compiled>
0005 leave

== disasm: #<ISeq:block in <compiled>@<compiled>:1 (1,9)-(3,3)>
local table (size: 1, argc: 1)
[1] n@0<Arg>
0000 putself                                                          (   2)
0001 getlocal_WC_0                          n@0
0003 opt_send_without_block                 <calldata!mid:puts, argc:1, FCALL|ARGS_SIMPLE>
0005 leave

Первый фрагмент — putobject 10, send :times со ссылкой на блок, leave. Второй фрагмент — инструкции блока с local table, показывающей параметр n. send :times содержит block in <compiled> — ссылку на второй фрагмент.

RubyVM::InstructionSequence — MRI-специфичный API. Формат вывода может меняться между версиями Ruby, но идея та же: каждый scope компилируется отдельно, инструкции работают со стеком, local table связывает индексы с именами.

От байткода к машинному коду

До Ruby 3.1 YARV-инструкции только интерпретировались — виртуальная машина читала их одну за другой. С Ruby 3.1 появился YJIT — встроенный JIT-компилятор, который во время выполнения замечает горячие участки и переводит их YARV-инструкции в машинный код процессора. В Ruby 4.0 добавлен экспериментальный ZJIT — следующее поколение того же слоя. Оба работают поверх тех же инструкций YARV, которые создаёт компилятор: байткод остаётся основой исполнения, а JIT ускоряет только часто используемый код.

Sources

← Токенизация и парсинг | Исполнение →

Graph View

Backlinks