python - 元组在 CPython 中是如何实现的？

Question

我一直在尝试了解 CPython 是如何在幕后实现的。 Python 是高级别的很好，但我不喜欢把它当作一个黑盒子。

考虑到这一点，如何实现元组？我看过 the source (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 的辅助数组，它存储每个给定长度的元组的链表长度，这样就不会超过这个上限。

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