Сравнение производительности dict() и {} в Python

Какое-то время назад, во время разбора кода, мы обсудили выбор dict() вместо {} в новом коде на Python. Коллега утверждал, что dict() более читаем и чётче выражает предназначение кода, поэтому следует предпочесть его. Меня это не убедило, но в тот момент контраргументов не нашлось, поэтому я воздержался.

Это заставило меня задуматься: в чём разница между типом dict и литеральным выражением {}?

Давайте изучим этот вопрос.

Примечание

Во всех примерах кода я буду использовать Python 3.12. Это очень важно, потому что между последними дополнительными версиями Python есть существенные различия

Словари Python

Сначала давайте сравним разницу производительности между двумя этими способами. Для этого я воспользуюсь модулем timeit.

$ python -m timeit "dict()"
10000000 loops, best of 5: 40 nsec per loop
$ python -m timeit "{}"
20000000 loops, best of 5: 19.6 nsec per loop

На моём MacBook M1 разница почти двукратная. Довольно существенно, особенно если учитывать, что оба этих выражения создают полностью одинаковый объект.

Откуда берётся такое разли��ие?

Прежде чем мы разберём это, нам нужно немного отклониться от темы и поговорить о том, что происходит при исполнении кода на Python. Python — это интерпретирумый язык, ему необходим интерпретатор. Самый популярный для Python — это CPython; это эталонная реализация, то есть все остальные интерпретаторы используют её для определения «корректного» поведения. Если вы устанавливали Python из стандартного дистрибутива, то на вашей машине установлен CPython.

Любопытно, что CPython — это и компилятор, и интерпретатор. При исполнении кода на Python он сначала компилирует его в команды байт-кода, а затем интерпретирует их.

Чтобы лучше понять причины разницы производительности между dict() и {}, давайте сравним команды байт-кода, в которые они компилируются. У Python есть встроенный модуль dis, выполняющий именно эту задачу.

>>> import dis
>>> def a():
...   return dict()
...
>>> def b():
...   return {}
...
>>> dis.dis(a)
  1           0 RESUME                   0

  2           2 LOAD_GLOBAL              1 (NULL + dict)
             12 CALL                     0
             20 RETURN_VALUE
>>> dis.dis(b)
  1           0 RESUME                   0

  2           2 BUILD_MAP                0
              4 RETURN_VALUE

Хотя они создают одинаковый результат, очевидно, что два выражения исполняют разный код.

Команды байт-кода

Вывод dis.dis понять довольно просто.

 (1) |    (2)    |          (3)          | (4) |      (5)      
-----|-----------|-----------------------|-----|---------------
   1 |         0 | RESUME                | 0   |
     |           |                       |     |
   2 |         2 | LOAD_GLOBAL           | 1   | (NULL + dict)
     |        12 | CALL                  | 0   |
     |        20 | RETURN_VALUE          |     |

Каждый столбец имеет своё предназначение:

1. Номер строки исходного кода.

2. Адрес команды — байтовый индекс в скомпилированном байт-коде.

3. Имя байт-кода (опкод).

4. Параметры операции.

5. Человекочитаемая интерпретация параметров операций.

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

1. RESUME — ничего не делает. Она выполняет внутреннее отслеживание, отладку и проверки оптимизации.

2. LOAD_GLOBAL — записывает в стек глобальную переменную. Из человекочитаемой интерпретации параметров опкода мы знаем, что она записывает dict (пока не будем обращать внимание на NULL).

3. CALL — вызывает вызываемый объект с количеством аргументов, задаваемым argc; в нашем случае это ноль.

4. RETURN_VALUE — возвращает последний элемент из стека вызывающей стороне.

При компиляции return {} получается ещё один опкод:

5. BUILD_MAP — записывает в стек новый объект словаря. Извлекает 2 * count элементов, чтобы словарь содержал count записей.

