Вот ещё один вопрос на собеседовании для сеньора Python. Есть три разных способа сгенерировать список:

list1 = [0] * 3

list2 = [0, 0, 0]

list3 = [0 for i in range(3)]

В чём разница между list1, list2 и list3? Можно решить, что это один и тот же список, поскольку все они равны [0, 0, 0] :

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

sys.getsizeof(object[, default])

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

Учитывается только потребление памяти, напрямую связанное с объектом, а не потребление объектами, на которые он ссылается.

Почему у них разный размер? Почему sizeof([0, 0, 0]) больше, чем sizeof([0] * 3) ? Чтобы понять это, нужно разобраться в процессе. Нужно узнать, что происходило со списками, когда мы их создавали.

Python — это интерпретируемый язык программирования. Весь написанный нами код Python будет скомпилирован в байт-код для виртуальной машины Python:

Итак, каковы же байт-коды, соответствующие [0] * 3 и [0, 0, 0] ?

Анализ байт-кода CPython путём его дизассемблирования поддерживает модуль dis. Байт-код CPython, который этот модуль принимает как входные данные, определён в файле Include/opcode.h и используется компилятором и интерпретатором.

Этот способ можно использовать так:

import dis

print("disassemble [0] * 3")
dis.dis("[0] * 3")

print("disassemble [0, 0, 0]")
dis.dis("[0, 0, 0]")

print("disassemble [0 for i in range(3)]")
dis.dis("[0 for i in range(3)]")

Судя по байт-коду, списки явно разные!

Возможно, вы не знакомы с байт-кодом и виртуальной машиной Python, но не волнуйтесь: здесь мы вместе изучим основы CPython.

CPython

Есть несколько различных реализаций виртуальных машин Python, включая CPython, PyPy и Jython.

CPython — это оригинальная реализация Гвидо ван Россума. Загружая интерпретатор Python с официального сайта, вы загружаете реализацию CPython. Итак, в этой статье мы говорим о CPython. Исходный код CPython можно найти на GitHub.

Python имеет разные версии: от 2.x до 3.13. Здесь имеется ввиду Python 3.9. Если вы хотите следовать за мной шаг за шагом, перейдите в ветку Python 3.9. Если вы почитаете исходники других версий исходного кода CPython, то увидите в реализации функций будут небольшие различия, хотя принципы те же.

Весь исходный код операций, связанных со списками, находится в файле Ojbects/listobject.c.

Откройте его в браузере.

Список Python в CPython

Список Python в CPython состоит из двух частей. Это:

• Структура на C, записывающая метаданные списка, с фиксированным размером в 56 байтов.
• Массив указателей, где каждый элемент указывает на местоположение элемента в списке Python. В 64-битной операционной системе указатель имеет фиксированную длину 8 байтов.

Таким образом, память, занимаемая списком Python во время выполнения, равна 56 + 8 * n байтам, где n — длина массива указателей. Однако важно отметить, что размер массива указателей не должен соответствовать количеству элементов в списке Python. Вот почему размер списков, созданных с использованием трёх ранее упомянутых методов, различается.

Чтобы понять проблему, нужно знать, как CPython создаёт массивы для списков Python и распределяет память.

[0] * 3

Когда мы создаём новый список таким образом, используется байт-код BINARY_MULTIPLY, который в CPython соответствует функции list_repeat.

Основной код:

size = Py_SIZE(a) * n;

np = (PyListObject *) list_new_prealloc(size);

Здесь Py_SIZE(a) используется для получения длины исходного списка, в данном случае равной 1. Между тем, n — это множитель, который здесь равен 3. Поэтому функция в конечном счёте вызывает list_new_prealloc(3) для создания нового массива.

Код list_new_prealloc выглядит следующим образом:

Вот главное:

op->ob_item = PyMem_New(PyObject *, size);

Здесь мы видим, что когда для выделения памяти используется PyMem_New, новый список запрашивает ровно столько памяти, сколько ему необходимо, — никаких дополнительных операций, очень точно. Если нам нужно сохранить три элемента, создаётся массив указателей длиной 3. Таким образом, общий объём памяти, занимаемый списком Python, составляет 56 + 3 * 8 = 80 байт.

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

