Як байткодова VM на Rust обігнала CPython 3.14

Деревообхідний інтерпретатор risp обчислював fib(30) за 1682 мс. Його байткодова VM робить це за 95 мс — а на циклах та арифметиці вона прямо обходить CPython 3.14. Жодна частина цього не з’явилася від одного хитрого трюку. Це результат прибирання одного вузького місця за раз, щоб дати проявитися наступному. Ось уся ця дуга, у справжньому коді:

#	зміна	fib	tailsum	arith	що прибрано
0	деревообхідний інтерпретатор (baseline)	1682 ms	760 ms	2459 ms	—
1	байткодова VM (наївна)	270 ms	90 ms	—	повторний аналіз AST + середовище з хешуванням рядків
2	вбудована цілочисельна арифметика	235 ms	78 ms	—	загальна диспетчеризація вбудованих для + - < =
4	кадр, кешований у регістрах	170 ms	60 ms	—	індексація стеку кадрів + інкремент Rc на виклик
8	гарячий шлях без перевірок	108 ms	35 ms	94 ms	гілки перевірки меж на операцію
10	самохвостовий виклик на місці	106 ms	25 ms	72 ms	налаштування кадру на ітерацію циклу
11	локальні на стеку	95 ms	28 ms	78 ms	вектор кадру на кожен виклик
—	CPython 3.14	61 ms	31 ms	96 ms

Компілюємо один раз: змінні стають індексами масиву

Деревообхідний інтерпретатор щоразу заново виводить значення кожного вузла, коли його запускає: чи є голова спеціальною формою? макросом? Потім він виділяє вектор для операндів і рекурсивно спускається. Читання змінної означає хешування її імені та зондування HashMap на кожному кадрі області видимості вгору ланцюгом. Усе це є функцією тексту програми, а не значень під час виконання, тож це можна зробити один раз. Компілятор розв’язує кожне посилання на змінну у фіксований слот під час компіляції:

fn resolve(&mut self, name: &Rc<str>) -> Resolved {
    let last = self.fns.len() - 1;
    // `rposition`, not `position`: a shadowing `let` sits at a HIGHER slot,
    // so the innermost binding must win.
    if let Some(i) = self.fns[last].slots.iter().rposition(|s| s == name) {
        return Resolved::Local(i as u32);
    }
    for f in &self.fns[..last] {
        if f.slots.iter().any(|s| s == name) { return Resolved::Capture; }
    }
    Resolved::Global(self.g.intern(name))
}

Локальне посилання тоді компілюється в Op::LoadLocal(i), і під час виконання це єдине читання stack[base + i], індекс масиву, який процесор може тримати в регістрі. Жодного хешування, жодного зондування мапи. Це найбільший окремий виграш — fib впав з 1682 мс до 270 мс за один крок — і саме тому LOAD_FAST у CPython (теж індекс масиву) є його швидким опкодом.

Тримаємо цілі без обгортки

Це структурна причина, чому VM на Rust взагалі може обійти CPython. Компілятор генерує спеціалізовані опкоди для двоаргументної арифметики замість загального виклику:

let fast = match &**op {
    "+" => Some(Op::Add), "-" => Some(Op::Sub), "*" => Some(Op::Mul),
    "<" => Some(Op::Lt),  ">" => Some(Op::Gt),  "=" => Some(Op::NumEq),
    // ... <= >=
    _ => None,
};
if let Some(fop) = fast
    && !self.redefined_ops.contains(&**op)        // (def + ...) suppresses inlining
    && matches!(self.resolve(op), Resolved::Global(_))
{
    self.compile(&parts[1], false)?;
    self.compile(&parts[2], false)?;
    self.emit(fop);
    return Ok(());
}

Швидкий шлях VM обробляє випадок (Int, Int) за кілька інструкцій і делегує все інше справжній вбудованій функції, тож семантика (включно з пасткою переповнення) лишається ідентичною:

fn bin_arith(
    stack: &mut Vec<Value>,
    int_fast: fn(i64, i64) -> Option<i64>,
    builtin: fn(&[Value]) -> RispResult,
) -> Result<(), RispError> {
    // SAFETY: a binary op is emitted only after its two operands are pushed.
    let b = unsafe { stack.pop().unwrap_unchecked() };
    let a = unsafe { stack.pop().unwrap_unchecked() };
    if let (Value::Int(x), Value::Int(y)) = (&a, &b)
        && let Some(z) = int_fast(*x, *y)
    {
        stack.push(Value::Int(z));
        return Ok(());
    }
    let r = builtin(&[a, b])?;
    stack.push(r);
    Ok(())
}
// dispatch: Op::Add => bin_arith(&mut stack, i64::checked_add, b_add)?,

Value::Int(i64) лежить вбудовано на стеку: без вказівника на купу, без лічильника посилань. Швидкий шлях зіставляє два цілі, викликає i64::checked_add (add плюс перевірка переповнення) і кладе результат, жодного разу не торкаючись алокатора. CPython, навпаки, виділяє в купі та веде лічильник посилань для об’єкта PyLong на кожен проміжний арифметичний результат, навіть для 1 + 1. Ось чому саме на арифметично насиченому циклі risp виграє з найбільшим відривом. А сканування redefined_ops тримає це чесним: якщо програма колись робить (def + …), + прибирається з вбудованого набору і спрямовується звичайним шляхом виклику, тож перевизначення оператора все одно працює.

