python - 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 项 dict 字面量对哈希表进行了严重的预调整，然后在调整大小时将大小翻了四倍。

---

当 CPython 2.7 计算 dict 文字时，在它开始填充条目之前，它用于创建 dict 的操作码是 BUILD_MAP。这需要一个参数，即 dict 将包含多少条目的提示，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 旨在“创建一个预先调整大小的新字典以容纳估计的元素数量”。创建的 dict 中哈希表的确切大小受许多实现细节的影响，例如最小大小 (#define PyDict_MINSIZE 8) 和大小为 2 的幂的要求 (以避免在实现中需要划分)。

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

---

Dicts resize on insertion when they become at least 2/3 full.对于 6 项和 7 项 dict 文字，该 dict 以 8 个条目开始，因此在第 6 次插入时会发生调整大小。 dict 足够小，resize 是哈希表大小的四倍:

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

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

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

---

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