Сохранение большого словаря в Python влияет на производительность приложения

17

У меня возникают трудности с пониманием (и в конечном итоге решением), почему наличие большого словаря в памяти делает создание других словарей дольше.

Вот тестовый код, который я использую

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)

Если я запускаю код как есть (сначала инициализируя sample_dict в Foo), а затем создавая тот же словарь еще 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]

Если, однако, я НЕ инициализирую sample_dict в Foo (комментируя 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]

Я заметил, что если я выключу сборщик мусора Python, вызывая gc.disable (), производительность не только улучшает ~ 5x, но и хранение большого словаря в 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

У меня есть 2 вопроса:

  • Почему отключение сборки мусора ускоряет создание словаря.
  • Как достичь даже производительности (с помощью Foo init и без него) без отключения сборки мусора.

Буду признателен за это.

Спасибо!

ОБНОВЛЕНО: После того, как Тим Петерс упомянул, что я создаю изменяемые объекты, я решил попытаться создать неизменяемые объекты (кортежи в моем случае) и voila - гораздо более быстрые результаты (то же самое с использованием 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

Я понимаю, что создание кортежей намного быстрее, чем создание списка, но почему использование словаря неизменных объектов не влияет на время, затраченное на сбор мусора? Являются ли неизменяемые объекты не задействованными в эталонном цикле?

Спасибо.

P.S. Как это бывает, в моем реальном сценарии преобразование списка в кортежи решило проблему (никогда не было необходимости иметь списки, просто не думал об использовании кортежей), но мне все еще интересно, почему это быстрее.     

задан barmaley 15.10.2013 в 23:42
источник

2 ответа

35

«Создание словаря» на самом деле - красная селедка. Что делает создание словаря в этом случае , так это то, что он создает сто тысяч новых 125-элементных списков. Поскольку списки могут быть задействованы в эталонных циклах, которые создают 12,5 миллионов элементов списка, циклическая сборка мусора CPython должна проверять всякий раз, когда она сканирует поколение, содержащее dict. Не имеет значения, что эти списки находятся в словарях, и только важно, чтобы они существовали.

Итак, то, что вы делаете, в значительной степени зависит от времени, затрачиваемого на циклическую сборку мусора Python. Не имеет особого значения, что вы продолжаете создавать больше dicts, важно только, чтобы вы создавали новые изменяемые объекты (которые могут быть задействованы в циклах) намного быстрее, чем вы уничтожаете старые изменчивые объекты. Это (избыток распределений по освобождению от дезактивации) является тем, что запускает циклический CPython gc).

Не так много, вы можете это сделать, увы. Программы, которые проходят через четко обозначенные фазы создания насыпей новых объектов, могут быть полезны, если отключить циклический gc на время . Не могу догадаться, относится ли это к вам.

А, забыли одно: dict в Foo делает такую ​​большую разницу, потому что Foo «прилипает». Все остальные создаваемые вами dicts отбрасываются сразу же после их создания (за это отвечает подсчет ссылок CPython), поэтому не добавляйте к времени, потребляемому циклическим gc. Но dict в Foo делает, потому что , что dict не исчезает. Измените свой цикл, чтобы добавить новые dicts в список, и вы увидите, что время увеличивается для каждого dict, затем падает много, затем снова поднимается и т. Д. Это отражает, что dicts переходит к более старым поколениям внутри циклического gc Python, так что часто проверяются циклическим gc. Это осложняется: -)

Подробнее?

Трудно быть более точным, потому что производительность циклического gc в определенных случаях зависит от гор деталей реализации, которые могут и делать изменения в выпусках.

Общие рекомендации по использованию «неизменяемых объектов», когда это возможно, основаны на довольно глубоком ;-) понимании того, как циклический gc реализуется в CPython, и как он развивается на протяжении многих лет.

Так получилось, что today (самые последние версии Python 2 и Python 3), прилагаются большие усилия, чтобы освободить определенные кортежи и dicts от циклического gc. Это может измениться. Специальная оболочка таких вещей не является бесплатной, поэтому решение о том, добавлять ли дополнительные трюки, как это, всегда является сложным балансирующим действием. Это более легкое решение для неизменных объектов, следовательно, совет двигаться к ним.

Кортежи и дикты не были специально обрезаны до самого конца 2008 года, как описано в в этом из трекера по проблеме Python .

И - удивление ;-) - это оказалось ужасным следствием производительности в редких случаях some , которые были исправлены

Отслеживаются кортежи изначально :

>>> 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 , чтобы он участвовал в цикле, потому что он и все его компоненты (на & amp; on, all the down) неизменяемы. Но 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() (для кортежа) по сравнению с двумя (для списка), независимо от количества элементов. Это может быть значительным для очень коротких последовательностей, но не для больших.

    
ответ дан Tim Peters 16.10.2013 в 00:00
источник
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        

Возможно, это разница в формате строки, которая вызывает разницу, когда сбор мусора отключен.

    
ответ дан Emil Davtyan 16.10.2013 в 00:22
источник