为什么defaultdict（int）的dict使用这么多内存？（以及其他简单的python性能问题）

Question

我知道，像我这样查询defaultdict中不存在的键会向defaultdict添加项。这就是为什么在性能方面比较我的第二个代码片段和第一个代码片段是公平的。在

import numpy as num
from collections import defaultdict

topKeys = range(16384)
keys = range(8192)

table = dict((k,defaultdict(int)) for k in topKeys)

dat = num.zeros((16384,8192), dtype="int32")

print "looping begins"
#how much memory should this use? I think it shouldn't use more that a few
#times the memory required to hold (16384*8192) int32's (512 mb), but
#it uses 11 GB!
for k in topKeys:
    for j in keys:
        dat[k,j] = table[k][j]

print "done"

这是怎么回事？此外，与第一个脚本相比，这个类似的脚本运行时间长达数年之久，而且还使用了荒谬的内存量。在

^{pr2}$

我猜python int可能是64位的int，这可能是其中的一部分，但是这些相对自然和简单的构造真的会产生如此巨大的开销吗？ 我想这些脚本表明了它们的存在，所以我的问题是：到底是什么导致第一个脚本的内存使用率高，第二个脚本的运行时间长和内存使用率高，有没有办法避免这些开销？在

编辑： 64位计算机上的Python2.6.4。在

编辑2：我明白为什么，按照第一个近似值，我的表应该占用3GB 16384*8192*（12+12）字节 以及6GB的defaultdict负载因子，强制它保留两倍的空间。 然后，内存分配的低效会消耗掉另一个因素2。在

下面是我剩下的问题： 有没有办法告诉它使用32位int？在

为什么我的第二个代码段与第一个代码段相比要花很长时间才能运行？第一个花了大约一分钟，我在80分钟后杀了第二个。在

Answer 1

Python int在内部表示为C long（实际上比这复杂一些），但这并不是问题的根源。在

最大的开销是你使用dicts。（defaultdict和dicts在本说明中大致相同）。dict是使用哈希表实现的，这很好，因为它可以快速查找非常一般的键。（当您只需要查找连续的数字键时，就没有必要了，因为它们可以以一种简单的方式进行布局以获得它们。）

一个dict可以有比它的项目更多的槽。假设你有一个dict，它的槽数是物品的3倍。每个插槽都需要一个指向键的指针和一个用作链表末尾的指针。这是数字的6倍，加上所有你感兴趣的项目的指针。考虑到系统上的每个指针都是8字节，在这种情况下有16384个defaultdict。粗略地看一下这个，16384 occurrences * (8192 items/occurance) * 7 (pointers/item) * 8 (bytes/pointer) = 7 GB。这是在我得到存储的实际数字之前（每个唯一的数字本身就是一个Python dict）、外部dict、numpy数组，或者Python为了优化一些而跟踪的内容。在

您的开销听起来比我猜想的要高一点，我很想知道11GB是用于整个进程还是仅为表计算的。无论如何，我确实希望这个dict of defaultdicts数据结构的大小比numpy数组表示大几个数量级。在

至于“有没有办法避免这些费用？”答案是“使用numpy存储大型、固定大小的连续数字数组，而不是dicts！”你必须更加具体和具体地解释为什么你认为这样的结构是必要的，以便更好地建议什么是最好的解决方案。在

Answer 2

mikegraham很好地解释了为什么字典使用更多的内存，但是我想我应该解释一下为什么defaultdicts的表dict开始占用这么多内存。在

现在设置defaultdict（DD）的方式是，每当您检索不在DD中的元素时，您将获得DD的默认值（对于您的案例，DD将存储一个以前不在DD中的键，默认值为0。我个人不喜欢这样，但事情就是这样的。然而，这意味着，对于内部循环的每次迭代，都会分配新的内存，这就是为什么它会一直占用。如果你改变路线

for k in topKeys:
    for j in keys:
        dat[k,j] = table[k][j]

到

^{pr2}$

然后默认值没有被分配给DDs中的键，因此内存对于我来说保持在540mb左右，这主要是为dat分配的内存。DDs对于稀疏矩阵来说是不错的，但是如果您想要的话，您可能应该在Scipy中使用稀疏矩阵。在

Answer 3

好吧，看看你的代码实际上在做什么：

topKeys = range(16384)
table = dict((k,defaultdict(int)) for k in topKeys)

这将创建一个包含16384defaultdict(int)的dict。dict有一定的开销：dict对象本身在60到120字节之间（取决于构建中指针和ssize的大小）。这只是对象本身；除非dict少于几个项，否则数据是一个单独的内存块，在12到24字节之间，并且总是在1/2到2/3之间填充。DefaultDict要大4到8个字节，因为它们有额外的东西要存储。int是12个字节，尽管在可能的情况下可以重用它们，但代码片段不会重用大部分。因此，实际上，在一个32位的构建中，该代码段将占用60 + (16384*12) * 1.8 (fill factor)字节作为tabledict，16384 * 64字节用于它存储为值的defaultdict，而{}字节用于整数。所以这只是超过1.5兆字节，而没有在defaultdicts中存储任何内容。这是一个32位的构建；一个64位的构建将是这个大小的两倍。在

然后创建一个numpy数组，这实际上在内存方面非常保守：

^{pr2}$

这会给数组本身带来一些开销，通常的Python对象开销加上数组的维数和类型等等，但是它不会超过100字节，而且只针对一个数组。不过，它确实将16384*8192int32存储在512Mb中。在

然后你有一种非常奇特的方法来填充这个numpy数组：

for k in topKeys:
    for j in keys:
        dat[k,j] = table[k][j]

这两个循环本身不占用太多内存，每次迭代都会重复使用。但是，table[k][j]为您请求的每个值创建一个新的Python整数，并将其存储在defaultdict中。创建的整数总是0，而且它总是被重用，但是存储对它的引用仍然会占用defaultdict中的空间：前面提到的每个条目的12个字节乘以填充因子（介于1.66和2之间），这使您在那里有接近3Gb的实际数据，而在64位的构建中则是6Gb。在

除此之外，由于您不断添加数据，defaultdicts必须不断增长，这意味着它们必须不断重新分配。由于Python的malloc前端（obmalloc）以及它如何在自己的块中分配较小的对象，以及进程内存在大多数操作系统上的工作方式，这意味着您的进程将分配更多而无法释放它；它实际上不会使用所有11Gb，Python将重新使用大块之间的可用内存作为defaultdict，但是总的映射地址空间将是11Gb。在