为什么 sys.getsizeof 为较小的列表报告较大的值？

Question

我不明白当两个列表都像文字一样创建时， sizeof 的行为有何不同。我希望第二个 sizeof 的输出等于或小于第一个 sizeof 的输出，而不是更大！

>>> sys.getsizeof([0,1,2,3,4,5,6])
120
>>> sys.getsizeof([0,1,2,3,4,5])
152

Answer 1

短篇故事：

这是关于过度分配和避免无用的过度分配。您的案例有 6 个和 7 个要素。在这两种情况下，Python 首先计算 12 作为要分配的位置数量。过度分配的目的是允许未来快速扩展更多元素，因此 Python 尝试猜测未来会发生什么并采取相应的行动。

对于 6 个元素的情况，它认为“嗯，如果我们要添加另外 6 个元素，那么已经有 12 个位置确实很好，所以我们现在就这样做。”

对于 7 个元素的情况，它认为“嗯，如果我们要添加另外 7 个元素，那么 12 个位置无论如何都不够（对于 14 个元素），所以无论如何我们都必须重新过度分配，所以我们不要现在就过度分配了。也许甚至不会再有一次延期。”

因此，对于 6 个元素，它分配 12 个位置，对于 7 个元素，它分配 8 个位置（最小过度分配为 4 的倍数）。这就是4个点的差距。一个点保存一个指向对象的指针，在 64 位 Python 中该指针占用 8 个字节。因此，7 个元素比 6 个元素需要少 4*8 = 32 个字节，这就是您观察到的结果（120 字节与 152 字节）。

很长的故事：

我可以在 CPython 3.10.0 中重现它。发生的情况如下：

>>> import dis
>>> dis.dis('[0,1,2,3,4,5,6]')
  1           0 BUILD_LIST               0
              2 LOAD_CONST               0 ((0, 1, 2, 3, 4, 5, 6))
              4 LIST_EXTEND              1
              6 RETURN_VALUE

构建一个空列表，然后通过该元组进行扩展。它首先调整大小以为元素腾出空间。这是为了计算要分配多少个位置：

>>> import dis
>>> dis.dis('[0,1,2,3,4,5,6]')
  1           0 BUILD_LIST               0
              2 LOAD_CONST               0 ((0, 1, 2, 3, 4, 5, 6))
              4 LIST_EXTEND              1
              6 RETURN_VALUE

让我们用 Python 来测试一下：

>>> for newsize in range(10):
...     new_allocated = (newsize + (newsize >> 3) + 6) & ~3
...     if newsize - oldsize > new_allocated - newsize:
...         new_allocated = (newsize + 3) & ~3
...     s = f'[{",".join(map(str, range(newsize)))}]'
...     calculated_size = sys.getsizeof([]) + 8 * new_allocated
...     actual_size = sys.getsizeof(eval(s))
...     print(f'{s:20}  {calculated_size=}  {actual_size=}')
... 
[]                    calculated_size=88  actual_size=56
[0]                   calculated_size=88  actual_size=64
[0,1]                 calculated_size=120  actual_size=72
[0,1,2]               calculated_size=120  actual_size=120
[0,1,2,3]             calculated_size=120  actual_size=120
[0,1,2,3,4]           calculated_size=120  actual_size=120
[0,1,2,3,4,5]         calculated_size=152  actual_size=152
[0,1,2,3,4,5,6]       calculated_size=120  actual_size=120
[0,1,2,3,4,5,6,7]     calculated_size=120  actual_size=120
[0,1,2,3,4,5,6,7,8]   calculated_size=152  actual_size=152

我们计算的尺寸与实际尺寸相符。除了少于三个元素之外，但那是因为它们不是通过这样的扩展创建的（我将在最后展示），所以我们的公式不适用于此处也就不足为奇了。

我们再看一下代码：

    new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;
    /* Do not overallocate if the new size is closer to overallocated size
     * than to the old size.
     */
    if (newsize - Py_SIZE(self) > (Py_ssize_t)(new_allocated - newsize))
        new_allocated = ((size_t)newsize + 3) & ~(size_t)3;

以及您的案例的值：

              [0,1,2,3,4,5]    [0,1,2,3,4,5,6]

oldsize             0                 0
newsize             6                 7
new_allocated      12                12
    corrected      12                 8

再次从代码中推理：

>>> for newsize in range(10):
...     new_allocated = (newsize + (newsize >> 3) + 6) & ~3
...     if newsize - oldsize > new_allocated - newsize:
...         new_allocated = (newsize + 3) & ~3
...     s = f'[{",".join(map(str, range(newsize)))}]'
...     calculated_size = sys.getsizeof([]) + 8 * new_allocated
...     actual_size = sys.getsizeof(eval(s))
...     print(f'{s:20}  {calculated_size=}  {actual_size=}')
... 
[]                    calculated_size=88  actual_size=56
[0]                   calculated_size=88  actual_size=64
[0,1]                 calculated_size=120  actual_size=72
[0,1,2]               calculated_size=120  actual_size=120
[0,1,2,3]             calculated_size=120  actual_size=120
[0,1,2,3,4]           calculated_size=120  actual_size=120
[0,1,2,3,4,5]         calculated_size=152  actual_size=152
[0,1,2,3,4,5,6]       calculated_size=120  actual_size=120
[0,1,2,3,4,5,6,7]     calculated_size=120  actual_size=120
[0,1,2,3,4,5,6,7,8]   calculated_size=152  actual_size=152

newsize 7更接近 12，而不是 0，因此它决定不过度分配（好吧，它确实过度分配到最接近的 4 的倍数，以进行内存对齐，并且因为这看起来效果很好）。

正如 Serhiy Storchaka 在提案中所述，其背后的原因是：

2. 如果列表是根据已知大小的序列创建的并且不再添加项目，这是很常见的情况。或者如果它是通过连接几个序列创建的。在这种情况下，列表可能会过度分配永远不会使用的空间。[...] 我的想法是，如果我们一次添加多个项目并需要重新分配一个数组，我们会检查过度分配的大小是否足以下次添加相同数量的项目。如果还不够，我们不会过度分配。[...] 如果多次扩展列表中的许多项目，将会节省空间。

因此，我们的想法是考虑未来相同规模的增长，如果下一次增长无论如何都需要新的过度分配，那么当前的过度分配将无济于事，所以我们不要这样做。

关于最多两个元素的大小：不使用元组，而是LIST_EXTEND将各个值放入堆栈并直接构建列表BUILD_LIST（注意其参数 0、1 或 2）：

dis.dis('[]')
  1           0 BUILD_LIST               0
              2 RETURN_VALUE
dis.dis('[1969]')
                    
  1           0 LOAD_CONST               0 (1969)
              2 BUILD_LIST               1
              4 RETURN_VALUE
dis.dis('[1969, 1956]')
                    
  1           0 LOAD_CONST               0 (1969)
              2 LOAD_CONST               1 (1956)
              4 BUILD_LIST               2
              6 RETURN_VALUE

要执行的BUILD_LIST代码会构建一个新的列表对象，其中包含所需的确切数量的点（数量oparg：0、1 或 2），没有过度分配。然后就在那里，它只使用一个快速的小循环将值从堆栈中弹出并将它们放入列表中：

    new_allocated = (newsize + (newsize >> 3) + 6) & ~3
    if newsize - oldsize > new_allocated - newsize:
        new_allocated = (newsize + 3) & ~3