Мы уже видим несколько очевидных различий между двумя ситуациями. Выражение {} создаёт словарь напрямую, а dict() делегирует эту задачу вызываемому объекту. Прежде, чем это может случиться, он сначала должен записать в стек глобальное значение (dict); на самом деле, он делает это каждый раз, когда мы вызываем эту функцию.

Почему?

Потому что dict непостоянен: его можно перезаписывать, а потому получить другое значение.

>>> def a():
...   return dict()
...
>>> dict = lambda: 42
>>>
>>> assert a() == 42

Такое может произойти. Именно поэтому Python должен генерировать эту излишнюю нагрузку по записи и вызову вызываемого объекта при каждом вызове функции.

Ну ладно, всё это звучит очень логично. Вызов вызываемого объекта создаёт излишнюю трату ресурсов, и разумно предположить, что разница, которую мы увидели в начале этого поста — результат этой траты. Но уверены ли мы, что внутри dict() вызывает тот же код, что и {}? dict — это класс и, к счастью, функция dis.dis может компилировать классы в байт-код.

Пример

import dis

class Foo:
    def bar(self):
        return 42

    def __str__(self):
        return self.__class__.__name__

dis.dis(Foo)

Она выводит дизассемблированный код для всех методов классов:

Disassembly of __str__:
  8           0 RESUME                   0

  9           2 LOAD_FAST                0 (self)
              4 LOAD_ATTR                0 (__class__)
             24 LOAD_ATTR                2 (__name__)
             44 RETURN_VALUE

Disassembly of bar:
  5           0 RESUME                   0

  6           2 RETURN_CONST             1 (42)

Давайте попробуем выполнить это для dict:

>>> dis.dis(dict)
>>>

… ничего не выводится? Почему?

Ну, модуль dis не особо полезен для изучения внутренних типов, и dict — один из таких типов, определяемый внутри исходного кода интерпретатора.

Блуждаем в исходном коде CPython

Чтобы прикоснуться к запретной магии, нам нужно сначала клонировать репозиторий CPython. Нам не нужна вся история, так что укажем --depth 1.

git clone --depth 1 --branch v3.12.0 https://github.com/python/cpython.git
# или
git clone --depth 1 --branch v3.12.0 [e-mail]:python/cpython.git

Затем нам нужно найти то, что мы действительно ищем — место, где интерпретирутся команды опкодов. Выпив чашку кофе и введя множество команд grep, мы, наконец, находим файл Python/bytecodes.c. Он состоит из одного оператора switch и похоже, что все команды байт-кода интерпретирутся здесь.

Тип dict

Давайте сначала взглянем на dict. Все внутренние типы определяются как объекты PyTypeObject, а ��ип dict определяется в файле dictobject.c. У него определено множество атрибутов, но нас интересуют только два:

PyTypeObject PyDict_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "dict",
    sizeof(PyDictObject),
    // ...
    dict_init,                                  /* tp_init */
    // ...
    dict_new,                                   /* tp_new */
    // ...
};

Эта пара (dict_new и dict_init) сообщает нам, что происходит, когда создаётся новый словарь.

Примечание

Конструктор в Python называется __new__. Это статический метод, возвращающий новый объект своего типа.

Метод-инициализатор называется __init__. Он берёт новый созданный объект и инициализирует его атрибуты. Метод __init__ вызывается после метода __new__.

Функция dict_new определена здесь: dictobject.c#L3751.

static PyObject *
dict_new(PyTypeObject*type, PyObject *args, PyObject*kwds)
{
    assert(type != NULL);
    assert(type->tp_alloc != NULL);
    // dict subclasses must implement the GC protocol
    assert(_PyType_IS_GC(type));

    PyObject *self = type->tp_alloc(type, 0);
    if (self == NULL) {
        return NULL;
    }
    PyDictObject *d = (PyDictObject *)self;

    d->ma_used = 0;
    d->ma_version_tag = DICT_NEXT_VERSION(
            _PyInterpreterState_GET());
    dictkeys_incref(Py_EMPTY_KEYS);
    d->ma_keys = Py_EMPTY_KEYS;
    d->ma_values = NULL;
    ASSERT_CONSISTENT(d);

    // ...

    return self;
}

