Производительность интерпретатора Python 3.14 с оптимизацией хвостовых вызовов

Примерно месяц назад проект CPython смерджил новую стратегию реализации интерпретатора байт-кода. Первоначальные результаты были очень впечатляющими, продемонстрировав среднее повышение производительности на 10-15% в широком спектре бенчмарков на различных платформах.

К сожалению, как будет показано в этом посте, такой впечатляющий рост производительности оказался вызван в первую очередь непреднамеренным обходом регрессии в LLVM 19. При бенчмаркинге в сравнении с более подходящим базовым случаем (таким как GCC, clang-18 и LLVM 19 с флагами настройки), рост производительности снижается примерно до 1-5%, в зависимости от конкретной конфигурации.

Когда было заявлено о выпуске интерпретатора с оптимизацией хвостовых вызовов, меня удивили и впечатлили улучшения производительности, но в то же время я был сбит с толку: я не специалист, но поверхностно знаком с архитектурой современных CPU, компиляторов и интерпретаторов, поэтому не мог объяснить причин эффективности этих изменений. Меня охватило любопытство (и, возможно, одержимость): всё отчёты в этом посте стали результатом компилирования, бенчмаркинга и дизассемблирования десятков различных двоичных файлов Python.

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

Кроме того, до моего эксперимента влияние регрессии LLVM, похоже, было мало изучено (и на момент публикации поста баг ещё не был устранён); таким образом, альтернативное решение (без этого результата работы), вероятно, было бы на 10-15% медленнее для сборок, использующих clang-19 или более новые версии. Например, Саймон Уиллисон воссоздал ускорение на 10% в реальных условиях (по сравнению с Python 3.13), использовав сборки из python-build-standalone.

Результаты замеров производительности

Ниже представлены мои результаты. Я выполнил бенчмаркинг множества сборок интерпретатора CPython, использовав множество разных компиляторов и разных опций конфигурации на двух машинах: на сервере Intel (Raptor Lake i5-13500, поддержкой которого я занимаюсь в Hetzner) и на моём Apple M1 Macbook Air. Вы сами можете воспроизвести эти сборки, воспользовавшись моей конфигурацией nix, которая оказалась необходима для одновременного управления таким большим количеством параметров.

Все сборки используют LTO и PGO. Выбраны следующие конфигурации:

• clang18: сборка выполнена при помощи Clang 18.1.8 с применением computed goto.
• gcc (только Intel): сборка выполнена при помощи GCC 14.2.1 с применением computed goto.
• clang19: сборка выполнена при помощи Clang 19.1.7 с использованием computed goto.
• clang19.tc: сборка выполнена при помощи Clang 19.1.7 с использованием нового интерпретатора с оптимизацией хвостовых вызовов.
• clang19.taildup: сборка выполнена при помощи Clang 19.1.7, computed goto и некоторых флагов настройки -mllvm, что позволило обойти регрессию.

В качестве базового примера для сравнения я использовал clang18, а итоговые «средние» результаты получены при помощи pypeformance/pyperf compare_to. Полные файлы вывода и отчёты можно найти на github.

Обратите внимание, что интерпретатор с оптимизацией хвостовых вызовов всё равно демонстрирует рост производительности по сравнению с clang-18, но он гораздо менее существенный, чем замедление от перехода на clang-19. Кроме того, на некоторых других платформах команда разработчиков Python замеряла более высокий рост производительности, чем я (даже с учётом бага).

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

Регрессия LLVM

Краткое введение

Классический интерпретатор байт-кода состоит из оператора switch внутри цикла while и выглядит примерно так:

while (true) {
  opcode_t this_op = bytecode[pc++];
  switch (this_op) {
    case OP_IMM: {
      // записываем непосредственное значение в стек
      break;
    }
    case OP_ADD: {
      // обрабатываем сложение
      break;
    }
    // etc
  }
}

Большинство компиляторов компилирует switch в таблицу переходов — они генерируют таблицу, содержащую адрес каждого блока case OP_xxx, индексируют её опкодом и выполняют косвенный переход.

