CPython内存分配

Question

这是一篇受此评论启发的帖子，内容涉及如何在CPython中为对象分配内存。最初，这是在创建列表并将其添加到for循环中_以_ 实现列表理解的上下文中。

所以这是我的问题：

1. CPython中有多少个不同的分配器？
   • 每个功能是什么？
2. 什么时候被正式malloc称为？（malloc根据此评论中的内容，列表理解可能不会导致调用，
3. python在启动时会为其分配多少内存？
   1. 是否有规则来控制哪些数据结构在此存储器上首先获得“特权”？
4. 删除对象时，该对象使用的内存会发生什么变化（python将来是否仍会保留在内存中以分配给另一个对象，或者GC是否释放内存供其他进程使用，例如Google Chrome） ？
5. GC何时触发？
6. lists是动态数组，这意味着它们需要一块连续的内存。这意味着，如果我尝试将对象追加到无法扩展其基础C数据结构数组的列表中，则会将该数组复制到内存的不同部分，在该部分中可以使用较大的连续块。因此，当我初始化列表时，会为该数组分配多少空间？
   • 新数组分配了多少额外空间，新数组现在容纳了旧列表和附加对象？

编辑 ：从评论中，我收集到这里有太多问题。我之所以这样做，是因为这些问题都很相关。不过，在这种情况下，我很乐意将其分成几篇文章（请在评论中告知我）

Answer 1

在C API文档的“内存管理”一章中可以回答很多问题。

有些文档比您要的要模糊。有关更多详细信息，您必须转向源代码。除非您选择特定版本，否则没有人会愿意这样做。（至少2.7.5、2.7.6之前，3.3.2、3.3.3之前和3.4之前的版本对不同的人很有趣。）

该obmalloc.c文件的源是许多问题的良好起点，并且顶部的注释中有一个漂亮的ASCII艺术图：

    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）级别上有各种通用的支持分配器-至少一个对象分配器，一个arena分配器和一个小块分配器，等等-
但除第一个以外的所有分配器都是私有的实现细节（甚至对于C-API都是专用的；显然，所有这些对于Python代码都是专用的）。

然后是原始分配器，其原始功能是在更高级别的分配器需要OS时向操作系统请求更多内存。

何时自动调用malloc？

原始内存分配器（或其堆管理器） 应该
是唯一调用过的东西malloc。（实际上，它甚至可能不一定要调用malloc；它可能使用诸如mmap或VirtualAlloc代替的函数。但是，重点是，这是有史以来唯一要求操作系统提供内存的东西。）Python内核中有一些例外，但它们很少有相关性。

文档明确指出，更高级别的代码绝不应尝试对从获得的内存中的Python对象进行操作malloc。

但是， 除了 Python对象 外 ，还有很多stdlib和扩展模块可malloc用于其他目的。 __

例如，一个1000x1000 int32值的numpy数组不会分配一百万个Python
int，因此它不必通过int分配器。相反，它只是malloc一百万个Cint的数组，并在访问它们时根据需要将它们包装在Python对象中。

python在启动时会为其分配多少内存？

这是特定于平台的，因此很难从代码中找出。但是，当我python3.3在64位Mac上启动新的解释器时，它的初始内存为13.1MB，然后几乎立即扩展为201MB。因此，这应该是一个粗略的指导。

是否有规则来控制哪些数据结构在此存储器上首先获得“特权”？

不是，不是 恶意的或错误的，特定于对象的分配器可能会立即抢占所有预分配的内存以及更多内容，没有阻止它的方法。

删除对象时，该对象使用的内存会发生什么变化（python将来是否仍会保留在内存中以分配给另一个对象，或者GC是否释放内存供其他进程使用，例如Google
Chrome） ？

它返回到特定于对象的分配器，该对象可以将其保留在空闲列表中，或者将其释放到保留其自己的空闲列表的原始分配器。原始分配器几乎 永远不会
将内存释放回操作系统。

这是因为通常没有充分的理由将内存释放回现代OS。如果周围有大量未使用的页面，则操作系统的VM将在其他进程需要时将它们分页出去。当有 是
一个很好的理由，它几乎总是特定应用，以及最简单的解决方案是使用多个进程来管理庞大的短期内存需求。

GC何时触发？

这取决于您所说的“ GC”的含义。

CPython使用引用计数；每次释放对对象的引用时（通过重新绑定变量或集合中的插槽，使变量超出范围等），如果它是最后一个引用，则将立即清除它。在文档的“引用计数”部分对此进行了说明。

但是，重新计数存在一个问题：即使两个对象相互引用，即使所有外部引用都消失了，它们也仍然无法清除。因此，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（logN）个浪费，但这通常不是导致复制排序变慢的因素。