如何在CPython中实现元组？

Question

我一直在尝试学习如何在场景下实现CPython。Python是高级的，这很好，但是我不喜欢将其视为黑匣子。

考虑到这一点，元组如何实现？我已经看过源代码（tupleobject.c），但它已经超出我的头了。

我看到的PyTuple_MAXSAVESIZE = 20和PyTuple_MAXFREELIST = 2000，什么是节约型和“自由列表”？（长度为20/21或2000/2001的元组之间会有性能差异吗？是什么导致了最大元组长度的强制执行？）

Answer 1

请注意，此答案中的所有内容都是基于我从查看所链接的实现中所获得的信息。

似乎元组的标准实现只是简单地作为一个数组。但是，有很多优化措施可以加快处理速度。

首先，如果您尝试制作一个空元组，则CPython会交出代表该空元组的规范对象。结果，它可以节省仅分配单个对象的大量分配。

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

自由列表本身实现为一个大小数组，PyTuple_MAXSAVESIZE用于存储指向未使用的元组的指针，其中数组的第n个元素指向NULL（如果没有大小为n的额外元组可用）或指向大小为n的回收元组。如果存在多个可重复使用的大小为n的不同元组，则通过使每个元组的第零入口指向下一个可重复使用的元组，将它们链接在一起形成一种链表。（由于仅分配了一个长度为零的元组，因此永远不会存在读取不存在的第零个元素的风险）。这样，分配器可以存储每种大小的一些元组以供重用。为了确保这不会占用太多内存，请使用第二个常量PyTuple_MAXFREELIST）来控制任何存储桶中任何这些链接列表的最大长度。然后有一个辅助长度数组，PyTuple_MAXSAVESIZE用于存储每个给定长度的元组的链表的长度，以便不超过此上限。

总而言之，这是一个非常聪明的实现！

希望这可以帮助！