Мы видим, что сначала она распределяет новый объект через переданный распределитель (9-я строка), а затем задаёт некоторые из его внутренних полей (15-я, 19-я и 20-я строки). Любопытно, что она не распределяет предварительно внутреннюю память словаря (см. помеченные строки). Поначалу это может показаться странным, но нужно помнить, что инициализация объекта, как и предварительное распределение памяти, выполняется не методом __new__, для этого нужен метод __init__.

После помещения нового объекта в память функция dict_init может вставлять в него элементы. Логика вставки делегируется функции dict_update_common, которую можно найти здесь: dictobject.c#L2678.

static int
dict_update_common(PyObject *self, PyObject *args, PyObject *kwds,
                   const char *methname)
{
    PyObject *arg = NULL;
    int result = 0;

    if (!PyArg_UnpackTuple(args, methname, 0, 1, &arg)) {
        result = -1;
    }
    else if (arg != NULL) {
        result = dict_update_arg(self, arg);
    }

    if (result == 0 && kwds != NULL) {
        if (PyArg_ValidateKeywordArguments(kwds))
            result = PyDict_Merge(self, kwds, 1);
        else
            result = -1;
    }
    return result;
}

Она обновляет словарь из args и kwargs.

args и dict_update_arg

Для args она вызывает функцию dict_update_arg.

static int
dict_update_arg(PyObject *self, PyObject *arg)
{
    if (PyDict_CheckExact(arg)) {
        return PyDict_Merge(self, arg, 1);
    }
    PyObject *func;
    if (_PyObject_LookupAttr(arg, &_Py_ID(keys), &func) < 0) {
        return -1;
    }
    if (func != NULL) {
        Py_DECREF(func);
        return PyDict_Merge(self, arg, 1);
    }
    return PyDict_MergeFromSeq2(self, arg, 1);
}

Функция проверяет, является ли arg словарём, и если это так, объединяет два словаря (PyDict_Merge), а в противном случае добавляет новые элементы из последовательностей пар (PyDict_MergeFromSeq2).

kwargs и PyDict_Merge

Путь kwargs заканчивается в том же месте — в PyDict_Merge. Давайте изучим это.

Внутри она делегирует всю логику функции dict_merge.

