Джимми Остлер экспериментировал с tail-call интерпретаторами в Rust и поделился результатами. Его вдохновил пост о разных стилях диспетчеризации в виртуальных машинах на Scala, написанный Ноэлем. Остлер решил перенести эти подходы в Rust и замерить, как они влияют на производительность.
Tail-call — это приём, при котором компилятор превращает рекурсивный вызов в прыжок, не выделяя новый стековый кадр. В Rust за это отвечает нестабильная фича explicit_tail_calls с ключевым словом become.
Сначала Остлер собрал простую стековую машину с пятью инструкциями: Lit, Add, Sub, Mul, Div. Для неё он сделал четыре варианта диспетчеризации. Switch dispatch — обычный цикл с match по массиву байткода. Subroutine dispatch — каждая инструкция становится объектом, реализующим трейт Fn, и вызывается через динамическую диспетчеризацию. Indirect dispatch — операции сами вызывают общую функцию dispatch, а не возвращаются в цикл. Direct dispatch — каждая операция после выполнения сразу вызывает следующую через массив обработчиков. В первых вариантах Остлер использовал static mut и unsafe, но предупредил, что так писать не стоит.
Замеры на его машине показали: direct — 24.59 ns/iter, indirect — 55.32, subroutine — 79.93, switch — 59.39. Direct оказался самым быстрым, потому что полностью использует tail-call. Правда, автор предупреждает: цифры маленькие, и компилятор мог оптимизировать слишком агрессивно, зная все инструкции заранее.
Затем Остлер перешёл к более реалистичной регистровой машине для своего проекта ternary. Это 16-битная машина с 16 регистрами и инструкциями Halt, Add, Sub, Mul, Div, Bgt, Bleq. Инструкция кодируется в 16 бит: поле IMM, два регистра и код операции. Для этой машины он повторил все четыре техники. Switch dispatch — цикл с декодированием. Subroutine dispatch — статический массив функций-обработчиков. Indirect dispatch — взаимные tail-call между dispatch и обработчиками. Direct dispatch — обработчики сами вызывают следующий по массиву HANDLERS.
В этом варианте Остлер отказался от static mut и unsafe, спрятав состояние в структуру Machine. Он отметил, что indirect и direct упрощают сложный контроль потока, включая переходы. Бенчмарков для регистровой машины в статье нет, но описание техник полностью повторяет предыдущий эксперимент.