python - CPython内存分配

Question

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

所以这是我的问题：


CPython中有多少个不同的分配器？


每个的功能是什么？

malloc什么时候被正式调用？ （基于this comment中的说法，列表理解可能不会导致调用malloc
python在启动时会为其分配多少内存？


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

删除对象时，该对象使用的内存发生了什么（将来python是否仍保留在内存中以分配给另一个对象，或者GC是否释放内存供其他进程（例如Google Chrome浏览器使用）） ？
GC何时触发？
list是动态数组，这意味着它们需要一块连续的内存。这意味着，如果我尝试将对象追加到无法扩展其基础C数据结构数组的列表中，则会将该数组复制到内存的不同部分，在该部分中可以使用较大的连续块。那么，当我初始化列表时，会为该数组分配多少空间？


新数组分配了多少额外空间，新数组现在包含旧列表和附加对象？



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

Answer 1

在C API文档的Memory Management章节中可以回答很多问题。

有些文档比您要的要模糊。有关更多详细信息，您必须转向源代码。除非您选择特定版本，否则没有人会愿意这样做。 （至少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核心中的异常，但它们很少相关。

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

但是，除了Python对象之外，还有很多使用 malloc的stdlib和扩展模块。

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




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


这是特定于平台的，因此很难从代码中找出。但是，当我在64位Mac上启动新的 int解释器时，它以13.1MB的虚拟内存开始，并且几乎立即扩展到201MB。因此，这应该是一个粗略的指南。


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


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




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


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

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




GC何时触发？


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

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

但是，重新计数存在一个问题：即使两个对象相互引用，即使所有外部引用都消失了，它们也不会被清除。因此，CPython一直都有一个循环收集器，该循环收集器会定期遍历对象，以查找相互引用但没有外部引用的对象的循环。 （这有点复杂，但这是基本概念。）在 python3.3模块的文档中已对此进行了详细说明。当您要求显式收集器，空闲列表变低或长时间未运行时，收集器可以运行。这是动态的，并且在某种程度上是可配置的，因此很难给出“何时”的具体答案。




列表是动态数组，这意味着它们需要一块连续的内存。这意味着，如果我尝试将对象追加到无法扩展其基础C数据结构数组的列表中，则会将该数组复制到内存的不同部分，在该部分中可以使用较大的连续块。那么，当我初始化列表时，会为该数组分配多少空间？


此代码主要在 gc中。情况很复杂;有很多特殊情况，例如timsort用于创建临时中间列表和非就地排序的代码。但是最终，一些代码决定它需要N个指针的空间。

这也不是特别有趣。大多数列表都不会扩展，或者扩展得远远超出原始大小，因此在开始时进行额外的分配会浪费静态列表的内存，而对于大多数增长中的列表并没有太大帮助。因此，Python保守起见。我认为它首先要查看其内部空闲列表，该内部空闲列表的大小不超过N指针（它也可以合并相邻的释放列表存储；我不知道是否这样做），因此它有时可能会整体占用一点空间，但通常不。确切的代码应该在 listobject.c中。

无论如何，如果列表分配器的空闲列表中没有空间，它会下降到对象分配器中，依此类推。它可能最终达到0级，但通常不会。


新数组分配了多少额外空间，新数组现在包含旧列表和附加对象？


这在 PyList_New中处理，这是有趣的部分。

避免 list_resize二次方的唯一方法是在几何上进行过度分配。太小因素（例如1.2）的总体占用将浪费大量的时间进行前几次扩展。使用太大的因数（例如1.6）会浪费非常大的阵列太多的空间。 Python通过使用从2.0开始但很快收敛到1.25左右的序列来处理此问题。根据3.3资料来源：


增长模式是：0、4、8、16、25、35、46、58、72、88，...




您没有特别询问 list.append，但是我知道这是提示您的原因。

请记住，timsort主要是合并排序，而插入排序是针对尚未排序的小子列表。因此，它的大多数操作都涉及分配一个大小约为2N的新列表，并释放两个大小约为N的列表。因此，复制时它的空间和分配效率几乎与就地相同。最多有O（log N）个浪费，但这通常不是导致复制排序变慢的因素。