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

TLDR：6 项和 7 项字典文字对哈希表的大小进行了错误的预调整，然后在调整大小时将大小增加四倍。

当 CPython 2.7 计算字典文字时，在开始填充条目之前，它用于创建字典的操作码是BUILD_MAP。这需要一个参数，即 dict 将包含多少条目的提示，它使用它来预设 dict 的大小：

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

这样做的目的是最大限度地减少字典在创建过程中调整大小的次数，但由于它们没有考虑负载因子，因此它并不能完全消除调整大小。

正如源代码注释所示，_PyDict_NewPresized旨在“创建一个预先调整大小的新字典以容纳估计数量的元素”。创建的字典中哈希表的确切大小受到许多实现细节的影响，例如最小大小 ( #define PyDict_MINSIZE 8) 以及大小为 2 的幂的要求（以避免在实现中需要除法）。

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

当字典达到至少 2/3 时，会在插入时调整大小。对于 6 和 7 条目的字典文字，字典以 8 条目开始，因此在第 6 次插入时会发生调整大小。字典足够小，调整大小会使哈希表的大小增加四倍：

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

mp->ma_used是哈希表中已使用条目的数量，此时为 6。6 小于 50000，因此我们调用dictresize(mp, 4 * 6)，将哈希表的大小调整为 32 个条目，即大于 24 的最小 2 次方。

相比之下，对于 8 条目的字典文字，哈希表以 16 条目开始。字典在创建过程中不会达到 2/3 满，因此初始 16 条目哈希表在字典创建后仍然存在，并且生成的字典比 6 和 7 条目字典文字小。

Python 3 使用不同的增长策略以及其他 dict 实现更改，这就是您在 Python 3 中看到不同结果的原因。