Давно было известно, что можно ускорить подобный интерпретатор байт-кода, реплицировав dispatch таблицы переходов в тело каждого опкода. То есть вместо того, чтобы каждый опкод заканчивался jmp loop_top, он должен содержать отдельный экземпляр логики «декодируй следующую команду и индекс через таблицу переходов».

Современные компиляторы C поддерживают получение адреса меток с последующим использованием этих меток в «computed goto» для реализации этого паттерна. Поэтому многие современные интерпретаторы байт-кода, включая CPython (до проведения работ с хвостовыми вызовами), используют цикл интерпретатора, который выглядит примерно так:

static void *opcode_table[256] = {
    [OP_IMM] = &&TARGET_IMM,
    [OP_ADD] = &&TARGET_ADD,
    // и так далее
};

#define DISPATCH() goto *opcode_table[bytecode[pc++]]

DISPATCH();

TARGET_IMM: {
    // записываем непосредственное значение в стек
    DISPATCH();
}
TARGET_ADD: {
    // обрабатываем сложение
    DISPATCH();
}

Computed goto в LLVM

Как оказалось, из соображений производительности (производительности компилятора, а не сгенерированного кода) Clang и LLVM сливают все goto этом коде в единую команду LLVM indirectbr, к которой выполняет переход каждый опкод. То есть компилятор берёт всю нашу упорную работу нами и намеренно переписывает её в граф потока управления, который, по сути, выглядит так же, как интерпретатор на основе switch!

Затем при генерации кода LLVM выполняет «хвостовую дупликацию» и копирует ветвление обратно в каждую точку, восстанавливая исходное предназначение. Эти манипуляции в общем виде задокументированы в старом посте об LLVM, в котором рассказывается о новой реализации.

Регрессия LLVM 19

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

Чтобы избежать в некоторых случаях катастрофических замедлений (или использования огромных объёмов памяти), LLVM 19 реализовал определённые ограничения на проход хвостовой дупликации, заставляя его выполнять выход, если дупликация увеличит размер IR выше заданного предела.

К сожалению, в CPython эти ограничения привели к тому, что в Clang все dispatch-переходы остаются объединёнными, что полностью нивелирует весь смысл реализации на основе computed goto! Этот баг впервые был обнаружен другой реализацией языка со схожим циклом интерпретатора, но ещё никто не наблюдал (насколько я понимаю) того, что он влияет на CPython.

Мы можем не только ощутить влияние бага по снижению производительности, но и непосредственно увидеть его, дизассемблировав объектный код и подсчитав количество косвенных переходов:

$ objdump -S --disassemble=_PyEval_EvalFrameDefault ${clang18}/bin/python3.14 | 
  egrep -c 'jmps+*'
332

$ objdump -S --disassemble=_PyEval_EvalFrameDefault ${clang19}/bin/python3.14 | 
  egrep -c 'jmps+*'
3

▍ Другие странности

Я полностью уверен, что эту регрессию вызвала логика дупликации хвостовых вызовов: если устранить его, то производительность вернётся к уровню clang-18. Однако я не могу полностью объяснить причины величины регрессии.

В прошлом считалось, что оптимизация репликации dispatch байт-кода в каждый опкод ускоряет интерпретаторы на величины от 20% до 100%. Однако более современные исследования показывают, что на современных процессорах с улучшенным прогнозированием ветвления повышение скорости оказывается гораздо более скромным: порядка 2-4%.

Мы можем проверить эти значения (2-4%) на практике, потому что Python благодаря опции конфигурации по-прежнему поддерживает «старомодный» интерпретатор, использующий один оператор switch. Вот, что мы увидим, если проведём бенчмарк этого интерпретатора (в таблице ниже «.nocg» означает «no computed goto»):

Обратите внимание, что clang19.nocg всего на 2% медленнее clang18, хотя базовая сборка clang19 медленнее на 9%! Я интерпретирую эти два процента как более точную оценку затрат/выигрышей только одной дупликации dispatch, а второй результат я не вполне понимаю.

▍ Нужны ли нам computed goto?

