«X <y <z» быстрее, чем «x <y и y <z»?

129

Из этой страницы мы знаем, что:

Связанные сравнения выполняются быстрее, чем использование andоператора. Пишите x < y < zвместо x < y and y < z.

Однако я получил другой результат, проверяя следующие фрагменты кода:

$ python -m timeit "x = 1.2" "y = 1.3" "z = 1.8" "x < y < z"
1000000 loops, best of 3: 0.322 usec per loop
$ python -m timeit "x = 1.2" "y = 1.3" "z = 1.8" "x < y and y < z"
1000000 loops, best of 3: 0.22 usec per loop
$ python -m timeit "x = 1.2" "y = 1.3" "z = 1.1" "x < y < z"
1000000 loops, best of 3: 0.279 usec per loop
$ python -m timeit "x = 1.2" "y = 1.3" "z = 1.1" "x < y and y < z"
1000000 loops, best of 3: 0.215 usec per loop

Похоже, что x < y and y < zбыстрее чем x < y < z. Зачем?

После поиска некоторых сообщений на этом сайте (например, этого ) я знаю, что «оценивается только один раз» - это ключ к успеху x < y < z, однако я все еще не понимаю. Для дальнейшего изучения я разобрал эти две функции, используя dis.dis:

import dis

def chained_compare():
        x = 1.2
        y = 1.3
        z = 1.1
        x < y < z

def and_compare():
        x = 1.2
        y = 1.3
        z = 1.1
        x < y and y < z

dis.dis(chained_compare)
dis.dis(and_compare)

И результат:

## chained_compare ##

  4           0 LOAD_CONST               1 (1.2)
              3 STORE_FAST               0 (x)

  5           6 LOAD_CONST               2 (1.3)
              9 STORE_FAST               1 (y)

  6          12 LOAD_CONST               3 (1.1)
             15 STORE_FAST               2 (z)

  7          18 LOAD_FAST                0 (x)
             21 LOAD_FAST                1 (y)
             24 DUP_TOP
             25 ROT_THREE
             26 COMPARE_OP               0 (<)
             29 JUMP_IF_FALSE_OR_POP    41
             32 LOAD_FAST                2 (z)
             35 COMPARE_OP               0 (<)
             38 JUMP_FORWARD             2 (to 43)
        >>   41 ROT_TWO
             42 POP_TOP
        >>   43 POP_TOP
             44 LOAD_CONST               0 (None)
             47 RETURN_VALUE

## and_compare ##

 10           0 LOAD_CONST               1 (1.2)
              3 STORE_FAST               0 (x)

 11           6 LOAD_CONST               2 (1.3)
              9 STORE_FAST               1 (y)

 12          12 LOAD_CONST               3 (1.1)
             15 STORE_FAST               2 (z)

 13          18 LOAD_FAST                0 (x)
             21 LOAD_FAST                1 (y)
             24 COMPARE_OP               0 (<)
             27 JUMP_IF_FALSE_OR_POP    39
             30 LOAD_FAST                1 (y)
             33 LOAD_FAST                2 (z)
             36 COMPARE_OP               0 (<)
        >>   39 POP_TOP
             40 LOAD_CONST               0 (None)

Кажется, что у x < y and y < zнего меньше скрытых команд, чем у x < y < z. Стоит ли считать x < y and y < zбыстрее, чем x < y < z?

Протестировано с Python 2.7.6 на процессоре Intel (R) Xeon (R) E5640 @ 2,67 ГГц.

zangw
источник
8
Больше дезассемблированных команд не означает большей сложности или более медленного кода. Однако, увидев ваши timeitтесты, я заинтересовался этим.
Марко Бонелли
6
Я предположил, что разница в скорости по сравнению с «оценкой один раз» возникает, когда yэто не просто поиск переменной, а более дорогой процесс, такой как вызов функции? Т.е. 10 < max(range(100)) < 15быстрее, чем 10 < max(range(100)) and max(range(100)) < 15потому что max(range(100))вызывается один раз для обоих сравнений.
zehnpaard 01
2
@MarcoBonelli Это происходит, когда дизассемблированный код 1) не содержит циклов и 2) каждый байт-код работает очень-очень быстро, потому что в этот момент накладные расходы основного цикла становятся значительными.
Bakuriu
2
Прогнозирование ветвлений может испортить ваши тесты.
Кори Огберн
2
@zehnpaard Я согласен с вами. Когда «y» больше, чем простое значение (например, вызов функции или вычисление), я бы ожидал, что тот факт, что «y» вычисляется один раз в x <y <z, окажет гораздо более заметное влияние. В представленном случае мы находимся в пределах шкалы ошибок: преобладают эффекты (неудачного) предсказания ветвления, неоптимального байт-кода и других эффектов, зависящих от платформы / процессора. Это не отменяет общего правила, согласно которому однократная оценка лучше (а также более удобочитаема), но показывает, что это может не добавить столько ценности в крайних случаях.
MartyMacGyver 03

