18

This is a post inspired from this comment about how memory is allocated for objects in CPython. Originally, this was in the context of creating a list and appending to it in a for loop vis a vis a list comprehension.

So here are my questions:

  1. how many different allocaters are there in CPython?
    • what is the function of each?
  2. when is malloc acutally called? (a list comprehension may not result in a call to malloc, based on what's said in this comment
  3. How much memory does python allocate for itself at startup?
    1. are there rules governing which data structures get first "dibs" on this memory?
  4. What happens to the memory used by an object when it is deleted (does python still hold on to the memory to allocate to another object in the future, or does the GC free up the memory for another process, say Google Chrome, to use)?
  5. When is a GC triggered?
  6. lists are dynamic arrays, which means they need a contiguous piece of memory. This means that if I try to append an object into a list, whose underlying-C-data-structure array cannot be extended, the array is copied over onto a different part of memory, where a larger contiguous block is available. So how much space is allocated to this array when I initialize a list?
    • how much extra space is allocated to the new array, which now holds the old list and the appended object?

EDIT: From the comments, I gather that there are far too many questions here. I only did this because these questions are all pretty related. Still, I'd be happy to split this up into several posts if that is the case (please let me know to do so in the comments)

4

1 回答 1

28

C API 文档的内存管理章节中回答了大部分问题。

有些文档比您要求的要模糊。有关更多详细信息,您必须转到源代码。除非您选择特定版本,否则没有人愿意这样做。(至少 2.7.5、pre-2.7.6、3.3.2、pre-3.3.3 和 pre-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;它可能使用类似mmapor的函数VirtualAlloc。但关键是它是唯一向操作系统请求内存的东西。)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。所以,这应该是一个粗略的球场指南。

是否有规则管理哪些数据结构在此内存上首先获得“dib”?

不是真的,不。恶意或有缺陷的特定对象分配器可以立即获取所有预先分配的内存等等,没有什么可以阻止它。


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

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

这是因为通常没有充分的理由将内存释放回现代操作系统。如果您有大量未使用的页面,操作系统的虚拟机只会在另一个进程需要时将它们分页。如果有充分的理由,它几乎总是特定于应用程序,最简单的解决方案是使用多个进程来管理您巨大的短期内存需求。


什么时候触发 GC?

这取决于您所说的“GC”是什么意思。

CPython 使用引用计数;每次释放对对象的引用时(通过重新绑定集合中的变量或槽,让变量超出范围等),如果它是最后一个引用,它将立即被清除。这在文档的参考计数部分中进行了解释。

但是,引用计数存在一个问题:如果两个对象相互引用,即使所有外部引用都消失了,它们仍然不会被清除。因此,CPython 一直有一个循环收集器,它定期遍历对象,寻找相互引用但没有外部引用的对象的循环。(它有点复杂,但这是基本思想。)这在gc模块的文档中得到了充分的解释。收集器可以在您明确要求它时运行,当空闲列表变低时,或者当它很长时间没有运行时;这是动态的并且在某种程度上是可配置的,因此很难对“何时”给出具体的答案。


列表是动态数组,这意味着它们需要一块连续的内存。这意味着,如果我尝试将一个对象附加到一个列表中,而该列表的底层 C 数据结构数组无法扩展,则该数组将被复制到内存的不同部分,其中有更大的连续块可用。那么当我初始化一个列表时,这个数组分配了多少空间呢?

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

它也不是特别有趣。大多数列表要么永远不会扩展,要么扩展得远远超出原始大小,因此在开始时进行额外分配会浪费静态列表的内存,并且对大多数增长的列表没有多大帮助。所以,Python 玩得很保守。我相信它首先查看它的内部 freelist,它不比 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) 浪费,但这通常不是使复制排序变慢的因素。

于 2013-08-30T01:33:37.780 回答