Я не говорил о бенчмарке clang19.nocg, который, по утверждениям, быстрее, чем clang19. На этом этапе я обнаружил ещё один (очень забавный) поворот этой истории.

Выше я говорил, что Clang и LLVM:

1. Компилируют switch в таблицу переходов и косвенный переход, очень схожий с тем, который мы создаём вручную при помощи computed goto.
2. Компилирует computed goto в граф потока управления, который очень похож на классический граф switch, являющийся одним экземпляром dispatch опкодов, и
3. Могут обратить преобразование во время генерации кода, чтобы дуплицировать dispatch.

Если объединить всё это вместе, то у вас может возникнуть вопрос: «А не можем мы просто начать с интерпретатора на основе switch, чтобы компилятор выполнял всю хвостовую дупликацию, и получить те же преимущества?»

И оказалось, что это действительно возможно.

clang-18 (или clang-19 с соответствующими флагами) в случае использования «классического» интерпретатора на основе switch на самом деле всё равно дуплицирует логику dispatch в каждое тело каждого опкода. Вот ещё одна таблица, в которой показаны те же сборки с количеством косвенных переходов на основе предыдущего теста objdump | grep:

Таким образом, весь интерпретатор с computed goto оказывается абсолютно ненужной сложностью (по крайней мере, для современного Clang). Компилятор вполне сам может выполнять ту же трансформацию и (очевидно) computed goto недостаточно, чтобы её гарантировать!

Однако я протестировал GCC, и этот компилятор (по крайней мере, версии 14.2.1) не воссоздаёт switch, но реализует желаемое поведение при использовании computed goto. Так что, по крайней мере, в этом случае мы наблюдаем ожидаемое поведение.

Исправление

Устраняющий регрессию пул-реквест LLVM 114990 был смерджен вскоре после публикации моего поста. Мне удалось выполнить бенчмарк до мерджа и я подтверждаю, что он восстанавливает ожидаемую производительность.

Для релизов до этого исправления вызвавший регрессию PR добавил настраиваемую опцию, позволяющую выбирать пороговое значение, после которого хвостовая дупликация будет прекращаться. Мы можем восстановить схожее поведение в clang-19, просто установив в качестве предела очень большое число¹.

Рассуждения

С готовностью признаю, что меня увлекла эта тема и что я залез в неё глубже, чем это было необходимо на самом деле. Тем не менее, я считаю, что из этого можно извлечь множество интересных уроков и наблюдений, которые вполне применимы к разработке ПО и обеспечению производительности в целом. Ниже я попытаюсь порассуждать о некоторых из них.

О бенчмаркинге

При оптимизации системы мы в общем случае создаём некий набор бенчмарков и методологию бенчмаркинга, а затем проверяем при помощи этих бенчмарков предложенные изменения.

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

Бенчмарки интерпретатора с оптимизацией хвостовых вызовов показали ускорение на 10-15% по сравнению со старым интерпретатором на основе computed goto. Эти бенчмарки были точными в том смысле, что они точно (насколько я знаю) измеряли разницу производительности между этими сборками. Однако чтобы обобщить эти конкретные примеры данных в заявление «интерпретатор с оптимизацией хвостовых вызовов на 10-15% быстрее, чем интерпретатор с computed goto» или даже «интерпретатор с оптимизацией хвостовых вызовов ускорит Python на 10-15% для наших пользователей» мы должны добавить больше допущений о мире. В данном случае ситуация оказалась сложнее, и в более широком применении эти заявления оказались ложными.

(Ещё раз повторюсь, что я не хочу винить разработчиков Python! Их работа сложна, и в ней можно ошибиться или прийти к неправильным выводам миллионами разных способов. Чтобы глубже разобраться в проблеме, мне пришлось примерно три недели заниматься активным бенчмаркингом и экспериментами. Я просто хочу сказать, что это очень обширная задача!)

▍ Базовые примеры для сравнения

Этот пример подчёркивает наличие ещё проблемы, одной часто встречающейся не только в сфере производительности ПО, но и в других: с какими исходными данными мы выполняем сравнение?

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

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