print(sys.getsizeof([0, 0] * 4))
# 56 + 2 * 4 * 8 => 120

print(sys.getsizeof([0] * 2))
# 56 + 1 * 2 * 8 => 72

print(sys.getsizeof([[], {}, 'str'] * 10))
# 56 + 3 * 10 * 8 => 296

[0, 0, 0]

Когда новый список создаётся таким способом, используется байт-код LIST_EXTEND, который в CPython соответствует функции list_extend:

Вот основа:

Py_ssize_t m;                  /* размер self */
Py_ssize_t n;                  /* предполагаемый размер iterable */

n = PySequence_Fast_GET_SIZE(iterable);
m = Py_SIZE(self);

list_resize(self, m + n)

m — это начальный размер списка, равный 0. А n — это размер списка позднее, он равен 3.

В конечном счёте на самом деле вызывается функция list_resize(self, 3).

list_resize

Подробнее рассмотрим изменение размера массива. Как только вы запрашиваете у операционной системы блок памяти для хранения массива, размер этого блока памяти фиксируется. Например, если вы запрашиваете массив с размером 80 байт, он может хранить максимум 10 указателей.

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

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

Например, если вам сейчас нужен массив ёмкостью 9, вы можете заранее выделить память для ёмкости 16. Когда вам нужен массив ёмкостью 17, можно выделить память для ёмкости 32.

Различные языки, платформы и структуры данных имеют разные стратегии изменения размера массива. Посмотрим, как list_resize реализован в CPython.

Код list_resize в Python 3.9 выглядит следующим образом:

Сначала он проверяет, достаточна ли текущая ёмкость allocated под массив для хранения элементов списка newsize. Если да, то дополнительно изменять размер массива не нужно.

Py_ssize_t allocated = self->allocated;

/* Пропуск realloc(), когда предыдущее перераспределение 
становится достаточно большим, 
чтобы вместить новый размер.  
Если новый размер меньше половины выделенного размера, 
realloc() выполняется, чтобы сократить список 
*/
if (allocated >= newsize && newsize >= (allocated >> 1)) {
    assert(self->ob_item != NULL || newsize == 0);
    Py_SET_SIZE(self, newsize);
    return 0;
}

Если ёмкость массива недостаточна, для изменения его размера используется следующий код:

/*
* Добавление отступов, чтобы выделенный размер был кратен 4.
* Последовательность роста такова:  0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...
*/
new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;

Когда newsize равна 3, new_allocated равна 8.

Возвращаясь к нашей теме, когда массив создаётся через [0, 0, 0], он выполняет байт-код LIST_EXTEND, который в конечном счёте вызывает list_resize(3). При этом создаётся массив указателей с длиной 8, совокупно занимающий 56 + 8 * 8 = 120 байтов памяти.

[0 for i in range(3)]

Когда новый список создаётся таким образом, используется байт-код LIST_APPEND, который в CPython соответствует функции list_app1:

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

Причина в следующем: при использовании [0, 0, 0] CPython выполняет list_resize(3) напрямую и создаётся массив длиной 8. Напротив, при использовании [0 for i in range(3)] список создаётся с помощью цикла for. Python не может предсказать окончательный размер такого списка, поэтому должен последовательно вызывать list_resize(1), list_resize(2) и list_resize(3).

Когда CPython выполняет list_resize(1), он создаёт массив ёмкостью 4.

Позже, когда CPython выполнил list_resize(2) и list_resize(3), ёмкости достаточно, и массив расходовать не нужно.

56 + 4 * 8 => 88

Более того, известно, что на данный момент ёмкость базового массива на языке C равна 4. Это означает, что когда списковое включение генерирует 4 элемента, размер списка остаётся равным 88 байтам. Однако, когда генератор списка создаёт 5 элементов, размер базового массива изменяется, а размер списка увеличивается до 120 байтов.

Читайте также:

• Автоматизируем создание отчета о расходах с помощью Python
• 12 проверенных способов оформления продакшн-кода на Python
• 5 удивительных скрытых возможностей Python. Часть 1

Читайте нас в Telegram, VK и Дзен

---

Перевод статьи: Shuai Li: Interviewer: What is the difference between [0] * 3 and [0, 0, 0] in Python?