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

В прошлой статье мы спустились до конца: выбрали инструкции реального процессора, распределили регистры, соблюли ABI. Это дорогой путь. Он требует знать систему команд целевой архитектуры, её кодировку, соглашения о вызовах, формат объектных файлов — и повторить всё это для каждой новой платформы. Для учебного языка, для скриптового движка внутри игры, для конфигурационного DSL, для смарт-контракта цена явно завышена.

Есть второй бэкенд, и он на порядок дешевле: придумать процессор самому. Раз система команд наша, мы вольны сделать её удобной для генерации, компактной, безопасной и одинаковой на всех платформах. Программа, которая исполняет такие команды, называется виртуальной машиной, а её система команд — байткодом.

Так работают Java, C#, Python, Ruby, Lua, Erlang, Smalltalk, PHP, Ethereum и WebAssembly. Эта статья — про то, как устроен такой бэкенд изнутри: как спроектировать набор инструкций, чем стековая машина отличается от регистровой и почему индустрия разошлась в этом вопросе, как выглядит кадр вызова, из чего складывается стоимость интерпретации и что делать, когда она перестаёт устраивать. К концу мы скомпилируем язык Mini в байткод и запустим две ВМ — стековую и регистровую, — а потом сравним их по числу исполненных инструкций.

Что такое виртуальная машина

Термин перегружен, и первым делом его нужно расщепить.

Системная ВМ (VMware, KVM, QEMU, Hyper-V) эмулирует целый компьютер: процессор, память, устройства, — чтобы на нём запустилась немодифицированная операционная система. Об этом подробно говорит статья про виртуализацию и контейнеры, и дальше речь пойдёт не о ней.

Процессная ВМ, она же ВМ языка, — это программа, исполняющая инструкции придуманной системы команд в рамках одного процесса. У неё нет прерываний, MMU и драйверов; вместо них — стек значений, куча, вызовы функций и инструкции ровно того уровня, который нужен исходному языку.

Формально виртуальная машина — это абстрактная машина, заданная четвёркой: множество состояний, набор инструкций, функция перехода и правила входа/выхода. Такая формулировка не украшение: SECD-машина Питера Ландина (1964) была придумана именно как способ строго определить вычисление лямбда-выражений, и все современные байткод-машины — её далёкие потомки. Связь с стратегиями вычисления прямая: набор инструкций ВМ фиксирует порядок вычисления так же жёстко, как это делает промежуточное представление.

Зачем спускаться в байткод, а не в машинный код

Цена одна, зато существенная: интерпретация медленнее. Простая ВМ на C проигрывает нативному коду в 10–50 раз, тщательно оптимизированная — в 3–10. Откуда берётся эта константа и как её уменьшить — вторая половина статьи.

Байткод как формат

Байткод — это линейная последовательность байтов, где первый байт инструкции задаёт операцию, а следующие байты — её операнды. Формат почти всегда пакуют в структуру, которую в разных проектах зовут chunk, code object, Code_t или method body:

• массив кода — собственно байты;
• пул констант — числа, строки, ссылки на функции, всё, что не помещается в байт операнда;
• число слотов кадра — сколько локальных переменных нужно функции;
• таблица отладочной информации — соответствие смещений строкам исходника (LineNumberTable в JVM, co_linetable в CPython по PEP 626).

Пул констант выглядит лишней косвенностью, пока не вспомнишь, зачем он: операнд шириной в байт адресует 256 значений, а константа 3.14159 или строка занимают 8 и более байт. Кроме того, пул даёт бесплатную дедупликацию и — что важнее — единственное место, где сборщик мусора видит все объекты, на которые ссылается код.

Ключевые решения при проектировании кодировки:

Ширина инструкции. Байтовая (JVM, EVM) — максимальная плотность, но операнды приходится дочитывать по одному байту. Словная (Lua — 32 бита, CPython с версии 3.6 — 16 бит) — выровненное чтение одной операцией и никакого побайтового разбора; за это платят пустыми битами. На современном процессоре выравненное чтение обычно выигрывает, и тренд — в сторону слов.

Escape для больших операндов. Если операнд не влез в байт, нужен запасной путь: wide в JVM, EXTENDED_ARG в CPython, формат iAx в Lua. Забыть про него — значит поставить в языке необъяснимый предел на число локальных переменных.

