CPython内存分配

Question

这篇文章的灵感来自于关于如何在CPython中为对象分配内存的评论.原来,这是创建一个列表,并追加到它在一个for循环的环境相一相的列表理解.

所以这是我的问题:

1. CPython中有多少个不同的分配器？
   • 每个人的功能是什么？
2. 什么时候被malloc称为？(malloc根据本评论中的内容,列表理解可能不会导致调用
3. python在启动时为自己分配了多少内存？
   1. 是否有规则管理哪些数据结构在此内存中获得第一个"dibs"？
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)有各种通用的支持分配器 - 至少是一个对象分配器,一个竞技场分配器和一个小块分配器等等 - 但除了第一个之外的所有都是私有的实现细节(即使对于C-API也是私有的;显然所有这些都是Python代码专用的).

在此之下,还有原始分配器,其功能是在更高级别的分配器需要时向操作系统请求更多内存.

什么时候被malloc称为？

原始内存分配器(或其堆管理器)应该是唯一可以调用的东西malloc.(事实上​​,它甚至可能不一定要调用malloc;它可能会使用类似mmap或VirtualAlloc相反的函数.但重点是它是唯一要求操作系统获取内存的东西.)Python的核心内部有一些例外,但它们是很少有相关性.

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

但是,除了 Python对象之外,还有许多malloc用于目的的stdlib和扩展模块.

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

python在启动时为自己分配了多少内存？

这是特定于平台的,有点难以从代码中找出.但是,当我python3.3在我的64位Mac上启动一个新的解释器时,它启动了13.1MB的虚拟内存,几乎立即扩展到201MB.所以,这应该是一个粗略的棒球场指南.

是否有规则管理哪些数据结构在此内存中获得第一个"dibs"？

不是,不是.恶意或错误的特定于对象的分配器可以立即获取所有预先分配的内存以及更多,并且没有什么可以阻止它.

对象在被删除时使用的内存会发生什么变化(python仍然保留在内存中以便将来分配给另一个对象,或者GC是否为另一个进程释放内存,比如Google Chrome,要使用) ？

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

这是因为通常没有充分的理由将内存释放回现代操作系统.如果您周围有大量未使用的页面,则操作系统的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(log N)浪费,但这通常不是使复制排序变慢的因素.