Обычно мы сравниваем с «лучшим на данный момент решением». Но иногда сделать это бывает сложно! Даже если вы теоретически понимаете актуальную методику, вы можете и не быть специалистом по применению её на практике. В случае ПО для этого, например, может понадобиться настраивать операционную систему, опции компилятора или другие флаги. Для лучшего на данный момент решения могут быть опубликованы бенчмарки, но они не всегда релевантны для вас; например, они могли быть опубликованы несколько лет назад на старом оборудовании, поэтому вы не можете сравнивать их напрямую со своими результатами. Или, возможно, его тесты проводились в масштабах, недостижимых для вас.

Сейчас я занимаюсь машинным обучением в Anthropic, и мы постоянно сталкиваемся с такой ситуацией в статьях по ML. Когда в статье утверждается о каком-то алгоритмическом улучшении или другом прогрессе, то наши исследователи обычно первым делом задают не вопрос «Что они сделали?», а «С какими исходными данными они сравнивают?». Легко получить впечатляющие результаты, если сравнивать с плохо настроенными исходными данными, и это наблюдение часто объясняет на удивление большую часть предполагаемых улучшений.

О разработке ПО

Ещё одним важным для меня моментом стала сложность и взаимосвязанность наших программных систем, их стремительное развитие и трудности с выявлением всех важных элементов.

Если бы месяц назад меня попросили оценить вероятность того, что релиз LLVM вызовет регрессию производительности на 10% в CPython, которую никто не заметит в течение пяти месяцев, то я бы сказал, что это крайне маловероятно! Оба этих проекта активно используются, разработчики обоих сильно заботятся о производительности и кто-то «уж точно» протестировал бы их и заметил проблему.

И, вероятно, эта конкретная ситуация действительно была крайне маловероятна! Однако существует так много различных программных проектов, активно развивающихся и зависимых от множества других проектов, что практически неизбежным становится постоянное появление таких регрессий.

▍ Про оптимизирующие компиляторы

Сага об интерпретаторе с computed goto иллюстрирует постоянные трения и неразрешённые вопросы об оптимизаторах и оптимизирующих компиляторах, на которые у нас как у отрасли в целом нет сложившихся ответов.

В общем случае мы ожидаем, что компиляторы будут соответствовать намерениям программиста и компилировать код так, чтобы в нём отражались намерения программиста.

Но в то же время мы ожидаем, что компиляторы будут оптимизировать наш код, преобразовывая его потенциально сложными и малопонятными способами для ускорения его работы.

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

Обычно компиляторы лишь обещают генерировать код, с «тем же поведением», что и написанный нами код; при этом они максимально стремятся обеспечить высокую производительность поверх этой гарантии.

И так мы оказываемся в этом странном мире, где clang-19 компилирует интерпретатор с computed goto «корректно» (в том смысле, что получившийся двоичный файл генерирует все ожидаемые нами значения), но в то же время он создаёт вывод, полностью противоречащий нашему стремлению к оптимизации. Более того, мы также видим другие версии компилятора, применяющие оптимизации к «наивному» интерпретатору на основе switch(), реализующему ту же оптимизацию, которую мы «намеревались» выполнить, переписав исходный код.

В ретроспективе можно решить, что интерпретатор с computed goto на уровне исходного кода и «воссоздание dispatch на уровне машинного кода» оказываются почти ортогональными понятиями! Мы видели примеры каждого экземпляра получившейся матрицы 2x2! Так как все эти двоичные файлы python при выполнении вычисляют те же значения, наши современные инструменты, по сути, не могут согласованным образом говорить о различиях между ними.

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

Я надеюсь, такой формат окажется гораздо более надёжным стилем написания требовательного к производительности кода, особенно в процессе эволюции компиляторов. Я ожидаю дальнейших экспериментов в этой категории.