static int
dict_merge(PyInterpreterState *interp, PyObject *a, PyObject *b, int override)
{
    PyDictObject *mp, *other;

    assert(0 <= override && override <= 2);

    /* We accept for the argument either a concrete dictionary object,
     * or an abstract "mapping" object.  For the former, we can do
     * things quite efficiently.  For the latter, we only require that
     * PyMapping_Keys() and PyObject_GetItem() be supported.
     */
    if (a == NULL || !PyDict_Check(a) || b == NULL) {
        PyErr_BadInternalCall();
        return -1;
    }
    mp = (PyDictObject*)a;
    if (PyDict_Check(b) && (Py_TYPE(b)->tp_iter == (getiterfunc)dict_iter)) {

        // ...
    else {
        /* Do it the generic, slower way */

        // ...
    }
    ASSERT_CONSISTENT(a);
    return 0;
}

Из комментария становится понятно, что функция была оптимизирована под вызов с другим словарём в качестве параметра. Если параметр не является словарём, то это общий Mapping — объект-контейнер, поддерживающий произвольный поиск ключей.

Выражение {}

Литеральное выражение изучать должно быть проще. Давайте вернёмся к файлу bytecode.c и найдём отображение для байт-кода BUILD_MAP.

inst(BUILD_MAP, (values[oparg*2] -- map)) {
    map = _PyDict_FromItems(
            values, 2,
            values+1, 2,
            oparg);
    if (map == NULL)
        goto error;

    DECREF_INPUTS();
    ERROR_IF(map == NULL, error);
}

Исходники см. здесь: bytecode.c#L1541.

Мы видим, что словарь полностью создаётся и возвращается функцией _PyDict_FromItems. Давайте перейдём к ней.

PyObject *
_PyDict_FromItems(PyObject *const *keys, Py_ssize_t keys_offset,
                  PyObject *const *values, Py_ssize_t values_offset,
                  Py_ssize_t length)
{
    bool unicode = true;
    PyObject *const *ks = keys;
    PyInterpreterState *interp = _PyInterpreterState_GET();

    for (Py_ssize_t i = 0; i < length; i++) {
        if (!PyUnicode_CheckExact(*ks)) {
            unicode = false;
            break;
        }
        ks += keys_offset;
    }

    PyObject *dict = dict_new_presized(interp, length, unicode);
    if (dict == NULL) {
        return NULL;
    }

    ks = keys;
    PyObject *const *vs = values;

    for (Py_ssize_t i = 0; i < length; i++) {
        PyObject *key = *ks;
        PyObject *value = *vs;
        if (PyDict_SetItem(dict, key, value) < 0) {
            Py_DECREF(dict);
            return NULL;
        }
        ks += keys_offset;
        vs += values_offset;
    }

    return dict;
}

Больше всего нас интересует строка 18: в отличие от dict_new, она предварительно распределяет словарь, так что уже имеет объём для всех его элементов. Затем она одну за другой вставляет пары ключ-значение.

Выводы

Подведём итог.

Когда мы выполняем dict(a=1, b=2), Python должен:

• распределить новый PyObject,

• создать dict при помощи метода __new__,

• вызвать его метод __init__, который внутри вызывает PyDict_Merge,

• так как kwargs не является dict, PyDict_Merge необходимо использовать более медленный метод, вставляющий элементы один за другим.

А выполнение {} заставляет Python:

• создать новый заранее распределённый словарь,

• один за другим вставлять элементы.

Честно говоря, если вы не создаёте словари в цикле, то я не думаю, что получите особый рост производительности, перейдя с dict на {}. Считаю, что об этом следует помнить после прочтения поста:

tl;dr

{} всегда быстрее, чем dict.

Приложение

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

Списки

$ python -m timeit "list((1, 2, 'a'))"
5000000 loops, best of 5: 53.4 nsec per loop
$ python -m timeit "[1, 2, 'a']"
10000000 loops, best of 5: 29.7 nsec per loop

Тип list

Тип list Python определяется в файле listobject.c:

PyTypeObject PyList_Type = {
    // ...
    (initproc)list___init__, /* tp_init */
    PyType_GenericAlloc, /* tp_alloc */
    PyType_GenericNew, /* tp_new */
    // ...
}

PyType_GenericNew ничего не делает — она игнорирует args и kwargs, и возвращает объект, распределённый type->typ_alloc. Источник: https://github.com/python/cpython/blob/main/Objects/typeobject.c#L1768

PyType_GenericAlloc распределяет новый объект и помечает его (если с ним можно выполнить сборку мусора) как «собираемый».

list___init__ — это обёртка для удобства вокруг функции list___init___impl, которая выполняет саму инициализации. Она выполняет основные подготовительные этапы:

• завершается с ошибкой, если были переданы kwarg,

• завершается с ошибкой, если args имеет больше одного элемента,

• преобразует первый аргумент args в итерируемый объект.

list___init___impl очищает список (если он не пустой) и расширяет его переданным итерируемым объектом (вызывая функцию list_extend).

Вопрос

Я думаю, что два этих способа:

list((1, 2, 3))

_tmp = list()
_tmp.extend((1, 2, 3))

эквивалентны во всём (за исключением генерируемой последовательности опкодов) и вызывают одинаковый код на C.

Литеральное выражение []

Опкод BUILD_LIST использует функцию _PyList_FromArraySteal для создания объекта списка и его возврата.

Примечание

С версии 3.12 используется _PyList_FromArraySteal. См. changelog 3.12 и gh-100146. До версии 3.12 опкод многократно вызывал POP() для получения элементов из стека, а затем вставлял их в список.

while (--oparg >= 0) {
    PyObject *item = POP();
    PyList_SET_ITEM(list, oparg, item);
}

См. изменение в gh-100146 PR.

Вспомогательная функция  _PyList_FromArraySteal создаёт пустой список (если элементов нет) или предварительно распределяет список, прежде чем вставлять в него элементы.

PyObject **dst = list->ob_item;
memcpy(dst, src, n * sizeof(PyObject *));

Множества

Примечание

Насколько я помню, не существует способов создания нового множества при помощи литерального выражения, поэтому приведённый ниже анализ выполнен для множеств с двумя элементами: 1 и 2.

$ python -m timeit "set((1, 2))"
5000000 loops, best of 5: 82.6 nsec per loop
$ python -m timeit "{1, 2}"
5000000 loops, best of 5: 45.5 nsec per loop

Тип set

Тип set в Python определяется в файле setobject.c:

PyTypeObject PySet_Type = {
    // ...
    (initproc)set_init, /* tp_init */
    PyType_GenericAlloc, /* tp_alloc */
    set_new, /* tp_new */
    // ...
}

set_new использует распределение для создания нового пустого объекта множества. Внутри он вызывает функцию make_new_set.

set_init выполняет предварительные этапы:

• завершается с ошибкой, если переданы kwarg,

• завершается с ошибкой, если args содержит больше одного элемента,

• преобразует первый аргумент args в итерируемый объект,

• если ��бъект множества уже заполнен, очищает его

… и вызывает функцию set_update_internal для вставки значений в объект множества.

Литеральное выражение {1, 2}

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

inst(BUILD_SET, (values[oparg] -- set)) {
    set = PySet_New(NULL);
    if (set == NULL)
    GOTO_ERROR(error);
    int err = 0;
    for (int i = 0; i < oparg; i++) {
        PyObject *item = values[i];
        if (err == 0)
            err = PySet_Add(set, item);
        Py_DECREF(item);
    }
    if (err != 0) {
        Py_DECREF(set);
        ERROR_IF(true, error);
    }
}

Источник: https://github.com/python/cpython/blob/main/Python/bytecodes.c#L1627.

Предупреждение

Сгенерированный байт-код будет отличаться, если мы добавим к литеральному выражению ещё один аргумент: {1, 2, 3}. Он становится таким:

   2 BUILD_SET                0
   4 LOAD_CONST               1 (frozenset({1, 2, 3}))
   6 SET_UPDATE               1
   8 RETURN_VALUE

Кортежи

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

>>> import sys
>>> sys.version_info
sys.version_info(major=3, minor=12, micro=1, releaselevel='final', serial=0)
>>>
>>> def a():
...   return tuple((1, 2, []))
>>>
>>> def b():
...   return (1, 2, [])
>>>
>>> import dis
>>>
>>> dis.dis(a)
  1           0 RESUME                   0

  2           2 LOAD_GLOBAL              1 (NULL + tuple)
             12 LOAD_CONST               1 (1)
             14 LOAD_CONST               2 (2)
             16 BUILD_LIST               0
             18 BUILD_TUPLE              3
             20 CALL                     1
             28 RETURN_VALUE
>>> dis.dis(b)
  1           0 RESUME                   0

  2           2 LOAD_CONST               1 (1)
              4 LOAD_CONST               2 (2)
              6 BUILD_LIST               0
              8 BUILD_TUPLE              3
             10 RETURN_VALUE

Возможно, добавлять этот пример в статью не имело особого смысла.

Тип tuple

Тип tuple в Python определяется в файле tupleobject.c. Любопытно, что он не имеет ни tp_alloc, ни tp_init.

PyTypeObject PyTuple_Type = {
    // ...
    0, /* tp_init */
    0, /* tp_alloc */
    tuple_new, /* tp_new */
    // ...
}

Функция tuple_new отвечает за распределение нового объекта кортежа, а элементы передаются как параметр.