为什么 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 个元素），所以我们有无论如何到 re-overallocate，所以我们现在不要过度分配。也许甚至不会有另一个扩展。"

因此，对于 6 个元素，它分配 12 个点，对于 7 个元素，它分配 8 个点（最小过度分配为 4 的倍数）。相差4个点。一个点包含一个指向对象的指针，64 位 Python 需要 8 个字节。所以 7 个元素需要比 6 个元素少 4*8 = 32 个字节，这是您观察到的（120 字节 vs 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

构建一个空列表，然后extended by that tuple. It first resizes to make room for the elements. Which does this计算分配多少个点：

    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;

让我们在 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 = (newsize + (newsize >> 3) + 6) & ~3
    if newsize - oldsize > new_allocated - newsize:
        new_allocated = (newsize + 3) & ~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

再次从代码推理：

    /* Do not overallocate if the new size is closer to overallocated size
     * than to the old size.

newsize 7 更接近 12 而不是 0，因此它决定不过度分配（好吧，它确实过度分配到最接近的 4 的倍数，用于内存对齐并且因为这似乎运作良好）。

其背后的原因，如 Serhiy Storchaka 在 proposal 中所述：

It is common enough case if the list is created from a sequence of a known size and do not adds items anymore. Or if it is created by concatenating of few sequences. In such cases the list can overallocate a space which will never be used. [...] My idea, that if we adds several items at a time and need to reallocate an array, we check if the overallocated size is enough for adding the same amount of items next time. If it is not enough, we do not overallocate. [...] It will save a space if extend a list by many items few times.

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

关于最多两个元素的大小：它不使用元组和 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

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

        case TARGET(BUILD_LIST): {
            PyObject *list =  PyList_New(oparg);
            if (list == NULL)
                goto error;
            while (--oparg >= 0) {
                PyObject *item = POP();
                PyList_SET_ITEM(list, oparg, item);
            }
            PUSH(list);
            DISPATCH();
        }

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

Why is sys.getsizeof reporting bigger values for smaller lists?

python

list

sizeof

短篇小说：

长话短说：