为什么Python列出内存中的大小与文档不匹配？

Question

我一直在尝试更好地理解当列表通过追加扩展时，Python 如何为列表分配内存。这个问题很好地涵盖了基础知识，并解释了内存增量随着列表长度的增加而增加。这篇文章是对源代码的解释，可以在这里找到。

我想问一下这个解释：

/* This over-allocates proportional to the list size, making room
 * for additional growth.  The over-allocation is mild, but is
 * enough to give linear-time amortized behavior over a long
 * sequence of appends() in the presence of a poorly-performing
 * system realloc().
 * Add padding to make the allocated size multiple of 4.
 * The growth pattern is:  0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...
 * Note: new_allocated won't overflow because the largest possible value
 *       is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.
 */
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.
 */

具体来说，这个计算：

新分配 = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;

我对此计算的理解是，新的内存分配将等于 newsize （触发增加的当前大小）+ newsize 右滚三位（有效除以 8）+ 6。然后将其与 1 的补码进行 AND 运算3，因此最后两位强制为零以使该值可被 4 整除。

我使用此代码生成列表并报告尺寸：

a = [i for i in range(108)]
print(sys.getsizeof(a))  # 920 bytes

b = [i for i in range(109)]
print(sys.getsizeof(b))  # 1080 bytes

在 109 个元素处，触发调整大小，新大小现在等于 928 字节

上面的计算应该是这样的：

1048 字节小于报告的 1060 字节大小。

文档指出，此过程可能不适用于小列表，因此我尝试了更大的列表。我不会以二进制形式重现此内容。

a = [i for i in range(10640)]
print(sys.getsizeof(a))  # 85176 bytes

b = [i for i in range(10641)]
print(sys.getsizeof(b))  # 95864 bytes

[85184 + (86184 >> 3) + 6] = 95838 字节

当应用“& ~3”时，这将降至 95836。再次低于报告的 95864。

为什么报告的调整大小大于计算的调整大小？

Answer 1

我相信你的错误是你对字节进行了计算。您必须在元素上执行此操作，然后添加空列表对象的开销。

这是

[i for i in range(109)]

的快速模拟：

size = 0
used = 0
for _ in range(109):
    used += 1
    if used > size:
        size = (used + ((used >> 3) + 6)) & ~3

print(f"allocated array size: {size * 8}")
print(f"full list size: {size * 8 + sys.getsizeof([])}")
print(f"should be the same as {sys.getsizeof([i for i in range(109)])}")

分配的数组大小：1024

完整列表大小：1080

应该和1080一样