Python2 字典中的非单调内存消耗

Question

有人可以解释一下 CPython 2.7 中字典的这种非单调内存使用吗？

>>> import sys
>>> sys.getsizeof({})
280
>>> sys.getsizeof({'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5})
280
>>> sys.getsizeof({'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5, 'six': 6})
1048
>>> sys.getsizeof({'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5, 'six': 6, 'seven': 7})
1048
>>> sys.getsizeof({'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5, 'six': 6, 'seven': 7, 'e
ight': 8})
664
>>> sys.getsizeof({'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5, 'six': 6, 'seven': 7, 'e
ight': 8, 'nine': 9})
664

Python3在这里是合理的，它将{'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5, 'six': 6, 'seven': 7}的大小打印为480。

我在 Ubuntu 15.10 和 OS X 10.11 上试过了。

Answer 1

好吧，我试了一下，让我们看看：

dct = {'four': 3, 'three': 2, 'two': 1, 'one': 0}
print(sys.getsizeof(dct))                             # = 272
print(sys.getsizeof(dict(dct)))                       # = 272
print(sys.getsizeof({k: v for k, v in dct.items()}))  # = 272

dct = {'four': 3, 'three': 2, 'five': 4, 'two': 1, 'one': 0}
print(sys.getsizeof(dct))                             # = 272
print(sys.getsizeof(dict(dct)))                       # = 272
print(sys.getsizeof({k: v for k, v in dct.items()}))  # = 272

dct = {'six': 5, 'three': 2, 'two': 1, 'four': 3, 'five': 4, 'one': 0}
print(sys.getsizeof(dct))                             # = 1040
print(sys.getsizeof(dict(dct)))                       # = 656
print(sys.getsizeof({k: v for k, v in dct.items()}))  # = 1040

dct = {'seven': 6, 'six': 5, 'three': 2, 'two': 1, 'four': 3, 'five': 4, 'one': 0}
print(sys.getsizeof(dct))                             # = 1040
print(sys.getsizeof(dict(dct)))                       # = 656
print(sys.getsizeof({k: v for k, v in dct.items()}))  # = 1040

dct = {'seven': 6, 'six': 5, 'three': 2, 'two': 1, 'four': 3, 'five': 4, 'eight': 7, 'one': 0}
print(sys.getsizeof(dct))                             # = 656
print(sys.getsizeof(dict(dct)))                       # = 1040
print(sys.getsizeof({k: v for k, v in dct.items()}))  # = 1040

我不确定这里发生了什么样的优化，但我认为这是因为这些结构使用了不同的 "best-practices"。我的意思是什么时候为hash-table分配多少内存。例如，如果你有 11 个或更多元素，你会得到另一个奇怪的差异：

dct = {1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9, 10:10, 11:11}
print(sys.getsizeof(dct))                             # = 1808
print(sys.getsizeof(dict(dct)))                       # = 1040
print(sys.getsizeof({k: v for k, v in dct.items()}))  # = 1040

所以这可能只是某种内存消耗 "optimization" 当以不同的方式创建字典时，为什么在使用 6 或 7 个元素时对于文字语法存在这种非单调异常值：我不知道。也许一些内存优化出了问题，它分配了太多内存是一个错误？我还没有阅读源代码。

Answer 2

TLDR：6 项和 7 项 dict 字面值预定义哈希值 table 很糟糕，然后在调整大小时将大小增加四倍。

当 CPython 2.7 计算字典文字时，在开始填充条目之前，它用于创建字典的操作码是 BUILD_MAP。这需要一个参数，提示字典将包含多少条目，which it uses to presize the dict:

    TARGET(BUILD_MAP)
    {
        x = _PyDict_NewPresized((Py_ssize_t)oparg);
        PUSH(x);
        if (x != NULL) DISPATCH();
        break;
    }

这是为了尽量减少在创建期间调整 dict 大小的次数，但由于它们没有考虑负载因子，因此并没有完全消除调整大小。

如 source code comments 所示，_PyDict_NewPresized 旨在 "Create a new dictionary pre-sized to hold an estimated number of elements"。创建的字典中散列 table 的确切大小受许多实现细节的影响，例如最小大小 (#define PyDict_MINSIZE 8) 和大小为 2 的幂的要求（以避免实施中需要划分）。

对于最多 7 个条目的字典文字，_PyDict_NewPresized 初始化一个 8 条目的散列 table；对于 8 个条目，它初始化一个 16 条目的散列 table，因为它使用的调整大小例程总是选择比参数更大的容量。

Dicts resize on insertion when they become at least 2/3 full. 对于 6 项和 7 项字典文字，字典以 8 项开始，因此在第 6 次插入时会调整大小。 dict 足够小，调整大小是散列大小的四倍 table:

return dictresize(mp, (mp->ma_used > 50000 ? 2 : 4) * mp->ma_used);

mp->ma_used是散列table中使用的条目数，此时为6。 6 小于 50000，所以我们调用 dictresize(mp, 4 * 6)，它将散列 table 调整为 32 个条目，即大于 24 的最小 2 次方。

相比之下，对于 8 条目字典文字，散列 table 从 16 个条目开始。字典在创建期间不会变成 2/3 满，因此初始的 16 项哈希 table 在字典创建后仍然存在，并且生成的字典小于 6 项和 7 项字典文字。

Python 3 使用 different growth policy，以及其他 dict 实现更改，这就是为什么您在 Python 3.

中看到不同结果的原因

Python2 字典中的非单调内存消耗

Non-monotonic memory consumption in Python2 dictionaries

python

python-2.7

memory

cpython

python-internals