Специализированные опкоды. JVM тратит отдельные коды на iload_0, iload_1, iload_2, iload_3 — однобайтовые формы самых частых инструкций. Это чистый обмен пространства опкодов на плотность кода и на одну сэкономленную диспетчеризацию операнда. Из 256 возможных кодов JVM занимает около двухсот, и большая их часть уходит именно на такие частные случаи.

Структурность управления. Классический байткод допускает переход по любому смещению. WebAssembly пошёл другим путём: там нет произвольных переходов, есть блоки block/loop/if и выходы наружу на N уровней. Это делает проверку корректности однопроходной и линейной по времени — решение, продиктованное безопасностью.

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

Стековая ВМ хранит промежуточные значения в стеке операндов. Инструкции не называют операнды: ADD снимает две верхние ячейки и кладёт сумму.

Главное достоинство — тривиальная генерация кода. Постфиксный обход дерева выражения (тот самый, что мы разбирали в статье про AST) сразу даёт корректный байткод: посети левое поддерево, посети правое, выдай операцию. Распределять нечего, временных имён не нужно, любое выражение любой глубины компилируется одинаково.

Второе достоинство — плотность: инструкция без операндов занимает один байт. Третье — простая верификация: глубина стека в каждой точке программы вычислима статически, и по ней проверяется, что ADD не выполнится на пустом стеке.

Недостатки зеркальны. Значение, посчитанное инструкцией, немедленно уходит в память стека, а следующая инструкция достаёт его обратно — трафик, которого в регистровой машине нет. Инструкций получается много, а каждая инструкция — это одна диспетчеризация, самая дорогая часть интерпретации. И «переиспользовать» посчитанное значение нельзя: если оно нужно дважды, его либо дублируют (DUP), либо считают заново, либо сохраняют в локальный слот.

Полезная связь с теорией: стек с конечным управлением — это в точности магазинный автомат, только память ячеек у нас не из конечного алфавита. Отсюда же ограничение EVM: стек глубиной 1024 и доступ только к 16 верхним элементам — следствие требования, чтобы стоимость исполнения была ограничена сверху.

Регистровая машина

Регистровая ВМ адресует операнды по номерам: ADD R3, R0, R1. «Регистры» тут — не регистры процессора, а слоты текущего кадра; для машины это просто индексы в массиве. Инструкция становится трёхадресной, то есть выглядит ровно как трёхадресный код IR — что не случайно: в регистровую ВМ IR ложится почти без перевода.

Плюсы и минусы меняются местами. Инструкций меньше, потому что промежуточные значения остаются на месте и не перекладываются. Зато каждая инструкция шире: Lua тратит на неё 32 бита (7 бит опкода, дальше поля A, B, C по 8–9 бит), и суммарный размер кода получается больше. Компилятору нужен распределитель слотов — это тот же алгоритм, что и в генерации кода, но проще: слотов много (в Lua до 255 на функцию), давление на регистры почти нулевое, и хватает наивной стратегии «слот на живой временный».

Замер на нашем примере (обе ВМ ниже в статье, обе исполняют fib(20)):

Регистровая версия исполняет на 45% меньше инструкций при коде на четверть большего размера. Это ровно то, что получили Ши, Кейси, Эртль и Грегг в «Virtual Machine Showdown: Stack Versus Registers»: около 47% экономии на числе исполненных инструкций, около 25% прибавки к размеру кода и выигрыш по времени порядка четверти при честном сравнении. Команда Dalvik сообщала о близких цифрах при переводе Java-байткода в свой регистровый формат.

Отсюда исторический расклад: машины, спроектированные как формат распространения кода (JVM, CLR, WebAssembly, EVM), — стековые, там важнее компактность и простота верификации. Машины, спроектированные как рантайм конкретного языка (Lua 5, Dalvik, BEAM, PyPy на своём уровне), — регистровые, там важнее скорость интерпретации. Обе крайности живут и здравствуют.

Проектируем ВМ для Mini

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

Смещения переходов — относительные и знаковые: так код функции можно перемещать в памяти, не переписывая переходы, и 16 бит хватает на функцию размером 32 КБ. Отсчёт ведём от байта, следующего за инструкцией, — ровно как это делает JVM и как делают процессоры.

