为什么defaultdict(int)字典占用这么多内存？（以及其他简单的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"

这里发生了什么？此外，相比第一个脚本，这个类似的脚本需要运行数万年，并且使用的内存量也极高。

topKeys = range(16384)
keys = range(8192)
table = [(j,0) for k in topKeys for j in keys]

我猜测Python的整数可能是64位整数，这可能解释了其中一些问题，但是这些相对自然和简单的构造真的会产生如此巨大的开销吗？ 我猜这些脚本表明确实会有这样的情况，所以我的问题是：到底是什么导致了第一个脚本的高内存使用率和第二个脚本的长运行时间和高内存使用率，并且有没有办法避免这些成本？

编辑： Python 2.6.4在64位机器上运行。

编辑2：我可以看出来，初步估计我的表应该占用3 GB 16384 * 8192 *（12 + 12）字节，而且如果使用defaultdict负载因子强制它保留双倍的空间，则需要6GB。 然后，内存分配的低效会再次增加2倍。

那么我的剩下的问题是： 有没有办法让它以某种方式使用32位整数？

为什么我的第二个代码片段与第一个相比要花费很长时间？第一个大约需要一分钟，而我在80分钟后终止了第二个。

- user19511

---

你使用的是Python 2还是Python 3？这是32位机器还是64位机器？ - Daniel Stutzbach

一个描述你最终想要实现什么的说明会很有帮助。 - Daniel Stutzbach

@Daniel，注意内存使用情况。我认为64位是一个安全的假设。 ;) - Mike Graham

Answer 1

Python中的整数在内部表示为C longs（实际上比这更复杂），但这并不是您问题的根源。

最大的开销来自于您对字典的使用。（defaultdicts和dicts在此说明中大致相同）。字典使用哈希表实现，这很好，因为它可以快速查找相当通用的键。 （当您只需要查找顺序数字键时，这并不是必需的，因为它们可以以易于访问的方式布置。）

字典可以有比项更多的插槽。假设您有一个具有3倍于项数的插槽的字典。每个插槽都需要留出指向键和作为链表结尾的指针的空间。这是数字数量的6倍，加上您感兴趣的项目的所有指针。考虑到这些指针在您的系统上每个8字节，并且在这种情况下有16384个defaultdicts。粗略地估计一下，16384次出现*（8192个/次）* 7（指针/项目）* 8（字节/指针）= 7 GB。这还没有考虑您正在存储的实际数字（其中每个唯一数字本身都是Python字典），外部字典，numpy数组或Python正在跟踪的东西以尝试优化一些内容。

您的开销听起来比我想象的高一些，我很想知道那11GB是为整个进程还是只计算了表而计算的。无论如何，我预计这个dict-of-defaultdicts数据结构的大小将比numpy数组表示法大几个数量级。

至于“有没有避免这些成本的方法？”的答案是“使用numpy存储大型固定大小的连续数字数组，而不是字典！”您需要更具体和具体地说明为什么发现这种结构更好以获得最佳解决方案的建议。

- Mike Graham

---

11 GB 是针对整个进程的。 - user19511

那么你的意思是Python列表中这些值不应该占用太多空间？因为你提到了字典特定的评论？因为我的第二个代码片段也使用了大量的RAM。 - user19511

@dukhat，list和dict的实现方式非常不同。列表只能分配比其大小多两倍的内存，并且不需要为键等内容存储指针。但是，与使用numpy数组相比，保留列表仍将占用更多的内存。这是我们使用numpy数组的主要原因之一。 - Mike Graham

Answer 2

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

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

这将创建一个包含16384个defaultdict(int)的字典。字典本身有一定的开销: 字典对象本身在60到120字节之间(取决于您构建中指针和ssize_t的大小)。这只是对象本身；除非字典少于几个项，否则数据是一个单独的内存块，在12到24字节之间，并且始终填充了1/2到2/3。并且defaultdict会比普通字典多4到8个字节的额外存储空间。整数每个占用12个字节，虽然它们在可能的情况下被重复使用，但那段代码不会重复使用大部分整数。因此，实际上，在32位构建中，该片段将占用60 + (16384 * 12)*1.8(填充因子)字节的table字典，16384 * 64字节的作为值存储的defaultdicts，以及16384 * 12字节的整数。因此，这仅仅是占用1.5MB多一点的空间，而没有在您的defaultdicts中存储任何内容。而在64位构建中，它的大小将是32位构建的两倍。

然后你创建一个numpy数组，它实际上对内存相当保守：

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

这将对数组本身产生一定的开销，通常是Python对象开销加上数组的维度和类型等，但不会超过100字节，只对一个数组有效。然而，它确实在你的512MB中存储了16384*8192个int32。

然后，您有一种相当奇特的方式来填充这个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将在大块之间重复使用可用内存来存储defaultdicts，但总映射地址空间将是11GB。

- Thomas Wouters

Answer 3

Mike Graham给出了一个很好的解释，为什么字典会使用更多的内存，但我想解释一下为什么你的defaultdict表开始占用如此之多的内存。

现在设置defaultdict(DD)的方式是，每当你检索一个不在DD中的元素时，你会得到DD的默认值（对于你的情况是0），但是DD现在也会存储一个以前不在DD中的键，并且该键的默认值为0。我个人不喜欢这样，但事实就是这样。然而，这意味着在内部循环的每次迭代中，都会分配新的内存，这就是为什么它需要很长时间的原因。如果你改变以下行：

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

到

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

如果DDs中的键没有被分配默认值，那么内存就会一直保持在约540MB左右，这主要是为dat所分配的内存。尽管DDs对于稀疏矩阵来说还不错，但如果您需要的是稀疏矩阵，最好直接使用Scipy中的稀疏矩阵。

- Justin Peel

---

如果你按照那种方式改变循环，它也会花费更少的时间——因为所有的defaultdict都是空的，所以它什么也不会做 :) 自动创建对象并将其插入字典是defaultdict的目的，也是它被添加的原因。如果你不想它被插入，你真的不应该使用defaultdict（而应该使用一个具有一个__getitem__函数的自定义类，该函数恰好执行你想要的操作） 。 - Thomas Wouters

没错，但我不确定 OP 是否理解 DD 中正在发生的事情。就我个人而言，如果只是请求 DD 中不存在的键的值，则不应将该键添加到 DD 中。只有在尝试设置键时才应该添加，但这只是我的观点。 - Justin Peel

@Justin，考虑 foo = defaultdict(list) 和 foo[bar].append(baz) 的常见情况。 - Mike Graham

@Mike 那是很好的一点。我猜这样做是为了应对值为数组的defaultdict，但我仍然认为它会导致大量的内存混乱。 - Justin Peel

@Justin，dict有一个get方法可以实现你想要的defaultdict功能。defaultdict所做的比你想要的更简单、更一致，并且在我一直使用defaultdict以及通常看到它在实际应用中使用时，不会导致内存混乱。它并不是为了OP使用它的目的而设计的，因此我认为它的设计没有太大问题。 - Mike Graham

@Mike 是的，我在这里看到了几个问题，因为人们正在以这种方式使用defaultdict，所以给我留下了这样的印象。我确实知道dict的get方法。 - Justin Peel