Ответы:

111

Разница в том, что in x < y < z yоценивается только один раз. Это не имеет большого значения, если y - переменная, но имеет значение, когда это вызов функции, для вычисления которого требуется некоторое время.

from time import sleep
def y():
    sleep(.2)
    return 1.3
%timeit 1.2 < y() < 1.8
10 loops, best of 3: 203 ms per loop
%timeit 1.2 < y() and y() < 1.8
1 loops, best of 3: 405 ms per loop
обкрадывать
источник
18
Конечно, может быть и семантическая разница. Функция y () может не только возвращать два разных значения, но и с переменной оценка оператора «меньше» в x <y может изменить значение y. Вот почему она часто не оптимизируется в байтовом коде (например, если y нелокальная переменная или одна из участвующих в замыкании)
Random832 01
Просто любопытно, зачем вам понадобилась sleep()функция внутри?
Prof
@Prof То есть для моделирования функции, которая требует времени для вычисления результата. Если функция вернется сразу, большой разницы между двумя результатами timeit не будет.
Роб
@ Роб А почему бы не было большой разницы? Было бы 3 мс против 205 мс, это достаточно хорошо демонстрирует, не так ли?
Проф
@Prof Вам не хватает того, что y () вычисляется дважды, так что это 2x200 мс вместо 1x200 мс. Остальное (3/5 мс) - это несущественный шум при измерении времени.
Роб
22

Оптимальный байт-код для обеих функций, которые вы определили, будет

          0 LOAD_CONST               0 (None)
          3 RETURN_VALUE

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

def interesting_compare(y):
    x = 1.1
    z = 1.3
    return x < y < z  # or: x < y and y < z

Опять же, две версии сравнения семантически идентичны, поэтому оптимальный байт-код одинаков для обеих конструкций. Насколько я могу понять, это будет выглядеть так. Я аннотировал каждую строку с содержимым стека до и после каждого кода операции в нотации Forth (верх стека справа, --делится до и после, завершение ?указывает на то, что могло или не могло быть там). Обратите внимание, что RETURN_VALUEотбрасывает все, что осталось в стеке под возвращенным значением.

          0 LOAD_FAST                0 (y)    ;          -- y
          3 DUP_TOP                           ; y        -- y y
          4 LOAD_CONST               0 (1.1)  ; y y      -- y y 1.1
          7 COMPARE_OP               4 (>)    ; y y 1.1  -- y pred
         10 JUMP_IF_FALSE_OR_POP     19       ; y pred   -- y
         13 LOAD_CONST               1 (1.3)  ; y        -- y 1.3
         16 COMPARE_OP               0 (<)    ; y 1.3    -- pred
     >>  19 RETURN_VALUE                      ; y? pred  --

Если реализация языка CPython, PyPy и т. Д. Не генерирует этот байт-код (или его собственную эквивалентную последовательность операций) для обоих вариантов, это демонстрирует низкое качество этого компилятора байт-кода . Получение из последовательностей байт-кода, которые вы разместили выше, является решенной проблемой (я думаю, все, что вам нужно в этом случае, - это сворачивание констант , удаление мертвого кода и лучшее моделирование содержимого стека; обычное устранение подвыражения также было бы дешевым и ценным ), и нет никакого оправдания тому, чтобы не делать этого в современной языковой реализации.

Теперь случается, что все текущие реализации языка имеют некачественные компиляторы байт-кода. Но вы должны игнорировать это при кодировании! Представьте, что компилятор байт-кода хорош, и напишите наиболее читаемый код. В любом случае, вероятно, будет достаточно быстро. Если это не так, сначала поищите алгоритмические улучшения, а затем попробуйте Cython - это обеспечит гораздо больше улучшений при тех же усилиях, чем любые настройки на уровне выражений, которые вы могли бы применить.