Гарячий цикл: регістри та індексація без перевірок

Щойно виділення пам’яті та пошуки зникли, залишком стала сама машинерія диспетчеризації. VM тримає активний кадр повністю в локальних змінних (closure, ip, base, cells), тож призупинені викликачі живуть у Vec, тоді як вказівник інструкцій робочого кадру — це просто usize у регістрі. А на шляхах, де компілятор гарантує валідність індексу, вона пропускає перевірку меж:

loop {
    // SAFETY: every function ends in `Return` and all jumps target valid indices,
    // so `ip` is always in range. The VM<->tree-walker differential tests guard this.
    let op = unsafe { *closure.func.code.get_unchecked(ip) };
    ip += 1;
    match op {
        Op::Const(i) => {
            let v = unsafe { closure.func.consts.get_unchecked(i as usize) }.clone();
            stack.push(v);
        }
        Op::LoadLocal(i) => {
            // SAFETY: base + i indexes this frame's locals; i < n_slots (compiler).
            let v = unsafe { stack.get_unchecked(base + i as usize) }.clone();
            stack.push(v);
        }
        // ...
    }
}

Кожна прибрана перевірка — це порівняння-з-розгалуженням, яке процесор виконував десятки мільйонів разів. На арифметичному циклі це сотні мільйонів усунутих гілок, і arith пройшов 129 → 94 мс. Немає й вектора локальних на кожен виклик: локальні живуть прямо на стеку операндів у [base .. base + n_slots], тож уже обчислені аргументи виклику просто стають локальними викликаної функції на місці. unsafe — це реальний компроміс, оскільки помилка компілятора тепер могла б спричинити UB, і саме тому ці доступи є найбільш ретельно протестованим кодом у проєкті (докладніше нижче).

Самохвостовий виклик на місці — вирішальний виграш на циклах

Хвостовий цикл на кшталт (loop (- n 1) (+ acc n)) усе ще робив повне перемикання кадру на кожній ітерації. Виправлення виявляє поширений випадок, функцію, що хвостово викликає саму себе, і перезаписує власні локальні замість цього:

Op::TailCall(argc) => {
    // ... resolve callable ...
    Value::Compiled(c) => {
        let f = &c.func;
        check_arity(f, argc)?;
        // Shift the (already-evaluated) args down onto `base` — the TCO.
        for i in 0..argc {
            let v = std::mem::replace(&mut stack[callee + 1 + i], Value::Nil);
            stack[base + i] = v;
        }
        stack.truncate(base + argc);
        stack.resize(base + f.n_slots, Value::Nil);
        // A self-recursive loop keeps the same closure and (empty) cells —
        // skip that register churn. `n_cells == 0` is load-bearing.
        if !(Rc::ptr_eq(&c, &closure) && f.n_cells == 0) {
            cells = make_cells(f.n_cells);
            closure = c;
        }
        ip = 0;   // jump to the top
    }
}

Три перевірки роблять це коректним, і всі три заслуговують свого місця. Rc::ptr_eq(&c, &closure) гарантує, що це та сама активація хвостово викликає сама себе, а не взаємна рекурсія між двома замиканнями з одного шаблону. f.n_cells == 0 гарантує, що жодне внутрішнє замикання не захопило локальні цього кадру; якщо щось захопило, повторне використання слотів змусило б дві ітерації розділяти одне зв’язування, тож код провалюється далі, щоб виділити свіжі комірки. А check_arity виконується безумовно. Коли перевірки проходять, хвостово-рекурсивний цикл на Lisp стає тим, чим він по суті є, машинним циклом: записуємо нові локальні, переходимо на ip = 0. Це вивело tailsum до 25 мс (попереду CPython-ових 30) і arith до 72 мс (попереду CPython-ових 96).

Під захистом другого інтерпретатора

Кожен блок unsafe вище називає інваріант, що його забезпечує компілятор, і risp не просто стверджує ці інваріанти, він їх тестує. Вивід VM тримається байт-у-байт ідентичним до виводу деревообхідного інтерпретатора завдяки диференційним тестам: та сама програма запускається на обох рушіях, і результати мають збігатися точно. Якби помилка компілятора колись згенерувала індекс поза діапазоном, тест зловив би це як хибне значення раніше, ніж воно могло б стати невизначеною поведінкою в реальних умовах. Компілятор навіть відкладає помилку некоректної, але недосяжної гілки cond на час виконання через Op::Raise, тож VM падає з помилкою точно в той момент і з тим самим повідомленням, що й деревообхідний інтерпретатор. unsafe спирається на простіший інтерпретатор, який ніколи не змінювався.

Єдина форма, яку вона не змогла виграти

Після одинадцяти кроків VM risp обходить CPython на sum (28 мс проти 31), арифметичному циклі (78 проти 96) та диспетчерному циклі, насиченому cond/let (203 проти 208), але відстає у 1.55× на fib з інтенсивними викликами (95 проти 61). Рекурсія fib нехвостова (два виклики живлять +), тож вона ніколи не потрапляє на дешевий шлях самохвостового виклику й платить повну вартість виклику ~2.7М разів, проти спеціалізованого, побудованого на computed-goto вбудованого шляху виклику в CPython. Жодне шліфування портативного байткодового циклу з диспетчеризацією через match не змогло б обійти нативний код на чистій рекурсії. Тож наступний крок припинив інтерпретувати й почав генерувати машинний код, скоротивши розрив на порядок.