Почему "если нет (a и b)" быстрее, чем "если нет или нет b"?

По прихоти, я недавно проверил эти два метода с помощью timeit, чтобы узнать, какой метод оценки был быстрее:

Разница в эффективности составляет от одного до девяти процентов, всегда в пользу if not (a and b), что противоположно тому, что я мог ожидать, так как я понимаю, что if not a or not b будет оценивать свои термины (if not a, а затем if not b) в порядке, запустив блок if, когда он встречает истинное выражение (и нет предложений and). Напротив, метод and_chk должен оценивать оба предложения, прежде чем он сможет вернуть любой результат в if not.., который его обертывает.

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

Для завершения сакэ, вот как я установил timeit...

... затем выполнил каждую функцию timeit.Timer(..) с помощью .timeit(cyc), чтобы опубликовать результаты.

Ответы

Ответ 1

TL; DR

Функция not_or_chk требует двух унарных операций в дополнение к двум переходам (в худшем случае), а функция and_chk имеет только два перехода (опять же, в худшем случае).

Подробнее

dis module на помощь! Модуль dis позволяет взглянуть на дизассемблирование вашего байт-кода на Python. Например:

import dis

"""Test method returns True if either argument is falsey, else False."""

def and_chk((a, b)):
    if not (a and b):
        return True
    return False

def not_or_chk((a, b)):
    if not a or not b:
        return True
    return False

print("And Check:\n")
print(dis.dis(and_chk))

print("Or Check:\n")
print(dis.dis(not_or_chk))

Производит этот вывод:

And Check:

  5           0 LOAD_FAST                0 (.0)
              3 UNPACK_SEQUENCE          2
              6 STORE_FAST               1 (a)
              9 STORE_FAST               2 (b)

  6          12 LOAD_FAST                1 (a)    * This block is the *
             15 JUMP_IF_FALSE_OR_POP    21        * disassembly of    *
             18 LOAD_FAST                2 (b)    * the "and_chk"     *
        >>   21 POP_JUMP_IF_TRUE        28        * function          *

  7          24 LOAD_GLOBAL              0 (True)
             27 RETURN_VALUE

  8     >>   28 LOAD_GLOBAL              1 (False)
             31 RETURN_VALUE
None
Or Check:

 10           0 LOAD_FAST                0 (.0)
              3 UNPACK_SEQUENCE          2
              6 STORE_FAST               1 (a)
              9 STORE_FAST               2 (b)

 11          12 LOAD_FAST                1 (a)    * This block is the *
             15 UNARY_NOT                         * disassembly of    *
             16 POP_JUMP_IF_TRUE        26        * the "not_or_chk"  *
             19 LOAD_FAST                2 (b)    * function          *
             22 UNARY_NOT
             23 POP_JUMP_IF_FALSE       30

 12     >>   26 LOAD_GLOBAL              0 (True)
             29 RETURN_VALUE

 13     >>   30 LOAD_GLOBAL              1 (False)
             33 RETURN_VALUE
None

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

С другой стороны, функция not_or_chk требует, чтобы операция not выполнялась дважды в худшем случае, в дополнение к интерпретатору, решающему, принимать или не выполнять прыжок.

Ответ 2

Я только что заметил этот вопрос через ваш вопрос Meta SO: Является ли уместным поделиться результатами моих исследований с решением моих собственных второстепенных вопросов?. Как вы упомянули в этом вопросе (и один из тегов по этому вопросу указывает), такая штука относится к категории микро-оптимизации. В идеале, не стоит беспокоиться о таких незначительных различиях в производительности, и, как говорит Кнут, преждевременная оптимизация - это корень всего зла. Но я думаю, что это интересно и поучительно расследовать такие вопросы, поскольку это может дать вам лучшее представление о том, как Python работает "под капотом".

Комментарий Mephy подсказывал мне, каковы различия во времени для if -непрерывных версий ваших функций. Результаты интересны, ИМХО. Я также воспользовался возможностью, чтобы упростить процедуру тестирования.

#!/usr/bin/env python

''' Do timeit tests on various implementations of NAND

    NAND returns True if either argument is falsey, else False.
    From https://stackoverflow.com/q/29551438/4014959
    Written by PM 2Ring 2015.04.09
'''

from timeit import Timer
import dis

def and_chk(a, b):
    return not (a and b)

def and_chk_if(a, b):
    if not (a and b):
        return True
    else:
        return False

def not_or_chk(a, b):
    return not a or not b

def not_or_chk_if(a, b):
    if not a or not b:
        return True
    else:
        return False


#All the functions
funcs = (
    and_chk,
    and_chk_if,
    not_or_chk,
    not_or_chk_if,
)

#Argument tuples to test the functions with
bools = (0, 1)
bool_tups = [(u, v) for u in bools for v in bools]


def show_dis():
    ''' Show the disassembly for each function '''
    print 'Disassembly'
    for func in funcs:
        fname = func.func_name
        print '\n%s' % fname
        dis.dis(func)
    print


def verify():
    ''' Verify that the functions actually perform as intended '''
    print 'Verifying...'
    for func in funcs:
        fname = func.func_name
        print '\n%s' % fname
        for args in bool_tups:
            print args, func(*args)
    print


