Оптимизация хвостовых вызовов (tail-call optimization, TCO) в языке C не существовала всегда. Соглашение о вызовах в C традиционно устроено так, что вызываемая функция (callee) не удаляет со стека данные, которые туда поместил вызывающий код (caller). Вызывающая сторона могла видеть объявление вида int f();, при этом реальный вызов мог передавать n>0 аргументов, а сама функция принимать m≤n параметров. Такая схема не сработала бы, если бы вызываемая функция сама очищала аргументы со стека.
Поэтому именно вызывающий код должен был удалять аргументы между вызовом и последующим возвратом — это превращало вызов в обычный, а не хвостовой.
В 1994 году, при изучении тогдашних компиляторов C, оптимизация хвостовых вызовов для сценариев, подобных описанным в оригинальной статье, отсутствовала. В 2001 году Марк Пробст реализовал оптимизацию хвостовых вызовов в GCC, используя отдельное соглашение о вызовах. В разделе 6.4 своей работы он перечисляет ограничения существовавшей на тот момент реализации TCO в GCC, в том числе: «Она не умеет обрабатывать индиректные вызовы» — а именно такие вызовы используются в хвостовых вызовах для диспетчеризации интерпретатора.
С тех пор к этому вопросу разработчик Gforth не возвращался — механизм goto * в GCC был достаточно хорош (по большей части), и не было особых причин полагать, что поддержка хвостовых вызовов в GCC изменилась, хотя в одном из release notes упоминались sibcalls, и мысль проверить это возникала неоднократно.
В прошлом году была прочитана статья «Copy-and-Patch Compilation» авторов Xu и Kjolstad, где используется оптимизация хвостовых вызовов. После знакомства с этой работой были проведены собственные тесты — проверялось, способны ли gcc и clang выполнять TCO для тех видов хвостовых вызовов, что показаны в оригинальной статье. Оказалось, что работает. При этом Xu и Kjolstad сообщают об использовании 100 000 фрагментов кода, тогда как в Gforth ограничиваются менее чем 2000 (для инструкций виртуальной машины, вариаций stack caching, статических суперинструкций и так далее). Возможность работать с 100 000 фрагментов открыла бы доступ к техникам, которые требуют слишком большого количества различных фрагментов кода, чтобы быть применимыми в системе на основе goto *.
В Gforth до внедрения этой техники руки пока не дошли, так что сообщество Python первым добралось до этой оптимизации — и заслуживает поздравлений.
Комментарии читателей
lafp поделился опытом реализации игрушечного интерпретатора для варианта языка Forth, который использует хвостовые вызовы для диспетчеризации инструкций:
Для меня основной выигрыш заключался в том, что все встроенные функции стали вести себя как сами инструкции, а не как отдельная инструкция «вызвать встроенную функцию». Также реализована поддержка нескольких десятков суперинструкций, что заметно помогло, поскольку они не сильно отличаются от всего остального. Производительность вполне достойная, но потребуется ещё немного поработать над оптимизатором, чтобы достичь нужного уровня (в перспективе хочется запустить это на маленьком компьютере, предоставить доступ к интерпретатору через браузер и позволить людям писать код, который будет управлять светодиодной матрицей — что-то похожее на этот проект, но в меньшем масштабе).
Код доступен на GitHub — это вариант языка Forth Haiku, позволяющий создавать художественные произведения из небольших фрагментов кода на Forth, что-то вроде ShaderToy, но для GLSL.
Robbepop рассказал о собственных бенчмарках интерпретатора WebAssembly:
Сегодня заново прогнал бенчмарки готовящейся версии Wasmi (интерпретатора WebAssembly). Он активно использует прямую диспетчеризацию по потоку (direct-threaded code) на основе хвостовых вызовов для диспетчеризации инструкций, но может быть настроен на использование индиректной диспетчеризации или даже старой доброй диспетчеризации через loop-switch. Бенчмарки показывают огромную разницу в производительности между switch-loop и threaded-code подходами — именно поэтому все современные быстрые интерпретаторы Wasm, такие как Wasmi, Wasm3 и Stitch, используют хвостовые вызовы. Для меня нативные хвостовые вызовы — одна из основ любого настоящего системного языка программирования.
Дополнительные материалы и ссылки от Robbepop: