Вызовы функций в Python по прежнему медленные? Анализ последних оптимизаций в CPython

в 16:00, , рубрики: python, производительность

Я наткнулся на пост в X/Twitter, где Pritam обнаружил, что его решение на Leetcode работало медленнее, когда он использовал встроенную функцию min, производительность улучшилась, когда он реализовал min в своем коде на Python.

Вызовы функций в Python по прежнему медленные? Анализ последних оптимизаций в CPython - 1

Это правда, что вызовы функций могут быть затратными, и они, как известно, еще более затратны в интерпретируемых языках, таких как Python. Стандартная рекомендация — использовать встраивание функций, если они являются частью узкого места.

Автор на этом скриншоте использовал Python 2, который на данный момент уже стал древностью. За последние 10 лет Python 3 получил множество релизов, и последние версии были нацелены на улучшение производительности языка. Так действительно ли вызовы функций по‑прежнему так сильно влияют на производительность в Python?

Мне стало интересно, и я написал три микро‑бенчмарка, чтобы проверить три кейса:

  • Эффект от вызова встроенной функции в цикле

  • Эффект от вызова функции Python в цикле

  • Эффект от встраивания функции в цикле

Как и ожидалось, результаты показывают, что последние релизы значительно улучшили производительность CPython во всех трех кейсах.

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

Бенчмарк 1: Проверка скорости выполнения простых инструкций в цикле

Начнем с первого бенчмарка, в котором мы выполняем простые вычисления внутри цикла, например, вычисляем минимум из списка значений. Код приведен ниже. Он использует цикл while вместо for, так как в коде из поста в Twitter использовался цикл while, и я хотел сохранить его.

def benchmark1(heights):
    a = 1
    b = len(heights) - 1
    min_height = heights[0]
    while a < b:
        if heights[a] < min_height:
            min_height = heights[a]
        a += 1

    return min_height

Ниже приведены показатели производительности для первого бенчмарка в последних версиях CPython:

Время выполнения вычисления минимума из списка значений в цикле без вызова каких‑либо функций.

Время выполнения вычисления минимума из списка значений в цикле без вызова каких‑либо функций.

Этот бенчмарк просто измеряет скорость выполнения простых вычислений, в данном случае сравнение двух целых чисел внутри цикла. Как мы видим, интерпретатор был значительно ускорен с последними релизами. Теперь давайте обсудим, благодаря каким внутренним оптимизациям получилось увеличить скорость выполнения.

Появление суперинструкций

Одна из простых оптимизаций, введенных в CPython, — суперинструкции. Это специальные инструкции байт‑кода, которые создаются путем объединения двух последовательных инструкций определенных типов, которые часто встречаются в парах в программах. Давайте разберемся, как это работает в контексте этого конкретного бенчмарка.

На изображении ниже показан байт‑код тела цикла этого бенчмарка для Python 3.14.0a0 (слева) и Python 3.10 (справа). В цикле интерпретатору нужно многократно загружать значения heights[a] и min_height в стек перед тем, как сравнить их. Для загрузки этих значений в стек интерпретатор использует инструкцию LOAD_FAST.

Вызовы функций в Python по прежнему медленные? Анализ последних оптимизаций в CPython - 3

Можно легко заметить разницу в байткоде для разных версий Python. В версия 3.10 байткод содержит две последовательные инструкции LOAD_FAST, тогда как в версии 3.14 они заменяются одной инструкцией LOAD_FAST_LOAD_FAST.

Это пример суперинструкции. Она создается компилятором во время оптимизации после генерации начального байт‑кода программы. Ниже код этой оптимизации в CPython, которая была введена в релизе 3.13.

static int
insert_superinstructions(cfg_builder *g)
{
    for (basicblock *b = g->g_entryblock; b != NULL; b = b->b_next) {

        for (int i = 0; i < b->b_iused; i++) {
            cfg_instr *inst = &b->b_instr[i];
            int nextop = i+1 < b->b_iused ? b->b_instr[i+1].i_opcode : 0;
            switch(inst->i_opcode) {
                case LOAD_FAST:
                    if (nextop == LOAD_FAST) {
                        make_super_instruction(inst, &b->b_instr[i + 1], LOAD_FAST_LOAD_FAST);
                    }
                    break;
                case STORE_FAST:
                    switch (nextop) {
                        case LOAD_FAST:
                            make_super_instruction(inst, &b->b_instr[i + 1], STORE_FAST_LOAD_FAST);
                            break;
                        case STORE_FAST:
                            make_super_instruction(inst, &b->b_instr[i + 1], STORE_FAST_STORE_FAST);
                            break;
                    }
                    break;
            }
        }
    }
    int res = remove_redundant_nops(g);
    assert(no_redundant_nops(g));
    return res;
}

Преимущества суперинструкций

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

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

Более того, реализация инструкции LOAD_FAST_LOAD_FAST в интерпретаторе позволяет процессору увеличить скорость ее выполнения, поскольку она включает в себя несколько независимых друг от друга инструкций, которые могут быть выполнены параллельно.

Реализация инструкции LOAD_FAST_LOAD_FAST в CPython. Одновременная загрузка двух значений в стек позволяет процессору выполнять эти инструкции параллельно благодаря ILP.

Реализация инструкции LOAD_FAST_LOAD_FAST в CPython. Одновременная загрузка двух значений в стек позволяет процессору выполнять эти инструкции параллельно благодаря ILP.

Специализация инструкций байт-кода

Вторая оптимизация, значительно улучшающая производительность для этого бенчмарка, — это специализация инструкций, введенная в релизе CPython 3.12.

Если вы снова посмотрите на байт‑код из предыдущего раздела, вы заметите, что интерпретатору нужно многократно выполнять COMPARE_OP и BINARY_OP для выполнения операций сравнения и инкремента внутри цикла.

Эти инструкции относительно затратны в выполнении, поскольку они связаны с динамической диспетчеризацией. Я рассматривал, что именно происходит под капотом в статье «How Many Lines of C it Takes to Execute a + b in Python?». Ниже краткое содержание.

Когда интерпретатору нужно обработать такие инструкции, как BINARY_OP или COMPARE_OP, он получает их операнды из стека. Интерпретатор не знает конкретные типы этих объектов‑операндов, будь то целые числа, строки, числа с плавающей запятой или что‑то еще, и, следовательно, не знает, как обработать данный случай. Интерпретатор определяет, как обработать операцию, выполняя поиск указателя на функцию внутри объектов‑операндов. Но это требует огромного количества операций поиска по указателям.

  • Сначала интерпретатору нужно разыменовать объект‑операнд.

  • Затем нужно разыменовать указатель на поле PyTypeObject (ob_type), которое содержит таблицы указателей на функции.

  • Затем интерпретатору нужно разыменовать таблицу указателей на функции и найти указатель на функцию.

  • Наконец, нужно разыменовать сам указатель на функцию, чтобы вызвать функцию.

Следующая иллюстрация показывает этот процесс поиска по указателям.

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

Количество уровней абстракции, связанных с выполнением бинарной операции или операции сравнения интерпретатором байт‑кода.

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

Но благодаря специализации медленные инструкции BINARY_OP и COMPARE_OP преобразуются в специализированные, например BINARY_ADD_INT, где операция сложения выполняется непосредственно в интерпретаторе без выполнения переходов по указателям.

Бенчмарк 2: Проверка скорости выполнения с использованием встроенной функции

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

def benchmark2(heights):
    a = 1
    b = len(heights) - 1
    min_height = heights[0]
    while a < b:
        min_height = min(heights[a], min_height)
        a += 1

    return min_height

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

Вызовы функций в Python по прежнему медленные? Анализ последних оптимизаций в CPython - 6

Произошло два изменения, с которыми связано уменьшение времени выполнения с 17,33 секунд в Python 3.10 до 6,7 секунд в Python 3.14.0a0. Давайте обсудим их.

Ускорение загрузки глобальных объектов

Давайте посмотрим на байт‑код этого бенчмарка.

Байт‑код второго бенчмарка в CPython 3.14.0a0.

Байт‑код второго бенчмарка в CPython 3.14.0a0.

При выполнении этого кода интерпретатору необходимо загрузить встроенную функцию min() в стек. Для этого он использует инструкцию LOAD_GLOBAL.

Инструкции LOAD_GLOBAL необходимо найти глобальный именованный объект в двух словарях. Первый словарь содержит все глобальные переменные в текущей области видимости, а второй — все встроенные функции.

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

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

Реализация LOAD_GLOBAL_BUILTIN в интерпретаторе байт-кода CPython.

Реализация LOAD_GLOBAL_BUILTIN в интерпретаторе байт‑кода CPython.

Оптимизация встроенных функций min и max

Специализация инструкции LOAD_GLOBAL в LOAD_GLOBAL_BUILTIN не является основной причиной впечатляющего результата последних версий Python в рамках этого бенчмарка. Реальная причина — это специфическая оптимизация, примененная к встроенным функциям min и max.

В интерпретаторе есть два соглашения для вызова функций: старое — tp_call и новое — vectorcall.

При использовании tp_call создаются промежуточные кортежи и словари для передачи аргументов функции, что может приводить к затратам на создание других промежуточных объектов (более подробно это описано в PEP 0590). При использовании vectorcall аргументы передаются как часть вектора, что устраняет необходимость в создании множества промежуточных объектов.

До релиза CPython 3.13 встроенные функции min и max вызывались с использованием tp_call. Это приводило к тому, что частый вызов функций приводил к выделению и освобождению множества промежуточных объектов. Переход на vectorcall улучшил производительность этих встроенных функций вплоть до 200%, а в нашем бенчмарке видно улучшение более чем на 150%.

Для получения дополнительного контекста вы можете ознакомиться с PR этого изменения.

Бенчмарк 3: Проверка скорости выполнения с использованием функции Python

Наконец, давайте обсудим изменения, которые стали причиной улучшения производительности в третьем бенчмарке, который реализует min как функцию Python и вызывает ее внутри цикла. Код приведен ниже.

def pymin(a, b):
    if a <= b:
        return a
    return b
	

def benchmark3(heights):
    a = 1
    b = len(heights) - 1
    min_height = heights[0]
    while a < b:
        min_height = pymin(heights[a], min_height)
        a += 1

    return min_height

Сравнение результатов выполнения данного бенчмарка для последних релизов CPython:

Вызовы функций в Python по прежнему медленные? Анализ последних оптимизаций в CPython - 9

Согласно данным в таблице, производительность значительно улучшилась с 3.10 до 3.12, а затем немного улучшилась для 3.14.0a0.

Этот бенчмарк по сути измеряет затраты на выполнение вызова функции Python‑to‑Python (поскольку и вызывающая, и вызываемая функции реализованы на Python).

До версии 3.11 обработка вызовов функций Python‑to‑Python в интерпретаторе была сложной и затратной, поскольку это приводило к рекурсивному вызову самого интерпретатора для обработки каждого такого вызова. Эта рекурсия была встроена в релизе CPython 3.11, что привело к значительному приросту производительности. Давайте разберем это более детально.

Встраивание вызовов функций Python-to-Python

Интерпретатор начинает выполнение программы Python с функции main. В первую очередь подготавливается фрейм стека функции main, после чего идет вызов интерпретатора. Точка входа в интерпретатор — это функция _PyEval_EvalFrameDefault, определенная в ceval.c.

Что такое фрейм стека? Выполнение каждой функции в вашем коде требует соответствующего фрейма. Он содержит локальные и глобальные переменные этой функции, скомпилированный байт‑код, указатель на инструкцию и другие данные, которые помогают интерпретатору выполнить код. Для получения более подробной информации вы можете посмотреть запись моей лекции о внутреннем устройстве виртуальной машины CPython.

Функция _PyEval_EvalFrameDefault содержит огромный оператор switch для обработки всех инструкций байт‑кода, поддерживаемых интерпретатором. Функция перебирает инструкции полученной функции и выполняет соответствующие операции.

Пример цикла обработки байт-кода в простой виртуальной машине, реализованной на Python. Интерпретатор проходит по каждой инструкции байт-кода и, основываясь на опкоде, обрабатывает ее. Виртуальная машина CPython реализована на C, это просто для иллюстрации.

Пример цикла обработки байт‑кода в простой виртуальной машине, реализованной на Python. Интерпретатор проходит по каждой инструкции байт‑кода и, основываясь на опкоде, обрабатывает ее. Виртуальная машина CPython реализована на C, это просто для иллюстрации.

Когда вы вызываете другую функцию в вашем коде Python, это приводит к генерации инструкции байт‑кода CALL. Вот тут все и становится интереснее.

В CPython 3.10 и ранее инструкция CALL создавала новый фрейм стека для вызываемой функции, а затем рекурсивно возвращалась в интерпретатор, вызывая его точку входа _PyEval_EvalFrameDefault.

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

В релизе 3.11 это было исправлено за счет устранения рекурсивного вызова интерпретатора. Теперь инструкция CALL просто создает фрейм стека для вызываемой функции, а затем сразу начинает выполнение байт‑кода новой функции, не покидая цикла.

Вы можете ознакомиться с обсуждением этого изменения в багтрекере CPython.

Специализация инструкции CALL

Хотя основное улучшение производительности этого бенчмарка связано с встраиванием функций, описанным выше, есть еще одно небольшое улучшение, касающееся выполнения вызовов функций в интерпретаторе — специализация инструкции CALL.

Инструкция CALL является универсальной для выполнения всех типов вызываемых объектов. При ее обработке интерпретатору необходимо проверить тип вызываемого объекта, например, является ли он методом класса, методом экземпляра, функцией или чем‑то еще, и на основе этого правильно вызвать нужный объект.

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

Заключение

Мы подробно рассмотрели производительность Python, сосредоточив внимание на затратах на вызовов функций, вызовах встроенных функций и встраивании кода. Наши бенчмарки показали значительные улучшения производительности с Python 3.10 до Python 3.14.0a0. Ниже краткий обзор причин этих улучшений:

  • Суперинструкции: Объединяя последовательные инструкции байт‑кода в единые суперинструкции, такие как LOAD_FAST_LOAD_FAST, CPython уменьшает затраты на выполнение отдельных инструкций байт‑кода. Это улучшение помогает как интерпретатору, так и процессору работать более эффективно.

  • Специализация инструкций байт‑кода: Новые специализированные инструкции байт‑кода (например, BINARY_ADD_INT) убирают необходимость в медленной динамической диспетчеризации, ускоряя обычные операции.

  • Оптимизация встроенных функций: Переход от старого метода tp_call к более быстрому vectorcall значительно повысил производительность встроенных функций min и max.

  • Встраивание вызовов функций Python‑to‑Python: Устранив старый способ обработки вызовов функций Python‑to‑Python (который включал громоздкие рекурсивные вызовы интерпретатора), новые версии, начиная с CPython 3.11, сделали эти вызовы быстрее.

В целом, эти изменения демонстрируют постоянные улучшения скорости и эффективности Python. Однако перед тем как использовать результаты из этой статьи, помните, что сначала необходимо провести профилирование, чтобы найти самые медленные участки кода (закон Амдала).

Автор: MrPizzly

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js