Распределение памяти CPython

Ответ 1

В большей части этого ответа в главе Управление памятью содержится документация по API C.

Некоторая документация более неопределенная, чем вы просите. Для получения дополнительной информации вам нужно обратиться к исходному коду. И никто не захочет этого делать, если не выбрать конкретную версию. (Не менее 2.7.5, pre-2.7.6, 3.3.2, pre-3.3.3 и pre-3.4 будут интересны для разных людей.)

Источник в файле obmalloc.c является хорошим отправным местом для многих ваших вопросов, а комментарии в верхней части имеют приятный небольшой график ASCII-art

    Object-specific allocators
    _____   ______   ______       ________
   [ int ] [ dict ] [ list ] ... [ string ]       Python core         |
+3 | <----- Object-specific memory -----> | <-- Non-object memory --> |
    _______________________________       |                           |
   [   Python`s object allocator   ]      |                           |
+2 | ####### Object memory ####### | <------ Internal buffers ------> |
    ______________________________________________________________    |
   [          Python`s raw memory allocator (PyMem_ API)          ]   |
+1 | <----- Python memory (under PyMem manager`s control) ------> |   |
    __________________________________________________________________
   [    Underlying general-purpose allocator (ex: C library malloc)   ]
 0 | <------ Virtual memory allocated for the python process -------> |

   =========================================================================
    _______________________________________________________________________
   [                OS-specific Virtual Memory Manager (VMM)               ]
-1 | <--- Kernel dynamic storage allocation & management (page-based) ---> |
    __________________________________   __________________________________
   [                                  ] [                                  ]
-2 | <-- Physical memory: ROM/RAM --> | | <-- Secondary storage (swap) --> |

сколько разных распределителей есть в CPython?

В соответствии с документами "несколько". Вы можете подсчитать числа в встроенных и stdlib-типах, а затем добавить несколько общих, если хотите. Но я не уверен, что это скажет вам. (И это было бы довольно специфично для версии. IIRC, точное число даже изменилось в дереве 3.3, поскольку был эксперимент с тем, должны ли строки нового стиля использовать три разных распределителя или один.)

Какова функция каждого?

Объектно-ориентированные распределители на уровне +3 предназначены для конкретных случаев использования, которые стоит оптимизировать. Как говорят документы:

Например, целочисленные объекты управляются по-разному в куче, чем строки, кортежи или словари, потому что целые числа подразумевают разные требования к хранению и компромиссы между скоростью и пространством.

Ниже приведены различные общие вспомогательные распределители на уровне +2 (и +1,5 и, возможно, +2,5) - по крайней мере, распределитель объектов, распределитель арены и распределитель малой блокировки и т.д., но все, кроме сначала это частные подробности реализации (что означает private даже для C-API, очевидно, что все это является частным для кода Python).

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

когда вызывается malloc?

Необработанный распределитель памяти (или его менеджер кучи) должен быть единственным, что когда-либо называет malloc. (На самом деле, возможно, даже необязательно вызвать malloc, вместо этого он может использовать такие функции, как mmap или VirtualAlloc. Но дело в том, что это единственное, что когда-либо запрашивает ОС для памяти.) Есть несколько исключения в ядре Python, но они редко будут релевантными.

В документах явно говорится, что код более высокого уровня никогда не должен пытаться работать с объектами Python в памяти, полученной из malloc.

Однако существует множество модулей stdlib и расширения, которые используют malloc для целей помимо объектов Python.

Например, массив numpy из 1000x1000 значений int32 не выделяет 1 миллион Python int s, поэтому ему не нужно проходить через распределитель int. Вместо этого он просто malloc содержит массив из 1 миллиона C int s и переносит их в объекты Python по мере необходимости при доступе к ним.

Сколько памяти питон выделяет для себя при запуске?

Это зависит от платформы и немного сложно понять из кода. Однако, когда я запускаю новый интерпретатор python3.3 на моем 64-битном Mac, он начинается с 13,1 МБ виртуальной памяти и почти сразу расширяется до 201 МБ. Таким образом, это должно быть грубым руководством по шарикам.

существуют ли правила, определяющие, какие структуры данных получают первые "dibs" в этой памяти?

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

Что происходит с памятью, используемой объектом при ее удалении (python все еще удерживает память для выделения другому объекту в будущем или GC освобождает память для другого процесса, например, Google Chrome, для использования)?

Он возвращается к объектно-ориентированному распределителю, который может содержать его в freelist или отсылать его в исходный распределитель, который сохраняет свой собственный фриланс. Необработанный распределитель почти никогда не выпускает память обратно в ОС.

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

Когда запускается GC?

Это зависит от того, что вы подразумеваете под "GC".

CPython использует refcounting; каждый раз, когда вы отпускаете ссылку на объект (путем перепроверки переменной или слота в коллекции, позволяя переменной выйти из области видимости и т.д.), если это была последняя ссылка, она будет немедленно очищена. Это объясняется в разделе Подсчет ссылок в документах.

Однако есть проблема с refcounting: если два объекта ссылаются друг на друга, даже когда все внешние ссылки уходят, они по-прежнему не будут очищены. Таким образом, у CPython всегда был сборщик циклов, который периодически ходит по объектам, которые ищут циклы объектов, которые ссылаются друг на друга, но не имеют внешних ссылок. (Это немного сложнее, но основная идея.) Это полностью объяснено в документах для модуля gc. Коллекционер может работать, когда вы спрашиваете его явно, когда фрилайсты становятся низкими или когда он не запускается в течение длительного времени; это динамично и в некоторой степени настраивается, поэтому трудно дать конкретный ответ "когда".

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

Код для этого в основном находится внутри listobject.c. Это сложно; существует множество особых случаев, таких как код, используемый timsort для создания временных промежуточных списков и для сортировки без места. Но, в конечном счете, какой-то фрагмент кода решает, что ему нужно место для N указателей.

Это также не особенно интересно. Большинство списков либо никогда не расширяются, либо расширяются далеко за пределы исходного размера, поэтому при добавлении дополнительного выделения в начале происходит отмена памяти для статических списков и не очень помогает большинству растущих списков. Итак, Python играет его консервативным. Я полагаю, что он начинается с просмотра внутреннего фрейлиста, который не слишком много больше, чем N указателей (он также может консолидировать смежное хранилище с открытым списком, я не знаю, если он это делает), поэтому он мог бы зацикливаться немного время от времени, но в целом это не делает. Точный код должен быть в PyList_New.

Во всяком случае, если в списковом распределителе нет места, он падает до распределителя объектов и так далее через уровни; он может достигнуть уровня 0, но обычно этого не происходит.

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

Это обрабатывается в list_resize, и это интересная часть.

Единственный способ избежать квадратичности list.append состоит в том, чтобы распределить геометрически. Газоанализируя слишком мало фактора (например, 1,2), тратит слишком много времени на первые несколько расширений; используя слишком большой коэффициент (например, 1,6), тратит слишком много места на очень большие массивы. Python обрабатывает это, используя последовательность, начинающуюся с 2.0, но быстро сходится к где-то около 1,25. Согласно источнику 3.3:

Рисунок роста: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88,...

Вы не спрашивали конкретно о sorted, но я знаю, что вас подсказало.

Помните, что timsort - это, прежде всего, сортировка слияния, с сортировкой вставки для небольших подсписок, которые еще не отсортированы. Таким образом, большая часть его операций включает в себя выделение нового списка размером 2N и освобождение двух списков размером около N. Таким образом, при копировании он может быть почти таким же, как и на месте, с точки зрения пространства и распределения. Существует до O (log N) отходов, но это обычно не фактор, который делает копирование сортировки медленнее.