def time_test(loops, reps):
    ''' Print timing stats for all the functions '''
    print 'Timing tests\nLoops = %d, Repetitions = %d' % (loops, reps)

    for func in funcs:
        fname = func.func_name
        print '\n%s' % fname
        setup = 'from __main__ import %s' % fname
        for args in bool_tups:
            t = Timer('%s%s' % (fname, args), setup)
            r = t.repeat(reps, loops)
            r.sort()
            print args, r


show_dis()
verify()
time_test(loops=520000, reps=3)

Выход

Disassembly

and_chk
 13           0 LOAD_FAST                0 (a)
              3 JUMP_IF_FALSE            4 (to 10)
              6 POP_TOP             
              7 LOAD_FAST                1 (b)
        >>   10 UNARY_NOT           
             11 RETURN_VALUE        

and_chk_if
 16           0 LOAD_FAST                0 (a)
              3 JUMP_IF_FALSE            4 (to 10)
              6 POP_TOP             
              7 LOAD_FAST                1 (b)
        >>   10 JUMP_IF_TRUE             5 (to 18)
             13 POP_TOP             

 17          14 LOAD_GLOBAL              0 (True)
             17 RETURN_VALUE        
        >>   18 POP_TOP             

 19          19 LOAD_GLOBAL              1 (False)
             22 RETURN_VALUE        
             23 LOAD_CONST               0 (None)
             26 RETURN_VALUE        

not_or_chk
 22           0 LOAD_FAST                0 (a)
              3 UNARY_NOT           
              4 JUMP_IF_TRUE             5 (to 12)
              7 POP_TOP             
              8 LOAD_FAST                1 (b)
             11 UNARY_NOT           
        >>   12 RETURN_VALUE        

not_or_chk_if
 25           0 LOAD_FAST                0 (a)
              3 UNARY_NOT           
              4 JUMP_IF_TRUE             8 (to 15)
              7 POP_TOP             
              8 LOAD_FAST                1 (b)
             11 UNARY_NOT           
             12 JUMP_IF_FALSE            5 (to 20)
        >>   15 POP_TOP             

 26          16 LOAD_GLOBAL              0 (True)
             19 RETURN_VALUE        
        >>   20 POP_TOP             

 28          21 LOAD_GLOBAL              1 (False)
             24 RETURN_VALUE        
             25 LOAD_CONST               0 (None)
             28 RETURN_VALUE        

Verifying...

and_chk
(0, 0) True
(0, 1) True
(1, 0) True
(1, 1) False

and_chk_if
(0, 0) True
(0, 1) True
(1, 0) True
(1, 1) False

not_or_chk
(0, 0) True
(0, 1) True
(1, 0) True
(1, 1) False

not_or_chk_if
(0, 0) True
(0, 1) True
(1, 0) True
(1, 1) False

Timing tests
Loops = 520000, Repetitions = 3

and_chk
(0, 0) [0.36773014068603516, 0.37793493270874023, 0.38387489318847656]
(0, 1) [0.36292791366577148, 0.37119913101196289, 0.37146902084350586]
(1, 0) [0.38673520088195801, 0.39340090751647949, 0.39670205116271973]
(1, 1) [0.38938498497009277, 0.39505791664123535, 0.40034103393554688]

and_chk_if
(0, 0) [0.4021449089050293, 0.40345501899719238, 0.41558098793029785]
(0, 1) [0.40686416625976562, 0.41213202476501465, 0.44800615310668945]
(1, 0) [0.4281308650970459, 0.42916202545166016, 0.43681907653808594]
(1, 1) [0.46246123313903809, 0.46759700775146484, 0.47544980049133301]

not_or_chk
(0, 0) [0.35435700416564941, 0.36368083953857422, 0.36867713928222656]
(0, 1) [0.35602092742919922, 0.35732793807983398, 0.36237406730651855]
(1, 0) [0.39550518989562988, 0.40660715103149414, 0.40977287292480469]
(1, 1) [0.4060060977935791, 0.4112389087677002, 0.41296815872192383]

not_or_chk_if
(0, 0) [0.4308779239654541, 0.44109201431274414, 0.45827698707580566]
(0, 1) [0.43600606918334961, 0.4370419979095459, 0.47623395919799805]
(1, 0) [0.48452401161193848, 0.48769593238830566, 0.49147915840148926]
(1, 1) [0.53107500076293945, 0.54048299789428711, 0.55434417724609375]

Эти тайминги выполнялись с использованием Python 2.6.6 на 2-ГГц Pentium 4 (одноядерный 32-разрядный), работающий с Mepis 11 (дистрибутив семейства Linux Debian).

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

Кроме того, обычно выполняется несколько повторений цикла синхронизации и принимает минимальное значение; FWIW, я обычно делаю от 3 до 5 повторений. Из timeit docs:

Примечание

Его соблазн рассчитать среднее и стандартное отклонение от результата вектор и сообщить об этом. Однако это не очень полезно. В типичный случай, самое низкое значение дает нижнюю оценку того, насколько быстро ваш машина может запускать данный фрагмент кода; более высокие значения в результате вектор, как правило, не вызваны изменчивостью скорости Pythons, но другими процессами, мешающими вашей точности времени. Таким образом, min() результата, вероятно, единственного числа, которое вас должно заинтересовать. После этого вы должны посмотреть на весь вектор и применить общий смысл, а не статистика.

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