Почему код, использующий промежуточные переменные, быстрее, чем код без него?

Ответ 1

Мои результаты были схожи с вашими: код, использующий промежуточные переменные, был довольно последовательным, по крайней мере, на 10-20% быстрее в Python 3.4. Однако когда я использовал IPython на том же интерпретаторе Python 3.4, я получил следующие результаты:

In [1]: %timeit -n10000 -r20 tuple(range(2000)) == tuple(range(2000))
10000 loops, best of 20: 74.2 µs per loop

In [2]: %timeit -n10000 -r20 a = tuple(range(2000));  b = tuple(range(2000)); a==b
10000 loops, best of 20: 75.7 µs per loop

Примечательно, что мне никогда не удавалось приблизиться к 74,2 мкс для первого, когда я использовал -mtimeit из командной строки.

Так что этот Гейзенбаг оказался довольно интересным. Я решил запустить команду с помощью strace и действительно происходит что-то подозрительное:

% strace -o withoutvars python3 -m timeit "tuple(range(2000)) == tuple(range(2000))"
10000 loops, best of 3: 134 usec per loop
% strace -o withvars python3 -mtimeit "a = tuple(range(2000));  b = tuple(range(2000)); a==b"
10000 loops, best of 3: 75.8 usec per loop
% grep mmap withvars|wc -l
46
% grep mmap withoutvars|wc -l
41149

Это хорошая причина для разницы. Код, который не использует переменные, вызывает системный вызов mmap почти в 1000 раз больше, чем тот, который использует промежуточные переменные.

В withoutvars полно mmap/munmap для области 256 munmap; эти же строки повторяются снова и снова:

