Внутренние структуры CPython

Question

GAE имеет различные ограничения, одним из которых является размер самого большого выделяемого блока памяти, составляющий 1 МБ (теперь в 10 раз больше, но это не меняет вопроса). Ограничение означает, что в list () нельзя поместить более некоторого количества элементов, поскольку CPython будет пытаться выделить непрерывный блок памяти для указателей на элементы. Наличие огромных списков (списков) может считаться плохой практикой программирования, но даже если в самой программе не создается огромная структура, CPython оставляет некоторые закулисные.

Похоже, что CPython поддерживает единый глобальный список объектов или что-то в этом роде. То есть приложение, которое имеет много мелких объектов, имеет тенденцию выделять все большие и большие единичные блоки памяти.

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

Самое простое короткое приложение, которое сталкивается с проблемой:

a = b = []
number_of_lists = 8000000
for i in xrange(number_of_lists):
    b.append([])
    b = b[0]

Может ли кто-нибудь объяснить мне, как запретить CPython выделять огромные внутренние структуры при наличии множества объектов в приложении?

Answer 1

В 32-битной системе каждый из 8000000 списков, которые вы создаете, выделит 20 байтов для самого объекта списка, плюс 16 байтов для вектора элементов списка. Таким образом, вы пытаетесь выделить как минимум (20 + 16) * 8000000 = 20168000000 байт, около 20 ГБ. И это в лучшем случае, если система malloc выделяет столько памяти, сколько требуется.

Я рассчитал размер объекта списка следующим образом:

• 2 Указатели в самой структуре PyListObject (см. listobject.h )
• 1 Указатель и один Py_ssize_t для части PyObject_HEAD объекта списка (см. object.h )
• один Py_ssize_t для PyObject_VAR_HEAD (также в object.h)

Вектор элементов списка немного перераспределен, чтобы избежать необходимости изменять его размер при каждом добавлении - смотрите list_resize в listobject.c . Размеры: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ... Таким образом, ваши одноэлементные списки выделят место для 4 элементов.

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

Answer 2

Чтобы вы знали об этом, у Python есть свой собственный распределитель. Вы можете отключить его, используя --without-pyalloc на этапе настройки.

Однако самая большая арена - 256 КБ, так что проблем не должно быть. Вы также можете скомпилировать Python с включенной отладкой, используя --with-pydebug. Это даст вам больше информации об использовании памяти.

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

Answer 3

Чего вы пытаетесь достичь с помощью

a = b = []

и

b = b[0]

заявления? Конечно, странно видеть подобные выражения в Python, потому что они не делают того, что вы могли наивно ожидать: в этом примере a и b - это два имени для одного и того же списка (подумайте, указатели) в с). Если вы делаете много подобных манипуляций, то легко запутать сборщик мусора (и вас самих!), Потому что у вас много странных ссылок, которые не были должным образом очищены.

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

Answer 4

Я немного смущен тем, что вы спрашиваете. В этом примере кода ничто не должно быть собрано мусором, поскольку вы никогда не убиваете никаких ссылок. Вы держите ссылку на список верхнего уровня в a, и вы добавляете в него вложенные списки (удерживаемые в b на каждой итерации). Если вы удалите 'a =', , то у вас есть объекты, на которые нет ссылок.

Edit: в ответ на первую часть, да, Python содержит список объектов, чтобы он мог знать, что отбраковывать. Это весь вопрос? Если нет, прокомментируйте / отредактируйте свой вопрос, и я сделаю все возможное, чтобы помочь заполнить пробелы.