from dataclasses import dataclass, field
from enum import IntEnum

class Op(IntEnum):
    CONST = 0     # u8: индекс в пуле констант
    LOAD  = 1     # u8: номер слота кадра
    STORE = 2     # u8: номер слота кадра
    ADD = 3; SUB = 4; MUL = 5; LT = 6; EQ = 7
    JMP  = 8      # i16: относительное смещение
    JMPF = 9      # i16: относительное смещение, снимает вершину
    CALL = 10     # u8: индекс функции, u8: число аргументов
    RET  = 11
    POP  = 12

OPERANDS = {Op.CONST: (1,), Op.LOAD: (1,), Op.STORE: (1,),   # ширины операндов в байтах:
            Op.JMP: (2,), Op.JMPF: (2,), Op.CALL: (1, 1)}     # одна таблица на компилятор,
                                                              # ВМ и дизассемблер

@dataclass
class Code:
    name: str
    nparams: int
    code: bytearray = field(default_factory=bytearray)
    consts: list = field(default_factory=list)
    nslots: int = 0                       # размер кадра в слотах

Одна таблица OPERANDS на три компонента — не эстетство. Как только ширины операндов разъезжаются между кодогенератором и интерпретатором, вы получаете ошибку, которая проявляется как «ВМ сошла с ума на сотой инструкции», и ищется она часами.

Компилятор: AST → байткод

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

class FnCompiler:
    def __init__(self, fn, fnindex):
        self.fnindex = fnindex                       # имя функции -> её номер
        self.out = Code(fn.name, len(fn.params))
        self.slots = {p: i for i, p in enumerate(fn.params)}
        self.out.nslots = len(fn.params)
        for s in fn.body:
            self.stmt(s)
        self.emit(Op.CONST, self.const(0))           # неявный `return 0`
        self.emit(Op.RET)

    def emit(self, op, *ops):
        self.out.code.append(int(op))
        for width, val in zip(OPERANDS.get(op, ()), ops):
            self.out.code += int(val).to_bytes(width, "little", signed=(width == 2))

    def const(self, v):
        if v not in self.out.consts:
            self.out.consts.append(v)
        return self.out.consts.index(v)

    def slot(self, name, declare=False):
        if declare or name not in self.slots:
            self.slots[name] = self.out.nslots
            self.out.nslots += 1
        return self.slots[name]

    def emit_jump(self, op):
        self.emit(op, 0)                             # заглушка, адрес ещё не известен
        return len(self.out.code)                    # позиция сразу после инструкции

    def patch_to(self, pos, target):                 # обратная заплатка
        self.out.code[pos - 2:pos] = (target - pos).to_bytes(2, "little", signed=True)

    def patch(self, pos):
        self.patch_to(pos, len(self.out.code))

    # --- выражения: каждое оставляет РОВНО ОДНО значение на стеке ---
    def expr(self, e):
        match e:
            case Num(value=v):
                self.emit(Op.CONST, self.const(v))
            case Var(name=n):
                self.emit(Op.LOAD, self.slots[n])
            case Binary(op=o, left=l, right=r):
                self.expr(l); self.expr(r)           # порядок вычисления фиксируем здесь
                self.emit({"+": Op.ADD, "-": Op.SUB, "*": Op.MUL,
                           "<": Op.LT, "==": Op.EQ}[o])
            case Call(callee=c, args=a):
                for arg in a:
                    self.expr(arg)                   # аргументы кладём слева направо
                self.emit(Op.CALL, self.fnindex[c], len(a))

    # --- инструкции: стековый эффект НУЛЕВОЙ ---
    def stmt(self, s):
        match s:
            case Let(name=n, init=i):
                self.expr(i); self.emit(Op.STORE, self.slot(n, declare=True))
            case Assign(name=n, value=v):
                self.expr(v); self.emit(Op.STORE, self.slots[n])
            case Return(value=v):
                self.expr(v); self.emit(Op.RET)
            case If(cond=c, then=t, els=e):
                self.expr(c)
                to_else = self.emit_jump(Op.JMPF)
                for st in t: self.stmt(st)
                if e:
                    to_end = self.emit_jump(Op.JMP)
                    self.patch(to_else)
                    for st in e: self.stmt(st)
                    self.patch(to_end)
                else:
                    self.patch(to_else)
            case While(cond=c, body=b):
                top = len(self.out.code)
                self.expr(c)
                to_end = self.emit_jump(Op.JMPF)
                for st in b: self.stmt(st)
                self.patch_to(self.emit_jump(Op.JMP), top)   # прыжок назад
                self.patch(to_end)
            case _:
                self.expr(s); self.emit(Op.POP)      # выражение-инструкция

