20

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

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

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 和不使用 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 碰巧的是,在我的实际场景中,将列表转换为元组解决了这个问题(从来不需要列表,只是没想过使用元组),但我仍然很好奇为什么它更快。

4

2 回答 2

40

“字典创作”在这里真的是一个红鲱鱼。在这种情况下,字典创建的相关之处在于它创建了十万个新的 125 元素列表。因为列表可能涉及引用循环,这会创建 1250 万个列表元素 CPython 的循环垃圾收集必须在扫描包含 dict 的代时进行检查。这些列表是否在字典中并不重要,重要的是它们是否存在。

因此,您所安排的主要是 Python 的循环垃圾收集所消耗的时间。继续创建更多 dicts 并不重要,重要的是创建新的可变对象(可能涉及循环)比销毁旧的可变对象快得多。那(分配超过释放)是触发 CPython 循环 gc 的原因)。

唉,你无能为力。经历了创建大量新对象的详细描述阶段的程序可以通过在 duration禁用循环 gc 来受益。不过,无法猜测这是否适用于您。

啊,忘了一个: dict in因为“坚持”Foo而产生了如此大的不同。Foo您创建的所有其他字典在构造后立即被丢弃(CPython 的引用计数负责),所以不要增加循环 gc 消耗的时间。但是 dict inFoo确实如此,因为那个dict 不会消失。更改循环以将新字典附加到列表中,您会看到每个字典的时间都增加了,然后下降了很多,然后又上升了,等等。这反映了字典在 Python 的循环 gc 中向老一代移动,所以被循环 gc 扫描的频率较低。它变得复杂;-)

更多细节?

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

尽可能使用“不可变对象”的一般建议是基于对 CPython 中如何实现循环 gc 以及多年来它如何发展的相当深入的理解。

碰巧的是,今天(Python 2 和 Python 3 的最新版本)正在努力将某些元组和字典从循环 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让它参与一个循环,因为它和它的所有组件(打开和打开,一直向下)都是不可变的。但t1仍需追踪!因为t1[0]是可变的,以后t1 可能是循环的一部分:

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

字典恰好使用了不同的策略。如果可能的话,它们是未跟踪的情况下创建的:

>>> 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

这很棘手,因为这样的 dict 仍然可以在以后成为循环的一部分!

>>> 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()与元素的数量无关。这对于非常短的序列可能很重要,但对于大型序列则不然。

于 2013-10-15T22:00:04.000 回答
4

像这样修改程序以检查字节码:

import time
import dis
import inspect

def create_dict():
    return {x:[x]*125 for x in xrange(0, 100000)}


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)
        dis.dis(inspect.currentframe().f_code)

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

这是输出:

dict_init in Foo took 0.44164 sec
 12           0 LOAD_GLOBAL              0 (time)
              3 LOAD_ATTR                1 (clock)
              6 CALL_FUNCTION            0
              9 STORE_FAST               0 (start)

 13          12 LOAD_GLOBAL              2 (create_dict)
             15 CALL_FUNCTION            0
             18 LOAD_GLOBAL              3 (Foo)
             21 STORE_ATTR               4 (sample_dict)

 14          24 LOAD_CONST               1 ('dict_init in Foo took {0} sec')
             27 LOAD_ATTR                5 (format)
             30 LOAD_GLOBAL              0 (time)
             33 LOAD_ATTR                1 (clock)
             36 CALL_FUNCTION            0
             39 LOAD_FAST                0 (start)
             42 BINARY_SUBTRACT     
             43 CALL_FUNCTION            1
             46 PRINT_ITEM          
             47 PRINT_NEWLINE       

 15          48 LOAD_GLOBAL              6 (dis)
             51 LOAD_ATTR                6 (dis)
             54 LOAD_GLOBAL              7 (inspect)
             57 LOAD_ATTR                8 (currentframe)
             60 CALL_FUNCTION            0
             63 LOAD_ATTR                9 (f_code)
             66 CALL_FUNCTION            1
             69 POP_TOP             
             70 LOAD_CONST               0 (None)
             73 RETURN_VALUE        
Run 0 took 0.641144 seconds
  1           0 LOAD_CONST               0 (-1)
              3 LOAD_CONST               1 (None)
              6 IMPORT_NAME              0 (time)
              9 STORE_NAME               0 (time)

  2          12 LOAD_CONST               0 (-1)
             15 LOAD_CONST               1 (None)
             18 IMPORT_NAME              1 (dis)
             21 STORE_NAME               1 (dis)

  3          24 LOAD_CONST               0 (-1)
             27 LOAD_CONST               1 (None)
             30 IMPORT_NAME              2 (inspect)
             33 STORE_NAME               2 (inspect)

  5          36 LOAD_CONST               2 (<code object create_dict at 0x1091396b0, file "dict.py", line 5>)
             39 MAKE_FUNCTION            0
             42 STORE_NAME               3 (create_dict)

  9          45 LOAD_CONST               3 ('Foo')
             48 LOAD_NAME                4 (object)
             51 BUILD_TUPLE              1
             54 LOAD_CONST               4 (<code object Foo at 0x10914c130, file "dict.py", line 9>)
             57 MAKE_FUNCTION            0
             60 CALL_FUNCTION            0
             63 BUILD_CLASS         
             64 STORE_NAME               5 (Foo)

 17          67 LOAD_NAME                6 (__name__)
             70 LOAD_CONST               5 ('__main__')
             73 COMPARE_OP               2 (==)
             76 POP_JUMP_IF_FALSE      186

 18          79 LOAD_NAME                5 (Foo)
             82 LOAD_ATTR                7 (dict_init)
             85 CALL_FUNCTION            0
             88 POP_TOP             

 19          89 SETUP_LOOP              94 (to 186)
             92 LOAD_NAME                8 (xrange)
             95 LOAD_CONST               6 (0)
             98 LOAD_CONST               7 (1)
            101 CALL_FUNCTION            2
            104 GET_ITER            
        >>  105 FOR_ITER                74 (to 182)
            108 STORE_NAME               9 (x)

 20         111 LOAD_NAME                0 (time)
            114 LOAD_ATTR               10 (clock)
            117 CALL_FUNCTION            0
            120 STORE_NAME              11 (start)

 21         123 LOAD_NAME                3 (create_dict)
            126 CALL_FUNCTION            0
            129 POP_TOP             

 22         130 LOAD_CONST               8 ('Run {0} took {1} seconds')
            133 LOAD_ATTR               12 (format)
            136 LOAD_NAME                9 (x)
            139 LOAD_NAME                0 (time)
            142 LOAD_ATTR               10 (clock)
            145 CALL_FUNCTION            0
            148 LOAD_NAME               11 (start)
            151 BINARY_SUBTRACT     
            152 CALL_FUNCTION            2
            155 PRINT_ITEM          
            156 PRINT_NEWLINE       

 23         157 LOAD_NAME                1 (dis)
            160 LOAD_ATTR                1 (dis)
            163 LOAD_NAME                2 (inspect)
            166 LOAD_ATTR               13 (currentframe)
            169 CALL_FUNCTION            0
            172 LOAD_ATTR               14 (f_code)
            175 CALL_FUNCTION            1
            178 POP_TOP             
            179 JUMP_ABSOLUTE          105
        >>  182 POP_BLOCK           
            183 JUMP_FORWARD             0 (to 186)
        >>  186 LOAD_CONST               1 (None)
            189 RETURN_VALUE        

也许是字符串格式的差异导致垃圾收集关闭时的差异。

于 2013-10-15T22:22:29.437 回答