Сохранение большого словаря в Python влияет на производительность приложения
У меня возникают трудности с пониманием (и в конечном итоге решением), почему наличие большого словаря в памяти делает создание других словарей дольше.
Здесь тестовый код, который я использую
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. Как это бывает, в моем реальном сценарии преобразование списка в кортежи разрешило проблему (никогда не было необходимости иметь списки, просто не думал об использовании кортежей), но мне все еще интересно, почему это быстрее.
Ответы
Ответ 1
"Создание словаря" на самом деле - красная селедка. То, что делает словарь в этом случае, имеет важное значение в том, что он создает сто тысяч новых 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 и как он эволюционировал с годами.
Так получилось, что сегодня (самые последние версии Python 2 и Python 3) прилагаются сильные усилия, чтобы освободить определенные кортежи и dicts от циклического 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
([([...],)],)
Для 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() -подобной функцией (для кортежа) по сравнению с двумя (для списка), независимо от количества элементов. Это может быть значительным для очень коротких последовательностей, но не для больших.
Ответ 2
Измените эту программу, чтобы проверить байт-код:
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
Возможно, это разница в формате строки, которая вызывает разницу, когда сбор мусора отключен.