def compile_program(fns):
    index = {f.name: i for i, f in enumerate(fns)}
    return [FnCompiler(f, index).out for f in fns]

Два инварианта, которые стоит выписать на бумажке и проверять при каждой правке:

1. Выражение оставляет на стеке ровно одно значение, инструкция — ноль. Из этого следует, что стек между инструкциями пуст, а значит, глубина стека в любой точке однозначна и вычислима статически.
2. Все переходы патчатся. Незапатченный переход — это +0, то есть бесконечный цикл или падение. Разумно держать счётчик открытых заплаток и падать при завершении компиляции, если он не ноль.

Дизассемблер пишется в десяток строк на той же таблице OPERANDS и окупается мгновенно. Вот что порождает компилятор для fn fib(n) { if n < 2 { return n; } return fib(n-1) + fib(n-2); }:

fn fib/1  слотов: 1  констант: [2, 1, 0]
0000  LOAD  0
0002  CONST 0        ; 2
0004  LT
0005  JMPF  3        ; -> 0011
0008  LOAD  0
0010  RET
0011  LOAD  0
0013  CONST 1        ; 1
0015  SUB
0016  CALL  0 1
0019  LOAD  0
0021  CONST 0        ; 2
0023  SUB
0024  CALL  0 1
0027  ADD
0028  RET
0029  CONST 2        ; 0     <- неявный `return 0`, сюда управление не доходит
0031  RET

Первое, что нужно сделать в своей ВМ, — именно дизассемблер. Отлаживать байткод, глядя на bytearray(b'\x01\x00...'), невозможно; javap -c, python -m dis, luac -l существуют ровно поэтому.

Кадры вызова

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

Классическое решение (Lua, clox, CPython): аргументы уже лежат на стеке значений там, где им и место — в начале кадра вызываемой функции. Кадр описывается тройкой «код, указатель инструкции, база»; база — индекс в стеке значений, с которого начинаются слоты. Локальная переменная k — это stack[base + k].

стек значений в момент, когда fib(3) вызвал fib(2)

 индекс:    0         1         2         3
        +---------+---------+---------+---------+
        |  n = 3  |  n = 2  |  врем.  |  врем.  |
        +---------+---------+---------+---------+
        ^         ^                             ^
        base #0   base #1                       вершина

стек кадров — отдельный массив:
  #0  code=fib  ip=0x13  base=0     <- ждёт результата CALL
  #1  code=fib  ip=0x0b  base=1     <- исполняется сейчас

слот 0 кадра #1 — это stack[base + 0] = stack[1] = 2

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

Реализация цикла — сердце ВМ. Здесь важно каждое слово: ip держим в локальной переменной кадра, при вызове он уже указывает на следующую инструкцию, поэтому возвращаться некуда специально.

@dataclass
class Frame:
    code: Code
    ip: int
    base: int

