Python2词典中的非单调记忆消耗

Question

有人能解释一下cpython2.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。你知道吗

我在Ubuntu15.10和OSX10.11上试过这个。你知道吗

Answer 1

TLDR:6和7条目的dict文本严重地预先设置了哈希表的大小，然后在resize时将大小增加了四倍。你知道吗

---

当cpython2.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个条目的哈希表，因为它使用的resize例程总是选择一个大于参数的容量。你知道吗

---

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 literal，哈希表从16个条目开始。dict在创建过程中不会变为2/3满，因此初始的16个条目的哈希表在dict创建过程中仍然有效，并且生成的dict小于6个条目和7个条目的dict文本。你知道吗

---

python3使用了different growth policy，以及其他dict实现更改，这就是为什么在python3中看到不同的结果。你知道吗

Answer 2

我试过一点，让我们看看：

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

我不确定这里发生了什么样的优化，但我认为这是因为这些结构使用不同的“最佳实践”。我的意思是什么时候为哈希表分配多少内存，。例如，如果有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

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