在Python中保留大型字典会影响应用程序性能

Question

我在理解(并最终解决)为什么在内存中使用大型字典使得创建其他字典的时间更长时会遇到一些困难.

这是我正在使用的测试代码

import time
def create_dict():
    # return {x:[x]*125 for x in xrange(0, 100000)}
    return  {x:(x)*125 for x in xrange(0, 100000)}  # UPDATED: to use tuples instead of list of values


class Foo(object):
    @staticmethod
    def dict_init():
        start = time.clock()
        Foo.sample_dict = create_dict()
        print "dict_init in Foo took {0} sec".format(time.clock() - start)

if __name__ == '__main__':
    Foo.dict_init()
    for x in xrange(0, 10):
        start = time.clock()
        create_dict()
        print "Run {0} took {1} seconds".format(x, time.clock() - start)

如果我按原样运行代码(首先在Foo中初始化sample_dict),然后在循环中再次创建相同的字典10次,我得到以下结果:

dict_init in Foo took 0.385263764287 sec
Run 0 took 0.548807949139 seconds
Run 1 took 0.533209452471 seconds
Run 2 took 0.51916067636 seconds
Run 3 took 0.513130722575 seconds
Run 4 took 0.508272050029 seconds
Run 5 took 0.502263872177 seconds
Run 6 took 0.48867601998 seconds
Run 7 took 0.483109299676 seconds
Run 8 took 0.479019713488 seconds
Run 9 took 0.473174195256 seconds
[Finished in 5.6s]

但是,如果我没有初始化Foo中的sample_dict(注释掉Foo.dict_init())我在循环中的字典创建速度提高了近20%

Run 0 took 0.431378921359 seconds
Run 1 took 0.423696636179 seconds
Run 2 took 0.419630475616 seconds
Run 3 took 0.405130343806 seconds
Run 4 took 0.398099686921 seconds
Run 5 took 0.392837169802 seconds
Run 6 took 0.38799598399 seconds
Run 7 took 0.375133006408 seconds
Run 8 took 0.368755297573 seconds
Run 9 took 0.363273701371 seconds
[Finished in 4.0s]

我注意到如果我通过调用gc.disable()来关闭Python的垃圾收集器,性能不仅提高了~5倍,而且在Foo中存储大字典并没有什么不同.以下是禁用垃圾收集的结果:

dict_init in Foo took 0.0696136982496 sec
Run 0 took 0.113533445358 seconds
Run 1 took 0.111091241489 seconds
Run 2 took 0.111151620212 seconds
Run 3 took 0.110655722831 seconds
Run 4 took 0.111807537706 seconds
Run 5 took 0.11097510318 seconds
Run 6 took 0.110936170451 seconds
Run 7 took 0.111074414632 seconds
Run 8 took 0.110678488579 seconds
Run 9 took 0.111011066463 seconds

所以我有两个问题:

• 为什么禁用垃圾收集会加快字典创建速度
• 如何在不禁用垃圾回收的情况下实现均匀的性能(使用Foo init和w/o)

我很感激任何见解.

谢谢!

更新:在Tim Peters提到我正在创建可变对象之后,我决定尝试创建不可变对象(在我的情况下为元组)和瞧 - 更快,更快的结果(与使用gc和没有相同)

dict_init in Foo took 0.017769 sec
Run 0 took 0.017547 seconds
Run 1 took 0.013234 seconds
Run 2 took 0.012791 seconds
Run 3 took 0.013371 seconds
Run 4 took 0.013288 seconds
Run 5 took 0.013692 seconds
Run 6 took 0.013059 seconds
Run 7 took 0.013311 seconds
Run 8 took 0.013343 seconds
Run 9 took 0.013675 seconds

我知道元组创建比列表创建快得多,但为什么拥有不可变对象的字典不会影响垃圾收集所花费的时间？不可变对象是否不参与引用循环？

谢谢.

PS碰巧,在我的真实场景中,将列表转换为元组解决了问题(从来没有需要有列表,只是没有想到使用元组)但我仍然很好奇为什么它更快.

Answer 1

"字典创作"在这里真的是一个红色的鲱鱼.字典创建在这种情况下的作用是相关的是它创建了十万个新的125元素列表.因为列表可以参与引用循环,所以创建了1250万个列表元素,CPython的循环垃圾收集必须在扫描包含dict的生成时进行检查.这些列表在字典中并不重要,只有它们存在才重要.