class VM:
    def __init__(self, program):
        self.program, self.steps = program, 0

    def run(self, entry, args=()):
        code = next(c for c in self.program if c.name == entry)
        self.stack = list(args) + [0] * (code.nslots - len(args))
        frames = [Frame(code, 0, 0)]
        f, st = frames[-1], self.stack
        while True:
            self.steps += 1
            op = f.code.code[f.ip]; f.ip += 1              # FETCH
            if op == Op.CONST:                             # DECODE + EXECUTE
                st.append(f.code.consts[f.code.code[f.ip]]); f.ip += 1
            elif op == Op.LOAD:
                st.append(st[f.base + f.code.code[f.ip]]); f.ip += 1
            elif op == Op.STORE:
                st[f.base + f.code.code[f.ip]] = st.pop(); f.ip += 1
            elif op == Op.ADD:
                b = st.pop(); st[-1] += b
            elif op == Op.SUB:
                b = st.pop(); st[-1] -= b
            elif op == Op.MUL:
                b = st.pop(); st[-1] *= b
            elif op == Op.LT:
                b = st.pop(); st[-1] = st[-1] < b
            elif op == Op.EQ:
                b = st.pop(); st[-1] = st[-1] == b
            elif op == Op.JMP:
                off = int.from_bytes(f.code.code[f.ip:f.ip+2], "little", signed=True)
                f.ip += 2 + off
            elif op == Op.JMPF:
                off = int.from_bytes(f.code.code[f.ip:f.ip+2], "little", signed=True)
                f.ip += 2
                if not st.pop(): f.ip += off
            elif op == Op.POP:
                st.pop()
            elif op == Op.CALL:
                idx, argc = f.code.code[f.ip], f.code.code[f.ip+1]; f.ip += 2
                callee = self.program[idx]
                base = len(st) - argc                      # аргументы уже на месте
                st += [0] * (callee.nslots - argc)         # добить слоты нулями
                frames.append(Frame(callee, 0, base))
                f = frames[-1]
            elif op == Op.RET:
                v = st.pop()
                del st[f.base:]                            # срезать кадр целиком
                frames.pop()
                if not frames:
                    return v
                st.append(v)
                f = frames[-1]

Запускаем — и всё работает:

fib(20) = 6765   исполнено инструкций: 218906
main()  = 7      исполнено инструкций: 250

main здесь считает сумму fib(0..4) циклом while — то есть работают и переходы назад, и присваивания, и вложенные вызовы. Обратите внимание: рекурсия Mini не задействует стек Python. Кадры лежат в списке, глубина ограничена только памятью. Это принципиально: ВМ, которая для вызова гостевой функции рекурсивно вызывает себя, падает по переполнению нативного стека и не может дать языку внятную диагностику.

Та же функция на регистровой машине

Чтобы сравнение было честным, реализуем вторую ВМ — в стиле Lua. Инструкция это (op, A, B, C); поля B и C могут означать регистр (неотрицательное число) или константу (отрицательное). В Lua 5.3 роль такого признака играл старший бит операнда, в 5.4 для констант завели отдельные опкоды вида ADDK — идея та же.

K = lambda i: -i - 1                     # индекс константы кодируем отрицательным числом
FRAME = 8                                # окно регистров на кадр

fib_code = [                             # R0 = n
    ("LT",   1, 0, K(0)),                # R1 = n < 2
    ("JMPF", 1, 3, 0),                   # если ложно -> ip = 3
    ("RET",  0, 0, 0),                   # return n
    ("SUB",  2, 0, K(1)),                # R2 = n - 1
    ("CALL", 2, 0, 1),                   # R2 = fib(R2)
    ("SUB",  3, 0, K(0)),                # R3 = n - 2
    ("CALL", 3, 0, 1),                   # R3 = fib(R3)
    ("ADD",  4, 2, 3),                   # R4 = R2 + R3
    ("RET",  4, 0, 0),
]

class RVM:
    def __init__(self, code, consts): self.code, self.consts, self.steps = code, consts, 0

    def run(self, arg):
        regs = [0] * (FRAME * 1024)
        regs[0] = arg
        stack, base, ip = [], 0, 0
        rk = lambda x: self.consts[-x - 1] if x < 0 else regs[base + x]
        while True:
            self.steps += 1
            op, a, b, c = self.code[ip]; ip += 1
            if   op == "LT":   regs[base + a] = rk(b) < rk(c)
            elif op == "ADD":  regs[base + a] = rk(b) + rk(c)
            elif op == "SUB":  regs[base + a] = rk(b) - rk(c)
            elif op == "MOVE": regs[base + a] = regs[base + b]
            elif op == "JMP":  ip = b
            elif op == "JMPF":
                if not regs[base + a]: ip = b
            elif op == "CALL":
                stack.append((ip, base, a))
                regs[base + FRAME] = regs[base + a]        # аргумент -> R0 нового окна
                base, ip = base + FRAME, 0
            elif op == "RET":
                v = regs[base + a]
                if not stack: return v
                ip, base, dst = stack.pop()
                regs[base + dst] = v