Если конкретнее, то мне любопытно, можно ли будет заменить интерпретатор с computed goto на что-то типа атрибута (гипотетического) [[clang::musttailduplicate]] в цикле while интерпретатора. Я недостаточно специалист во всех соответствующих IR и проходах, чтобы утверждать это с уверенностью, но, возможно, кто-то, имеющий больше опыта в этой сфере, сможет оценить реализуемость этого.

Ещё одно примечание: о nix

Закончить я хотел рассказом о том, насколько полезен был nix для этого проекта. Примерно в течение года я экспериментировал с nix и NixOS для моей личной инфраструктуры, но в этом расследовании они практически спасли мою жизнь.

В экспериментах я собрал и проверил бенчмарками десятки различных интерпретаторов Python с четырьмя разными компиляторами (gcc, clang-18, clang-19 и clang-20), а также использовал бесчисленные комбинации флагов компиляторов. Ручное управление всем этим свело бы меня с ума; к тому же я точно совершил бы множество ошибок в сопоставлении компиляторов и флагов со сборками.

Благодаря nix я смог не запутаться во всех этих параллельных версиях и собирать их воспроизводимым «герметичным» образом. Я смог написать короткие абстракции, сильно упростившие их определение, и с абсолютной уверенностью знал, откуда взялась каждая конкретная сборка в моём хранилище nix, какими компиляторами и с какими флагами она создавалась. Я потратил лишь немного времени на написание вспомогательных функций, но благодаря этому моя матрица сборок стала на удивление краткой; можете оценить:

{
    base = callPackage buildPython { python3 = python313; };
    optimized = withOptimizations base;
    optLTO = withLTO optimized;

    clang18 = withLLVM llvmPackages_18 optLTO;
    clang19 = withLLVM llvmPackages_19 optLTO;
    clang20 = withLLVM llvmPackages_20 optLTO;

    clang18nozero = noZeroCallUsed clang18;
    clang18nocg = withoutCG clang18;

    clang19taildup = withTailDup clang19;
}

Мне даже удалось собрать специальную версию LLVM (с патчем устранения бага) и создавать сборки Python при помощи этого компилятора. И для этого понадобилось всего десять строк кода.

Тем не менее, нельзя сказать, что всё прошло идеально. Например, nix является «странным» в использовании ПО, и на то у него есть причины. Я опасаюсь, что эта странность неосознаваемым мной образом частично повлияла на мои бенчмарки или выводы. Например, ещё в самом начале исследования я обнаружил, что nix (по умолчанию) собирает проекты, используя hardening-флаги, которые непропорционально влияют на интерпретатор с оптимизацией хвостовых вызовов. Эту проблему я устранил, но есть ли другие?

Кроме того, Nix чрезвычайно хорошо расширяется и настраивается, но разбираться, как выполнить конкретную настройку, может быть очень сложно; для этого может потребоваться множество проб, ошибок и изучения исходников. В конечном итоге моя пропатченная сборка LLVM оказалась достаточно короткой и чистой, но для этого мне пришлось изучить большой объём исходного кода nixpkgs, смешивать и сопоставлять два плохо задокументированных механизма расширяемости (extend и overrideAttrs — не путать с override, используемым в другом месте), а также создать одну неудачную попытку, которая успешно пропатчила libllvm, но молча собрала новый clang для непропатченной версии.

Тем не менее, nix оказал мне огромную помощь и в конечном итоге он сильно упростил этот процесс исследования и отладки множества разных версиий. Не могу представить, что на это был бы способен какой-то другой инструмент.

Примечания

1. Стоит отметить, что включить эту опцию при использовании LTO достаточно сложно. Хвостовая дупликация происходит на этапе генерации кода, а в случае LTO-сборок генерация кода обычно происходит во время компоновки, а не компиляции. Таким образом, нам нужно гарантировать, что флаг передаётся lld, а не просто компилятору. Мне удалось заставить работать эту систему, настроив во время ./configure следующие переменные Python:

   ./configure [другие флаги] 
     "OPT=-g -O3 -Wall -mllvm -tail-dup-pred-size=5000" 
     "LDFLAGS=-fuse-ld=lld -Wl,-mllvm -Wl,-tail-dup-pred-size=5000"