zwol
источник
Что ж, самая важная из всех оптимизаций должна быть возможна в первую очередь: встраивание. И это далеко не «решенная проблема» для динамических языков, которые позволяют динамически изменять реализацию функции (хотя это выполнимо - HotSpot может делать аналогичные вещи, и такие вещи, как Graal, работают над тем, чтобы сделать такие оптимизации доступными для Python и других динамических языков. ). И поскольку сама функция может вызываться из разных модулей (или вызов может генерироваться динамически!), Вы действительно не можете выполнять эти оптимизации там.
Voo
1
@Voo Мой оптимизированный вручную байт-код имеет точно такую ​​же семантику, что и исходный, даже при наличии произвольного динамизма (одно исключение: предполагается a <b ≡ b> a). Кроме того, встраивание переоценено. Если вы делаете слишком много - а слишком легко сделать слишком много - вы взорвете I-cache и потеряете все, что приобрели, а затем и немного.
zwol 01
Вы правы, я думал, вы имели в виду, что хотите оптимизировать свой interesting_compareпростой байт-код вверху (который будет работать только с встраиванием). Совершенно оффтоп, но: Встраивание - одна из самых важных оптимизаций для любого компилятора. Вы можете попробовать запустить некоторые тесты, скажем, с HotSpot на реальных программах (а не с некоторыми математическими тестами, которые проводят 99% своего времени в одном цикле горячего цикла, оптимизированном вручную [и, следовательно, в любом случае не имеет больше вызовов функций]), когда вы отключите его возможность встраивать что угодно - вы увидите большие регрессии.
Voo
@Voo Да, простой байт-код вверху должен был быть «оптимальной версией» исходного кода OP, а не interesting_compare.
zwol 01
«одно исключение: предполагается a <b ≡ b> a» → что просто неверно в Python. Кроме того, я думаю, что CPython даже не может по-настоящему предположить, что операции yне изменяют стек, поскольку в нем много инструментов отладки.
Veedrac
8

Поскольку разница в выводе, похоже, связана с отсутствием оптимизации, я думаю, вам следует игнорировать эту разницу в большинстве случаев - может быть, разница исчезнет. Разница в том, что yоценивать нужно только один раз, и это решается путем дублирования его в стеке, что требует дополнительных POP_TOP- LOAD_FASTхотя решение для использования может быть возможным.

Однако важное различие заключается в том, что во x<y and y<zвтором yслучае следует оценивать дважды, если он x<yоценивается как истинный, это имеет значение, если оценка yзанимает значительное время или имеет побочные эффекты.

В большинстве случаев вам следует использовать, x<y<zхотя он несколько медленнее.

skyking
источник
6

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

x < y < zКонструкция:

  1. Яснее и прямее по своему смыслу.
  2. Его семантика - это то, что вы ожидаете от «математического значения» сравнения: вычислить x, yи z один раз проверить, выполняется ли все условие. Использование andизменяет семантику путем yмногократной оценки , что может изменить результат .

Поэтому выбирайте одно вместо другого в зависимости от желаемой семантики и, если они эквивалентны, будет ли один более читаемым, чем другой.

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

Но обратите внимание, что этот результат не сохраняется в более общей ситуации, а только в «худшем случае», который вы можете профилировать. Как отмечали другие, если вы измените yчто-то, что займет даже немного больше времени, вы увидите, что результаты меняются, потому что цепная нотация оценивает это только один раз.

Подводя итог:

  • Перед выполнением рассмотрите семантику.
  • Учитывайте удобочитаемость.
  • Не доверяйте микробенчмаркам. Всегда выполняйте профилирование с разными типами параметров, чтобы увидеть, как время функции / выражения ведет себя по отношению к указанным параметрам, и подумайте, как вы планируете его использовать.
Bakuriu
источник
5
Я думаю, что ваш ответ не включает тот простой и актуальный факт, что процитированная страница в конкретном случае вопроса - сравнение чисел с плавающей запятой - просто неверна. Цепное сравнение не быстрее, как видно из измерений и в сгенерированном байт-коде.
pvg 01
30
Мне не кажется полезным отвечать на вопрос, помеченный как производительность со словами «может быть, вам не стоит так много думать о производительности». Вы делаете потенциально покровительственные предположения об понимании задающим вопросы общих принципов программирования, а затем в основном говорите о них, а не о проблеме.
Бен Миллвуд,
@Veerdac, вы неправильно читаете комментарий. Предложенная оптимизация в исходном документе, на которую полагался OP, неверна, как минимум в случае с плавающей точкой. Это не быстрее.
pvg