如何在CPython中实现元组？

Question

我一直在努力学习如何在幕后实现CPython.Python很高级很棒,但我不喜欢把它当成黑盒子.

考虑到这一点,元组是如何实现的？我已经看过了源码(tupleobject.c),但它已经过了我的脑海.

我看到的PyTuple_MAXSAVESIZE = 20和PyTuple_MAXFREELIST = 2000,什么是节约型和"自由列表"？(长度为20/21或2000/2001的元组之间是否存在性能差异？什么强制实现最大元组长度？)

Answer 1

因为在正常操作过程中,Python会创建并销毁许多小元组,Python会为此目的保留小元组的内部缓存.这有助于减少大量内存分配和重新分配流失.出于同样的原因,从-5到255的小整数被实习(制成单体).

该PyTuple_MAXSAVESIZE定义控制了符合此优化条件的元组的最大大小,并且该PyTuple_MAXFREELIST定义控制这些元组中有多少在内存中保留.当一个长度为<的元组PyTuple_MAXSAVESIZE被丢弃时,如果仍然存在一个(in tupledealloc)空间,则将其添加到空闲列表中,以便在Python创建新的小元组(in PyTuple_New)时重新使用.

Python对于如何存储这些内容有点聪明; 对于长度> 0的每个元组,它将重用每个缓存元组的第一个元素,将PyTuple_MAXFREELIST元组链接到一个链表中.因此,free_list数组中的每个元素都是Python元组对象的链接列表,并且这种链表中的所有元组都具有相同的大小.唯一的例外是空元组(长度为0); 只需要一个,这是一个单身人士.

所以,是的,对于超长的元组,PyTuple_MAXSAVESIZEpython保证必须为新的C结构分别分配内存,如果你创建和丢弃这样的元组,这可能会影响性能.

如果你想了解Python C内部,我建议你学习Python C API ; 它将使Python更容易理解用于在C中定义对象,函数和方法的各种结构.

Answer 2

作为一个警告,这个答案中的所有内容都是基于我从查看您链接的实现中收集到的内容.

似乎元组的标准实现只是一个数组.但是,有一堆优化措施可以加快速度.

首先,如果你尝试创建一个空元组,CPython将返回一个表示空元组的规范对象.因此,它可以节省大量仅分配单个对象的分配.

接下来,为了避免分配一堆小对象,CPython为许多小列表回收内存.有一个固定的constant(PyTuple_MAXSAVESIZE),这样所有小于这个长度的元组都有资格回收它们的空间.每当长度小于此常量的对象被释放时,有可能不会释放与其关联的内存,而是根据其大小将其存储在"空闲列表"中(在下一段中更多内容) .这样,如果您需要分配大小为n的元组,并且之前已经分配了一个并且不再使用,则CPython可以只回收旧数组.

空闲列表本身实现为一个大小数组,PyTuple_MAXSAVESIZE存储指向未使用元组的指针,其中数组的第n个元素指向NULL(如果没有大小为n的额外元组可用)或者返回给大小为n的回收元组.如果有多个大小为n的不同元组可以重复使用,则通过将每个元组的第0个入口指向可以重用的下一个元组,将它们链接在一个链表中.(由于只分配了一个长度为零的元组,因此不存在读取不存在的第零个元素的风险).通过这种方式,分配器可以存储每个大小的一些元组以供重用.为了确保不会占用太多内存,还有第二个常量PyTuple_MAXFREELIST来控制任何存储桶中任何链接列表的最大长度.然后存在一个长度的辅助数组,PyTuple_MAXSAVESIZE它存储每个给定长度的元组的链表长度,以便不超过该上限.

总而言之,这是一个非常聪明的实现!

希望这可以帮助!