RVM(fib_code, [2, 1]).run(20) возвращает те же 6765 за 120 398 шагов вместо 218 906. Разницу видно на глаз в самом коде: там, где стековая версия делает LOAD n; CONST 1; SUB, регистровая обходится одной инструкцией SUB R2, R0, K1.

Окно регистров здесь фиксированное (FRAME = 8) — так проще; настоящая Lua выделяет окно ровно того размера, который посчитал компилятор, и умеет растить стек. Именно с этим связана классическая ошибка в ВМ на C: после realloc стека все ранее взятые указатели на его элементы становятся мусором.

Диспетчеризация: где на самом деле уходит время

Разберём одну итерацию цикла. Полезной работы в инструкции ADD — одно машинное сложение. Вокруг него: чтение байта опкода, проверка границ, вычисление адреса перехода, сам переход, инкремент ip, работа с вершиной стека. В простых ВМ на диспетчеризацию уходит до половины всего времени — это измеряли Эртль и Грегг в «The Structure and Performance of Efficient Interpreters».

Switch-диспетчеризация. Компилятор C превращает switch в таблицу переходов, и все опкоды разделяют один косвенный переход. Проблема исторически была в предсказателе: одна точка ветвления, из которой управление уходит в двести разных мест, предсказывалась плохо.

for (;;) {
    switch (*ip++) {                                   /* sp — вершина стека */
        case OP_ADD:  { Value b = *--sp; sp[-1] = sp[-1] + b; break; }
        case OP_LOAD: { *sp++ = frame->slots[*ip++];          break; }
        /* ... ещё две сотни случаев ... */
    }
}

Прямая шитая диспетчеризация (direct threading) через расширение GCC/Clang «метки как значения»: у каждого опкода свой косвенный переход, и предсказателю есть за что зацепиться — переходы образуют историю «после LOAD обычно идёт CONST».

static void *table[] = { &&op_const, &&op_load, &&op_add, /* ... */ };
#define DISPATCH() goto *table[*ip++]

    DISPATCH();                                        /* стартуем цикл */
op_add:
    { Value b = *--sp; sp[-1] = sp[-1] + b; DISPATCH(); }
op_load:
    { *sp++ = frame->slots[*ip++];          DISPATCH(); }

На процессорах 2000-х это давало ускорение до двух раз. Сегодня картина изменилась: Роу, Свами и Сезнек в «Branch Prediction and the Performance of Interpreters — Don’t Trust Folklore» (CGO 2015) показали, что предсказатель ITTAGE в современных ядрах справляется с «толстым» косвенным переходом почти так же хорошо, и разрыв между switch и threading во многих случаях сжался до единиц процентов. Вывод практический: не переписывайте интерпретатор на computed goto, не померив.

Что даёт больше:

• Суперинструкции — склеить частые пары в одну (LOAD + CONST + ADD → ADD_LOCAL_CONST). Убирает диспетчеризации и промежуточные обращения к стеку; генерируется автоматически из профиля, для этого и придумали vmgen.
• Кэширование вершины стека (stack caching) — держать верхний элемент в переменной, которую компилятор C положит в регистр. Дёшево и заметно.
• Специализация по типам — отдельный опкод для «сложить два целых», с проверкой и откатом на общий путь. Это уже мостик к JIT.
• Инлайн-кэши — запоминать результат разрешения имени/метода прямо в теле инструкции. Идея Дойча и Шиффмана из реализации Smalltalk-80 (1984), сегодня — основа V8 и CPython.

CPython 3.11 объединил всё это в «специализирующий адаптивный интерпретатор» (PEP 659): инструкция сначала исполняется в универсальной форме, считает запуски, затем заменяет себя на специализированную версию под увиденные типы, а при промахе откатывается назад. Плюс инлайн-кэши, размещённые прямо в потоке байткода. Итог — около 1.25× на типовых нагрузках без единой строки машинного кода.

Сложность. Исполнение — O(k) по числу исполненных инструкций; интересна константа. Наивная switch-ВМ на C тратит 10–30 машинных инструкций на одну инструкцию байткода, хорошо настроенная — 5–15, а JIT-скомпилированный код — 1–3. Память: O(глубина рекурсии × размер кадра) на стеки плюс O(размер программы) на код и пулы констант. Компиляция AST в байткод — O(n) по узлам дерева, все заплатки переходов O(1).

