[Перевод] Сравнение производительности 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 он сначала компилирует его в команды байт-кода, а затем интерпретирует их.
Чтобы лучше понять причины разницы производительности между dist() и {}, давайте сравним команды байт-кода, в которые они компилируются. У 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 | |Каждый столбец имеет своё предназначение:
Номер строки исходного кода.
Адрес команды — байтовый индекс в скомпилированном байт-коде.
Имя байт-кода (опкод).
Параметры операции.
Человекочитаемая интерпретация параметров операций.
Разобравшись с этим и воспользовавшись справкой по множеству опкодов, мы можем понять, что:
RESUME— ничего не делает. Она выполняет внутреннее отслеживание, отладку и проверки оптимизации.LOAD_GLOBAL— записывает в стек глобальную переменную. Из человекочитаемой интерпретации параметров опкода мы знаем, что она записываетdict(пока не будем обращать внимание наNULL).CALL— вызывает вызываемый объект с количеством аргументов, задаваемымargc; в нашем случае это ноль.RETURN_VALUE— возвращает последний элемент из стека вызывающей стороне.
При компиляции return {} получается ещё один опкод:
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 git@github.com: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 отвечает за распределение нового объекта кортежа, а элементы передаются как параметр.
