Почему более скорое число мод на python вызывается с показателями экспоненты?
Я пытался оптимизировать программу, с которой я возился, когда заметил, что выполнение value = i % 65536 оказалось медленным, а затем value = i % (2**16).
Чтобы проверить это, я запустил следующую программу:
import cProfile
import pstats
AMOUNT = 100000000
def test1():
for i in xrange(AMOUNT):
value = i % 65536
return
def test2():
for i in xrange(AMOUNT):
value = i % (256**2)
return
def test3():
for i in xrange(AMOUNT):
value = i % (16**4)
return
def test4():
for i in xrange(AMOUNT):
value = i % (4**8)
return
def test5():
for i in xrange(AMOUNT):
value = i % (2**16)
return
def run_tests():
test1()
test2()
test3()
test4()
test5()
return
if __name__ == '__main__':
cProfile.run('run_tests()', 'results')
stats = pstats.Stats('results')
stats.sort_stats('calls', 'nfl')
stats.print_stats()
... который произвел следующий вывод:
Fri May 11 15:11:59 2012 results
8 function calls in 40.473 seconds
Ordered by: call count, name/file/line
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
1 0.000 0.000 40.473 40.473 <string>:1(<module>)
1 0.000 0.000 40.473 40.473 test.py:31(run_tests)
1 10.466 10.466 10.466 10.466 test.py:6(test1)
1 7.475 7.475 7.475 7.475 test.py:11(test2)
1 7.485 7.485 7.485 7.485 test.py:16(test3)
1 7.539 7.539 7.539 7.539 test.py:21(test4)
1 7.508 7.508 7.508 7.508 test.py:26(test5)
Использование 65536 было самым медленным на 10.466 секунд, тогда как 256**2 было самым быстрым на 7,475 секунды (с другими возможными значениями экспоненты, находящимися между ними). Разумеется, эта разница в скорости заметна только при большом количестве повторений, но мне все еще интересно, почему это происходит.
Почему количество мод на 65536 медленнее, чем при использовании мода, используя экспоненты? Они должны оценивать один и тот же номер, и я бы подумал, что интерпретатору python потребуется больше времени, чтобы полностью оценить экспоненты, прежде чем принимать мода.
Как правило, более эффективно использовать полномочия двух в выражениях python, а не полностью набирать номер? И этот шаблон справедлив для операций, кроме модуля или других чисел, кроме 2?
(Кстати, я использую Python 2.7.2 (32 бит), и я запустил выше на 64-битном ноутбуке Windows 7).
EDIT:
Поэтому я попытался изменить порядок функций, которые я называю, и теперь обратное верно. Похоже, что первая функция в run_tests всегда будет работать медленнее при использовании cProfile, что странно. Итак, урок, я думаю, - профайлеры странны: D
Ответы
Ответ 1
В сгенерированном байт-коде нет разницы, поскольку компилятор хорошо выполняет свою работу и оптимизирует постоянное арифметическое выражение. Это означает, что результаты вашего теста являются просто совпадением (попробуйте синхронизировать функции в другом порядке!).
>>> import dis
>>> dis.dis(test1)
2 0 SETUP_LOOP 30 (to 33)
3 LOAD_GLOBAL 0 (xrange)
6 LOAD_GLOBAL 1 (AMOUNT)
9 CALL_FUNCTION 1
12 GET_ITER
>> 13 FOR_ITER 16 (to 32)
16 STORE_FAST 0 (i)
3 19 LOAD_FAST 0 (i)
22 LOAD_CONST 1 (65536)
25 BINARY_MODULO
26 STORE_FAST 1 (value)
29 JUMP_ABSOLUTE 13
>> 32 POP_BLOCK
4 >> 33 LOAD_CONST 0 (None)
36 RETURN_VALUE
>>> dis.dis(test5)
2 0 SETUP_LOOP 30 (to 33)
3 LOAD_GLOBAL 0 (xrange)
6 LOAD_GLOBAL 1 (AMOUNT)
9 CALL_FUNCTION 1
12 GET_ITER
>> 13 FOR_ITER 16 (to 32)
16 STORE_FAST 0 (i)
3 19 LOAD_FAST 0 (i)
22 LOAD_CONST 3 (65536)
25 BINARY_MODULO
26 STORE_FAST 1 (value)
29 JUMP_ABSOLUTE 13
>> 32 POP_BLOCK
4 >> 33 LOAD_CONST 0 (None)
36 RETURN_VALUE
(ну на самом деле есть разница: число хранится при разных смещениях в таблице констант. Я не могу себе представить, что это может вызвать какую-либо разницу).
Для полноты, здесь правильный тест, который использует модуль timeit:
import timeit
setup = "i = 1337"
best1 = best2 = float("inf")
for _ in range(5000):
best1 = min(best1, timeit.timeit("i % 65536", setup=setup, number=10000))
for _ in range(5000):
best2 = min(best2, timeit.timeit("i % (2**16)", setup=setup, number=10000))
print best1
print best2
Обратите внимание, что я измеряю минимальное время, а не среднее. Если по какой-то причине это занимает больше времени, это просто означает, что он прерывался чаще (потому что код не зависит ни от чего, кроме мощности вашего процессора).
Ответ 2
Hmmm, используя dis, чтобы показать коды байтов python, показывает, что функции идентичны. Python оптимизировал константу (как и ожидалось). Поэтому я подозреваю, что разница во времени - это кеширующие эффекты. Тайминги на моем ноутбуке несут это (используя Python 2.7.3 64 бит на Linux)
Fri May 11 23:37:49 2012 results
8 function calls in 38.825 seconds
Ordered by: call count, name/file/line
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
1 0.000 0.000 38.825 38.825 <string>:1(<module>)
1 0.000 0.000 38.825 38.825 z.py:31(run_tests)
1 7.880 7.880 7.880 7.880 z.py:6(test1)
1 7.658 7.658 7.658 7.658 z.py:11(test2)
1 7.806 7.806 7.806 7.806 z.py:16(test3)
1 7.784 7.784 7.784 7.784 z.py:21(test4)
1 7.697 7.697 7.697 7.697 z.py:26(test5)
Все в значительной степени идентичны
>>> from dis import dis
>>> def test1():
... for i in xrange(AMOUNT):
... value = i % 65536
... return
...
>>> def test5():
... for i in xrange(AMOUNT):
... value = i % (2**16)
... return
...
>>> dis(test1)
2 0 SETUP_LOOP 30 (to 33)
3 LOAD_GLOBAL 0 (xrange)
6 LOAD_GLOBAL 1 (AMOUNT)
9 CALL_FUNCTION 1
12 GET_ITER
>> 13 FOR_ITER 16 (to 32)
16 STORE_FAST 0 (i)
3 19 LOAD_FAST 0 (i)
22 LOAD_CONST 1 (65536)
25 BINARY_MODULO
26 STORE_FAST 1 (value)
29 JUMP_ABSOLUTE 13
>> 32 POP_BLOCK
4 >> 33 LOAD_CONST 0 (None)
36 RETURN_VALUE
>>> dis(test5)
2 0 SETUP_LOOP 30 (to 33)
3 LOAD_GLOBAL 0 (xrange)
6 LOAD_GLOBAL 1 (AMOUNT)
9 CALL_FUNCTION 1
12 GET_ITER
>> 13 FOR_ITER 16 (to 32)
16 STORE_FAST 0 (i)
3 19 LOAD_FAST 0 (i)
22 LOAD_CONST 3 (65536)
25 BINARY_MODULO
26 STORE_FAST 1 (value)
29 JUMP_ABSOLUTE 13
>> 32 POP_BLOCK
4 >> 33 LOAD_CONST 0 (None)
36 RETURN_VALUE
>>>
Ответ 3
Вы проводите каждый тест только один раз. Скорость вашего процессора не всегда одинакова, в начале теста она скорее всего спала, и поэтому первый тест был медленнее. Для сравнения небольших частей кода (например, mod) используйте модуль timeit:
>>> timeit.timeit('for i in range(10000): i % 65536', number=1000)
0.8686108589172363
>>> timeit.timeit('for i in range(10000): i % 256**2', number=1000)
0.862062931060791
>>> timeit.timeit('for i in range(10000): i % 4**8', number=1000)
0.8644928932189941
>>> timeit.timeit('for i in range(10000): i % 2**16', number=1000)
0.8643178939819336
>>> timeit.timeit('for i in range(10000): i % 65536', number=1000)
0.8640358448028564
Вы можете видеть, что среднее значение всегда равно 0.864.