Представление значений

Динамическому языку нужно уметь класть в один слот и число, и указатель, и nil. Способов три.

Всё — объект в куче (CPython). Даже 2 + 2 — это два PyObject, разыменование, вызов слота типа, аллокация результата. Универсально и медленно: каждая арифметическая операция превращается в поход в память со всеми последствиями для кэша.

Тегированное объединение — структура из тега типа и union. Просто, отлаживаемо, но на 64-битной машине занимает 16 байт из-за выравнивания, то есть вдвое режет плотность стека.

typedef struct { enum { VAL_NIL, VAL_BOOL, VAL_NUM, VAL_OBJ } type;
                 union { bool boolean; double number; Obj* obj; } as; } Value;

NaN-boxing — уложить всё в 8 байт, воспользовавшись тем, что стандарт IEEE 754 резервирует под «не-число» целое семейство битовых комбинаций (порядка 2⁵²). Числа хранятся как есть, всё остальное прячется в неиспользуемые NaN-паттерны.

#define QNAN     ((uint64_t)0x7ffc000000000000)
#define SIGN_BIT ((uint64_t)0x8000000000000000)
#define IS_NUM(v)  (((v) & QNAN) != QNAN)                       // не NaN -> просто double
#define IS_OBJ(v)  (((v) & (QNAN | SIGN_BIT)) == (QNAN | SIGN_BIT))
#define AS_OBJ(v)  ((Obj*)(uintptr_t)((v) & 0x0000FFFFFFFFFFFF)) // 48 бит адреса

Так живут LuaJIT, JavaScriptCore, SpiderMonkey и учебный clox. Плата — привязка к 48-битным адресам (ломается на 5-уровневой пейджинге с 57-битными адресами) и невозможность различить NaN, пришедший из настоящей арифметики. Родственный приём — тегирование указателей по младшим битам: OCaml помечает целые единицей в нулевом бите, V8 держит «маленькие целые» (Smi) в старшей половине слова. Подробнее про машинные представления — в статье про представление данных.

Верификация и безопасность

Байткод, полученный из ненадёжного источника, — это программа, которую вы собираетесь исполнить. Если ВМ доверчива, LOAD 250 в функции с двумя слотами прочитает чужую память, а JMP в середину инструкции сделает из вашего кода что угодно.

Ответ индустрии — верификация при загрузке:

• JVM проверяет типы на стеке и в локальных переменных для каждой точки программы. До Java 6 это делалось выводом с итерацией до неподвижной точки; затем в class-файл добавили StackMapTable — компилятор сам пишет типы на границах базовых блоков, и проверка становится линейной. Спецификация: JVMS, глава 4.10.
• WebAssembly валидируется за один линейный проход именно потому, что управление структурное, а типы явные — см. спецификацию и статью «Bringing the Web up to Speed with WebAssembly».
• EVM не верифицирует типы, зато считает газ: у каждой инструкции есть цена, и исполнение обрывается при исчерпании лимита. Это ответ на проблему остановки в мире, где код исполняют тысячи узлов; подробности — в статье про Ethereum и EVM.

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

Как это устроено в проде

Обратите внимание на закономерность: чем ближе ВМ к роли формата распространения, тем она стековее и проверяемее; чем ближе к роли рантайма — тем регистровее и быстрее. Dalvik — прямая иллюстрация: код приезжает в стековом Java-байткоде, а перед исполнением конвертируется в регистровый.

Структура типичной ВМ в терминах объектов — так это и выглядит в исходниках:

Типичные ошибки

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

Указатель на стек, переживший realloc. В ВМ на C соблазнительно держать Value* top. После роста стека он указывает в никуда. Либо индексы вместо указателей, либо пересчёт всех указателей после роста — третьего нет.

Рекурсия ВМ по нативному стеку. Если CALL реализован как рекурсивный вызов метода интерпретатора, глубина рекурсии гостевой программы ограничена нативным стеком, и переполнение выглядит как аварийное завершение вместо внятной ошибки. Свой стек кадров решает и это, и задачу продолжений/сопрограмм.

Слоты, адресуемые абсолютно. Работает ровно до первого рекурсивного вызова. Всё, что относится к кадру, адресуется через base.

