CPython内存分配 [英] CPython memory allocation
问题描述
这是一篇受此评论启发的帖子如何在CPython中为对象分配内存.最初，这是在创建列表并将其添加到for循环中以实现列表理解的上下文中.
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.
这是我的问题:
- CPython中有多少个不同的分配器?
- 每个功能是什么?
- how many different allocaters are there in CPython?
- what is the function of each?
- 是否有规则来控制哪些数据结构在此存储器上首先获得特权"?
list是动态数组，这意味着它们需要一块连续的内存.这意味着，如果我尝试将对象追加到无法扩展其基础C数据结构数组的列表中，则会将该数组复制到内存的不同部分，在该部分中可以使用较大的连续块.因此，当我初始化列表时，会为该数组分配多少空间?
- 为新数组分配了多少额外的空间，新数组现在容纳了旧列表和附加对象?
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)
推荐答案
C API文档的内存管理" 一章.
有些文档比您要的要模糊.有关更多详细信息，您必须转向源代码.除非您选择特定版本，否则没有人会愿意这样做. (至少2.7.5、2.7.6之前的版本，3.3.2、3.3.3之前的版本和3.4之前的版本对不同的人会很有趣.)
Some of the documentation is vaguer than you're asking for. For further details, you'd have to turn to the source code. And nobody's going to be willing to do that unless you pick a specific version. (At least 2.7.5, pre-2.7.6, 3.3.2, pre-3.3.3, and pre-3.4 would be interesting to different people.)
对于许多人来说， obmalloc.c 文件的来源是一个很好的起点您的问题，并且顶部的注释中有一个漂亮的ASCII艺术图:
The source to the obmalloc.c file is a good starting place for many of your questions, and the comments at the top have a nice little ASCII-art graph:
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中有多少个不同的分配器?
how many different allocaters are there in CPython?
根据文档，几个".您可以算出内建和stdlib类型中的那些，然后，如果确实需要，可以添加少数泛型的.但是我不确定它会告诉你什么. (这将是特定于版本的.IIRC，确切的数字甚至在3.3树中也发生了变化，因为进行了一种试验，即新型字符串应使用三个不同的分配器还是一个.)
According to the docs, "several". You could count up the ones in the builtin and stdlib types, then add the handful of generic ones, if you really wanted. But I'm not sure what it would tell you. (And it would be pretty version-specific. IIRC, the exact number even changed within the 3.3 tree, as there was an experiment with whether the new-style strings should use three different allocators or one.)
每个功能是什么?
what is the function of each?
级别3上的特定于对象的分配器用于值得优化的特定用例.正如文档所说:
The object-specific allocators at level +3 are for specific uses cases that are worth optimizing. As the docs say:
例如，整数对象在堆中的管理与字符串，元组或字典的管理不同，因为整数意味着不同的存储要求和速度/空间折衷.
For example, integer objects are managed differently within the heap than strings, tuples or dictionaries because integers imply different storage requirements and speed/space tradeoffs.
在此之下，在+2(以及+1.5甚至+2.5)级别上有各种通用的支持分配器-至少一个对象分配器，一个arena分配器和一个小块分配器，等等-但除首先是私有实现细节(意味着甚至对C-API都是私有的；显然，所有这些对于Python代码都是私有的).
Below that, there are various generic supporting allocators at level +2 (and +1.5 and maybe +2.5)—at least an object allocator, an arena allocator, and a small-block allocator, etc.—but all but the first are private implementation details (meaning private even to the C-API; obviously all of it is private to Python code).
然后是原始分配器，它的功能是在更高级别的分配器需要OS时要求操作系统提供更多的内存.
And below that, there's the raw allocator, whose function is to ask the OS for more memory when the higher-level allocators need it.
何时自动调用malloc?
when is malloc acutally called?
原始内存分配器(或其堆管理器)应该是曾经调用过malloc的唯一对象. (实际上，它甚至可能不一定调用malloc；它可能使用诸如mmap或VirtualAlloc之类的功能.但是，要点是，这是有史以来唯一要求操作系统提供内存的东西.) Python核心中的异常，但它们很少相关.
The raw memory allocator (or its heap manager) should be the only thing that ever calls malloc. (In fact, it might not even necessarily call malloc; it might use functions like mmap or VirtualAlloc instead. But the point is that it's the only thing that ever asks the OS for memory.) There are a few exceptions within the core of Python, but they'll rarely be relevant.
文档明确指出，更高级别的代码永远不要尝试对从malloc获取的内存中的Python对象进行操作.
The docs explicitly say that higher-level code should never try to operate on Python objects in memory obtained from malloc.
但是，有很多stdlib和扩展模块出于除 Python对象的目的而使用malloc.
However, there are plenty of stdlib and extension modules that use malloc for purposes besides Python objects.
例如，一个1000x1000 int32值的numpy数组不会分配一百万个Python int，因此它不必通过int分配器.相反，它只是一个由100万个C int组成的数组，并在访问它们时根据需要将它们包装在Python对象中.
For example, a numpy array of 1000x1000 int32 values doesn't allocate 1 million Python ints, so it doesn't have to go through the int allocator. Instead, it just mallocs an array of 1 million C ints, and wraps them up in Python objects as needed when you access them.
python在启动时会为其分配多少内存?
How much memory does python allocate for itself at startup?
这是特定于平台的，因此很难从代码中找出.但是，当我在64位Mac上启动新的python3.3解释器时，它从13.1MB的虚拟内存开始，几乎立即扩展到201MB.因此，这应该是一个粗略的指南.
This is platform-specific, and a bit hard to figure out from the code. However, when I launch a new python3.3 interpreter on my 64-bit Mac, it starts of with 13.1MB of virtual memory, and almost immediately expands to 201MB. So, that should be a rough ballpark guide.
是否有规则来控制哪些数据结构在此存储器上首先获得特权"?
are there rules governing which data structures get first "dibs" on this memory?
不是，不是.恶意的或有bug的对象特定的分配器可以立即获取所有预分配的内存，甚至更多，而且没有什么可以阻止它.
Not really, no. A malicious or buggy object-specific allocator could immediately grab all of the pre-allocated memory and more, and there's nothing to stop it.
删除对象时，该对象使用的内存会发生什么变化(python将来仍会保留在内存中以分配给另一个对象吗?GC是否会为其他进程释放内存，例如Google Chrome，使用)?
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)?
它返回到对象特定的分配器，该对象可以将其保留在自由列表中，或者将其释放到原始分配器，该原始分配器保留其自己的自由列表.原始分配器几乎从不将内存释放回操作系统.
It goes back to the object-specific allocator, which may keep it on a freelist, or release it to the raw allocator, which keeps its own freelist. The raw allocator almost never releases memory back to the OS.
这是因为通常没有充分的理由将内存释放回现代OS.如果周围有大量未使用的页面，则操作系统的VM会在其他进程需要时将它们分页出去.而且，当有充分的理由时，它几乎总是特定于应用程序的，最简单的解决方案是使用多个进程来管理您巨大的短期内存需求.
This is because there's usually no good reason to release memory back to a modern OS. If you have a ton of unused pages lying around, the OS's VM will just page them out if another process needs it. And when there is a good reason, it's almost always application-specific, and the simplest solution is to use multiple processes to manage your huge short-lived memory requirements.
何时触发GC?
When is a GC triggered?
这取决于您所说的"GC".
It depends on what you mean by "a GC".
CPython使用引用计数；每次释放对对象的引用时(通过重新绑定变量或集合中的插槽，使变量超出范围等)，如果它是最后一个引用，则将立即清除它.在文档的引用计数部分中对此进行了解释.
CPython uses refcounting; every time you release a reference to an object (by rebinding a variable or a slot in a collection, letting a variable go out of scope, etc.), if it was the last reference, it will be cleaned up immediately. This is explained in the Reference Counting section in the docs.
但是，重新计数存在一个问题:即使两个对象相互引用，即使所有外部引用都消失了，它们也不会被清除.因此，CPython一直都有一个循环收集器，该循环收集器会周期性地遍历对象，以查找相互引用但没有外部引用的对象的循环. (这有点复杂，但这是基本思想.)在 gc的文档中对此进行了充分说明. 模块.当您明确要求收集器，空闲列表变低或很长时间没有运行时，收集器便可以运行.这是动态的，并且在某种程度上是可配置的，因此很难给出何时"的具体答案.
However, there's a problem with refcounting: if two objects reference each other, even when all outside references go away, they still won't get cleaned up. So, CPython has always had a cycle collector that periodically walks objects looking for cycles of objects that reference each other, but have no outside references. (It's a little more complicated, but that's the basic idea.) This is fully explained in the docs for the gc module. The collector can run when you ask it to explicitly, when the freelists are getting low, or when it hasn't run in a long time; this is dynamic and to some extent configurable, so it's hard to give a specific answer to "when".
列表是动态数组，这意味着它们需要一块连续的内存.这意味着，如果我尝试将对象追加到无法扩展其基础C数据结构数组的列表中，则会将该数组复制到内存的不同部分，在该部分中可以使用较大的连续块.那么，当我初始化列表时，会为该数组分配多少空间?
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?
此代码大部分位于 listobject.c 中.情况很复杂;有很多特殊情况，例如timsort用于创建临时中间列表和非就地排序的代码.但是最终，一些代码决定了它需要N个指针的空间.
The code for this is mostly inside listobject.c. It's complicated; there are a bunch of special cases, like the code used by timsort for creating temporary intermediate lists and for non-in-place sorting. But ultimately, some piece of code decides it needs room for N pointers.
它也不是特别有趣.大多数列表从未扩展，或者扩展得远远超出原始大小，因此在开始时进行额外的分配会浪费静态列表的内存，而对于大多数增长中的列表并没有太大帮助.因此，Python保守起见.我认为它首先要查看其内部空闲列表，该内部空闲列表的大小不超过N指针(它可能还会合并相邻的释放列表存储；我不知道是否这样做)，因此它有时可能会整体占用一点空间，但通常没有.确切的代码应该在 PyList_New 中.
It's also not particularly interesting. Most lists are either never expanded, or expanded far beyond the original size, so doing extra allocation at the start wastes memory for static lists and doesn't help much for most growing lists. So, Python plays it conservative. I believe it starts by looking through its internal freelist that's not too much bigger than N pointers (it might also consolidate adjacent freed list storage; I don't know if it does), so it might overallocate a little bit occasionally, but generally it doesn't. The exact code should be in PyList_New.
无论如何，如果列表分配器的自由列表中没有空间，它会降到对象分配器中，依此类推.最终可能会达到0级，但通常不会.
At any rate, if there's no space in the list allocator's freelist, it drops down to the object allocator, and so on through the levels; it may end up hitting level 0, but usually it doesn't.
为新数组分配了多少额外的空间，新数组现在容纳了旧列表和附加对象?
how much extra space is allocated to the new array, which now holds the old list and the appended object?
这在 list_resize 中进行了处理，这很有趣部分.
This is handled in list_resize, and this is the interesting part.
避免list.append成为二次方的唯一方法是在几何上进行过度分配.太小因素(例如1.2)的总和浪费了最初的几次扩展所花费的太多时间.使用太大的因数(例如1.6)会浪费非常大的阵列太多的空间. Python通过使用从2.0开始但很快收敛到1.25左右的序列来处理此问题.根据3.3来源:
The only way to avoid list.append being quadratic is to over allocate geometrically. Overallocating by too small of a factor (like 1.2) wastes way too much time for the first few expansions; using too large of a factor (like 1.6) wastes way too much space for very large arrays. Python handles this by using a sequence that starts off at 2.0 but quickly converges toward somewhere around 1.25. According to the 3.3 source:
生长方式为:0、4、8、16、25、35、46、58、72、88，...
The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
您没有具体询问sorted，但是我知道这是提示您的原因.
You didn't ask specifically about sorted, but I know that's what prompted you.
请记住，timsort主要是合并排序，对于尚未排序的小子列表，则使用插入排序.因此，它的大多数操作都涉及分配一个大小约为2N的新列表，并释放两个大小约为N的列表.因此，复制时它的空间和分配效率几乎与就地相同.最多有O(log N)个浪费，但这通常不是导致复制排序变慢的因素.
Remember that timsort is primarily a merge sort, with an insertion sort for small sublists that aren't already sorted. So, most of its operations involve allocating a new list of about size 2N and freeing two lists of about size N. So, it can be almost as space- and allocation-efficient when copying as it would be in-place. There is up to O(log N) waste, but this usually isn't the factor that makes a copying sort slower.
这篇关于CPython内存分配的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