mmap(NULL, 262144, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f32e56de000
munmap(0x7f32e56de000, 262144)          = 0
mmap(NULL, 262144, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f32e56de000
munmap(0x7f32e56de000, 262144)          = 0
mmap(NULL, 262144, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f32e56de000
munmap(0x7f32e56de000, 262144)          = 0

Кажется, что вызов mmap исходит из функции _PyObject_ArenaMmap из Objects/obmalloc.c; obmalloc.c также содержит макрос ARENA_SIZE, который равен #define d (256 << 10) (то есть 262144); аналогично, munmap совпадает с _PyObject_ArenaMunmap из obmalloc.c.

obmalloc.c говорит, что

До Python 2.5 арены никогда не были free(). Начиная с Python 2.5, мы пытаемся free() арены free() и используем некоторые умеренные эвристические стратегии, чтобы увеличить вероятность того, что арены в конечном итоге могут быть освобождены.

Таким образом, эти эвристики и тот факт, что распределитель объектов Python освобождает эти свободные арены, как только они python3 -mtimeit 'tuple(range(2000)) == tuple(range(2000))' приводят к python3 -mtimeit 'tuple(range(2000)) == tuple(range(2000))' вызывающему патологическое поведение, когда Область памяти 256 КБ перераспределяется и высвобождается повторно; и это распределение происходит с mmap/munmap, что сравнительно дорого, поскольку они являются системными вызовами - более того, mmap с MAP_ANONYMOUS требует, чтобы вновь отображаемые страницы были обнулены - даже если Python это не заботит.

Такое поведение отсутствует в коде, который использует промежуточные переменные, потому что он использует немного больше памяти, и никакая область памяти не может быть освобождена, поскольку некоторые объекты все еще размещены в ней. Это потому, что timeit превратит его в петлю

for n in range(10000)
    a = tuple(range(2000))
    b = tuple(range(2000))
    a == b

Теперь поведение таково, что и a и b будут оставаться связанными до тех пор, пока они не будут * переназначены, поэтому во второй итерации tuple(range(2000)) выделит 3-й кортеж, а присваивание a = tuple(...) будет уменьшить счетчик ссылок старого кортежа, вызывая его освобождение, и увеличить счетчик ссылок нового кортежа; то же самое происходит с b. Поэтому после первой итерации всегда есть как минимум 2 из этих кортежей, если не 3, поэтому перебрасывание не происходит.

В частности, нельзя гарантировать, что код, использующий промежуточные переменные, всегда быстрее - в некоторых случаях может случиться так, что использование промежуточных переменных приведет к дополнительным вызовам mmap, тогда как код, который сравнивает возвращаемые значения напрямую, может подойти.

Кто-то спросил, почему это происходит, когда timeit отключает сборку мусора. Это правда, что timeit делает это:

Заметка

По умолчанию timeit() временно отключает сборку мусора во время синхронизации. Преимущество этого подхода в том, что он делает независимые тайминги более сопоставимыми. Этот недостаток заключается в том, что ГХ может быть важным компонентом производительности измеряемой функции. Если это так, GC может быть повторно включен как первый оператор в строке установки. Например:

Однако сборщик мусора в Python предназначен только для восстановления циклического мусора, то есть коллекций объектов, ссылки на которые образуют циклы. Это не тот случай здесь; вместо этого эти объекты освобождаются немедленно, когда счетчик ссылок падает до нуля.

Ответ 2

Первый вопрос должен быть, он воспроизводимый? Для некоторых из нас, по крайней мере, это определенно, хотя другие люди говорят, что они не видят эффекта. Это на Fedora с тестом равенства, которое изменилось на is, поскольку фактическое выполнение сравнения кажется неуместным для результата, а диапазон подталкивает до 200 000, поскольку это, по-видимому, максимизирует эффект:

$ python3 -m timeit "a = tuple(range(200000));  b = tuple(range(200000)); a is b"
100 loops, best of 3: 7.03 msec per loop
$ python3 -m timeit "a = tuple(range(200000)) is tuple(range(200000))"
100 loops, best of 3: 10.2 msec per loop
$ python3 -m timeit "tuple(range(200000)) is tuple(range(200000))"
100 loops, best of 3: 10.2 msec per loop
$ python3 -m timeit "a = b = tuple(range(200000)) is tuple(range(200000))"
100 loops, best of 3: 9.99 msec per loop
$ python3 -m timeit "a = b = tuple(range(200000)) is tuple(range(200000))"
100 loops, best of 3: 10.2 msec per loop
$ python3 -m timeit "tuple(range(200000)) is tuple(range(200000))"
100 loops, best of 3: 10.1 msec per loop
$ python3 -m timeit "a = tuple(range(200000));  b = tuple(range(200000)); a is b"
100 loops, best of 3: 7 msec per loop
$ python3 -m timeit "a = tuple(range(200000));  b = tuple(range(200000)); a is b"
100 loops, best of 3: 7.02 msec per loop

Я отмечаю, что различия между прогонами и порядок, в котором выполняются выражения, очень мало влияют на результат.

Добавление присвоений a и b в медленную версию не ускоряет ее. Фактически, как мы могли ожидать, назначение локальных переменных имеет незначительный эффект. Единственное, что ускоряет его, - это разделение выражения целиком на два. Единственное отличие, которое это должно сделать, это уменьшить максимальную глубину стека, используемую Python, при оценке выражения (от 4 до 3).

Это дает нам понять, что эффект связан с глубиной стека, возможно, дополнительный уровень перетаскивает стек на другую страницу памяти. Если это так, мы увидим, что внесение других изменений, влияющих на стек, изменится (скорее всего, убьет эффект), и на самом деле это то, что мы видим:

$ python3 -m timeit -s "def foo():
   tuple(range(200000)) is tuple(range(200000))" "foo()"
100 loops, best of 3: 10 msec per loop
$ python3 -m timeit -s "def foo():
   tuple(range(200000)) is tuple(range(200000))" "foo()"
100 loops, best of 3: 10 msec per loop
$ python3 -m timeit -s "def foo():
   a = tuple(range(200000));  b = tuple(range(200000)); a is b" "foo()"
100 loops, best of 3: 9.97 msec per loop
$ python3 -m timeit -s "def foo():
   a = tuple(range(200000));  b = tuple(range(200000)); a is b" "foo()"
100 loops, best of 3: 10 msec per loop

Итак, я думаю, что эффект полностью связан с тем, сколько стека Python потребляется во время процесса синхронизации. Это все еще странно.