Забытые корни для сборщика мусора. Значение, лежащее во временной переменной интерпретатора, а не на стеке ВМ, невидимо для GC — и может быть собрано прямо посреди операции. Об этом целиком следующая статья.

Байткод без версии формата. Как только байткод сохраняется в файл, он становится форматом, и старые файлы встретятся с новой ВМ. Магическое число плюс версия в заголовке — двадцать минут работы; .pyc и .class устроены именно так.

Семантика, разъехавшаяся между компилятором и ВМ. Деление на ноль, переполнение, сравнение разных типов — если компилятор свернул константы по одним правилам, а ВМ считает по другим, программа даёт разные ответы в зависимости от оптимизаций. Правила пишутся один раз и в одном месте.

Мини-итог

• Виртуальная машина — это ещё один бэкенд компилятора, только целевая архитектура придумана вами: переносимость, компактность, безопасность и простота реализации в обмен на скорость.
• Байткод — формат, а не деталь реализации: пул констант, ширина операндов, escape для больших значений, версия в заголовке, таблица строк для трассировок.
• Стековая машина проще в кодогенерации и компактнее; регистровая исполняет примерно вдвое меньше инструкций ценой более широкой кодировки и распределителя слотов. Наш замер: 218 906 против 120 398 шагов на одной и той же fib(20).
• Кадр описывается тройкой «код, ip, база», аргументы передаются на месте, локальные переменные — это индексы от базы, а не имена.
• Главная статья расходов — диспетчеризация. Порядок действий: сначала слоты вместо словарей, потом суперинструкции и кэширование вершины, потом специализация и инлайн-кэши, и только потом JIT.
• Верификация не роскошь. Даже для собственного байткода проверки границ при загрузке окупаются мгновенно.

Что почитать

• Robert Nystrom, Crafting Interpreters, часть III — лучшее из существующего введение: стековая ВМ на C, NaN-boxing, инлайн-кэши, GC. Бесплатно и целиком онлайн.
• The Java Virtual Machine Specification, главы 2 и 6 — образец того, как документируют систему команд.
• Roberto Ierusalimschy et al., The Implementation of Lua 5.0 — почему Lua перешла на регистровую машину и как устроена её кодировка.
• Yunhe Shi, Kevin Casey, M. Anton Ertl, David Gregg, Virtual Machine Showdown: Stack Versus Registers — главный количественный источник по теме статьи.
• M. Anton Ertl, David Gregg, The Structure and Performance of Efficient Interpreters — откуда берутся проценты в диспетчеризации; там же про суперинструкции.
• Erven Rohou, Bharath Swamy, André Seznec, Branch Prediction and the Performance of Interpreters — Don’t Trust Folklore — почему старые советы про computed goto нужно перепроверять.
• PEP 659: Specializing Adaptive Interpreter и PEP 744: JIT Compilation — как это делают в CPython прямо сейчас.
• James E. Smith, Ravi Nair, Virtual Machines: Versatile Platforms for Systems and Processes — единственная книга, которая честно разбирает и системные, и процессные ВМ.
• Спецификация WebAssembly — современный образец того, как проектируют байткод с нуля с оглядкой на верификацию.
• Связанные статьи портала: структуры данных: стеки и очереди — фундамент стековой машины, как работает процессор — с чего мы срисовываем цикл fetch-decode-execute, автоматы и языки — магазинные автоматы, императивная парадигма — модель вычислений, которую ВМ воплощает буквально, и лямбда-исчисление на практике — абстрактные машины как способ задать семантику.

Что дальше

Наша ВМ умеет считать числа — и ровно поэтому обходится без единого байта кучи. Стоит добавить строки, списки или замыкания, и появится вопрос, который откладывать больше нельзя: кто освобождает память. У ВМ здесь уникальная позиция — она точно знает все корни: стек значений, слоты кадров, пул констант, глобальные переменные. Следующая статья использует это знание: подсчёт ссылок и его беда с циклами, mark-sweep и mark-compact, копирующие и поколенческие сборщики, барьеры записи, инкрементальные и конкурентные алгоритмы — и главный практический вопрос любого рантайма: сколько миллисекунд длится пауза и что с ней делать.

Сборка мусора: подсчёт ссылок, mark-sweep, поколения, паузы