所以你的计时时间主要是Python循环垃圾收集所消耗的时间.你继续创造更多的dicts并不特别重要,只有你创建新的可变对象(可能涉及周期)比你破坏旧的可变对象要快得多.那(分配超过解除分配)是触发CPython的循环gc的原因.

唉,你可以做的不多.通过在一段时间内禁用循环gc ,可以通过编辑创建新对象堆的良好描述阶段的程序.但是无法猜测这是否适用于你.

啊,忘记了Foo一句:因为Foo"四处乱窜",这个词汇会产生如此大的影响.您创建的所有其他dicts在构造后立即被丢弃(CPython的引用计数负责),因此不要增加循环gc消耗的时间.但该词典Foo确实如此,因为该词典并没有消失.更改你的循环以将新的dicts附加到列表中,你会看到每个dict的时间都会增加,然后会下降很多,然后再次上升等等.这反映了在Python的循环gc中移动到老一代的dicts,所以不太频繁地通过循环gc进行扫描.它变得复杂;-)

更多细节？

很难更精确,因为在特定情况下循环gc的性能取决于大量的实现细节,这些细节可以 - 并且确实 - 在不同版本中发生变化.

在可能的情况下使用"不可变对象"的一般建议是基于相当深刻的;-)理解循环gc在CPython中的实现方式,以及它多年来如何演变.

事实上,今天(Python 2和Python 3的最新版本)发生了很大的努力,以免豁免某些元组和dicc与循环gc.这可能会改变.特殊外壳这样的东西不是免费的,所以决定是否添加更多这样的技巧总是一个困难的平衡行为.对于不可变对象来说,这是一个更容易的决定,因此建议转向那些.

直到2008年末,元组和词汇都不是特殊的,如Python问题跟踪器中详述的那样.

并且 - 出乎意料;-) - 在一些罕见的情况下,结果会产生可怕的性能后果,这在2012年中期的更多特殊情况下得到了解决.

一些好消息是gc.is_tracked()添加了一个函数,因此您至少可以调查循环gc是否要扫描特定对象.以下是Python 2.7.5下的一些示例.无法保证他们会一直这样工作:

永远不会跟踪"标量"对象(没有内部指针) - 它们不可能处于循环中:

>>> import gc
>>> gc.is_tracked(4)
False
>>> gc.is_tracked("2323")
False

最初跟踪元组:

>>> t1 = ([1],)
>>> t2 = ((1.),)
>>> gc.is_tracked(t1), gc.is_tracked(t2)
(True, True)

但是,如果循环gc运行并确定元组是"一直向下"不可变的,它会解开该元组:

>>> gc.collect()
0
>>> gc.is_tracked(t1), gc.is_tracked(t2)
(True, False)

没有什么可以t2让它参与一个循环,因为它及其所有组件(on&on,一直向下)是不可变的.但t1仍需要跟踪!因为t1[0]是可变的,t1 可能是以后循环的一部分:

>>> t1
([1],)
>>> t1[0][0] = t1
>>> t1
([([...],)],)

一个不同的政策恰好用于dicts.他们创造了未经跟踪,如果可能的话:

>>> d = {1: [2]}
>>> gc.is_tracked(d)
True

因为该dict具有可变值,所以它可能在以后成为循环的一部分,因此必须由循环gc跟踪.

>>> d[1][0] = d
>>> d
{1: [{...}]}

但是未跟踪密钥和值的dict是未跟踪的:

>>> d = {1: 2}
>>> gc.is_tracked(d)
False

这很棘手,因为这样的词典后来仍然可以成为一个循环的一部分!

>>> d[2] = d
>>> gc.is_tracked(d)
True

检测到这些变化并不是免费的.

然后有以上组合:

>>> d = {(1, 2): (4, "abc", 5)}
>>> gc.is_tracked(d)
True
>>> gc.collect()
3
>>> gc.is_tracked(d)
False

在这种情况下,d首先跟踪,因为它的键和值(元组)首先被跟踪创建.但是在第一次循环gc运行之后,它确定键和值"一直都是不可变的",所以要解开dict.

就像我说的,它变得复杂;-)

顺便说一句,

我知道元组创建比列表创建快得多

创建列表应该稍微慢一些.列表和元组在CPython中具有非常相似的实现.元组需要更少的内存(对于非常短的序列,这可能是显着的,以百分比表示),并且索引元组比列表快一些.但创作时间？它是一个malloc()类似函数(对于一个元组)与两个(对于一个列表)之间的区别,与元素的数量无关.这对于非常短的序列可能很重要,但对于大序列则不然.