Why is "if not (a and b)" faster than "if not a or not b"?

Question

On a whim, I recently tested these two methods with timeit, to see which evaluation method was faster:

import timeit

"""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

...and got these results:

 VALUES FOR a,b ->      0,0         0,1         1,0         1,1
        method
    and_chk(a,b)    0.95559     0.98646     0.95138     0.98788
 not_or_chk(a,b)    0.96804     1.07323     0.96015     1.05874
                                            ...seconds per 1,111,111 cycles.

The difference in efficiency is between one and nine percent, always in favour of if not (a and b), which is the opposite of what I might expect since I understand that if not a or not b will evaluate its terms (if not a and then if not b) in order, running the if block once it encounters a true expression (and there are no and clauses). In contrast, the and_chk method needs to evaluate both clauses before it can return any result to the if not.. that wraps it.

The timing results, however, disprove this understanding. How, then, is the if condition being evaluated? I am perfectly aware of the fact that this degree of microoptimization is practically, if not completely, pointless. I just want to understand how Python is going about it.

---

For completion's sake, this is how I set up timeit...

cyc = 1111111

bothFalse_and = iter([(0,0)] * cyc)
zeroTrue_and = iter([(1,0)] * cyc)
oneTrue_and = iter([(0,1)] * cyc)
bothTrue_and = iter([(1,1)] * cyc)

bothFalse_notor = iter([(0,0)] * cyc)
zeroTrue_notor = iter([(1,0)] * cyc)
oneTrue_notor = iter([(0,1)] * cyc)
bothTrue_notor = iter([(1,1)] * cyc)

time_bothFalse_and = timeit.Timer('and_chk(next(tups))', 'from __main__ import bothFalse_and as tups, and_chk')
time_zeroTrue_and = timeit.Timer('and_chk(next(tups))', 'from __main__ import zeroTrue_and as tups, and_chk')
time_oneTrue_and = timeit.Timer('and_chk(next(tups))', 'from __main__ import oneTrue_and as tups, and_chk')
time_bothTrue_and = timeit.Timer('and_chk(next(tups))', 'from __main__ import bothTrue_and as tups, and_chk')

time_bothFalse_notor = timeit.Timer('not_or_chk(next(tups))', 'from __main__ import bothFalse_notor as tups, not_or_chk')
time_zeroTrue_notor = timeit.Timer('not_or_chk(next(tups))', 'from __main__ import zeroTrue_notor as tups, not_or_chk')
time_oneTrue_notor = timeit.Timer('not_or_chk(next(tups))', 'from __main__ import oneTrue_notor as tups, not_or_chk')
time_bothTrue_notor = timeit.Timer('not_or_chk(next(tups))', 'from __main__ import bothTrue_notor as tups, not_or_chk')

...then ran each timeit.Timer(..) function with .timeit(cyc) to get the results posted.

Answer 1

TL;DR

The not_or_chk function requires two unary operations in addition to two jumps (in the worst case), while the and_chk function only has the two jumps (again, in the worst case).

Details

The dis module to the rescue! The dis module lets you take a look at the Python bytecode disassembly of your code. For example:

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))

Produces this output:

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

Take a look at the two blocks of Python bytecode that I've marked with the asterisks. Those blocks are your two disassembled functions. Note that and_chk only has two jumps, and the calculations in the function are made while deciding whether or not to take the jump.

On the other hand, the not_or_chkfunction requires the not operation to be carried out twice in the worst case, in addition to the interpreter deciding whether or not to take the jump.

Answer 2

I just noticed this question via your Meta SO question: Is it appropriate to share the results of my research toward solving my own minor questions?. As you mention in that question (and one of the tags on this question indicates), this sort of thing falls into the category of micro-optimization. Ideally, one shouldn't need to worry about such minor performance differences, and as Knuth says, premature optimization is the root of all evil. But I guess it is fun and instructive to investigate such matters, as it can give you a better feel for how Python works "under the hood".

Mephy's comment prompted me to see what the timing differences were for if-less versions of your functions. The results are interesting, IMHO. I also took the opportunity to streamline your testing procedure.

#!/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)

output

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]

These timings were performed using Python 2.6.6 on a 2GHz Pentium 4 (single-core 32 bit) running Mepis 11 (a Debian family Linux distro).

You'll note that I've avoided using your next(tups) strategy to get the arguments for each function call and instead I'm passing the args directly, as constants. The time taken to perform next(tups) should be fairly constant, but it's best to eliminate such overheads, when practical, so that the reported time measurements more accurately reflect the performance of the code we're really interested in.

Also, it's usual to perform several repetitions of the timing loop and take the minimum value; FWIW, I generally do 3 to 5 reps. From the timeit docs:

Note

It’s tempting to calculate mean and standard deviation from the result vector and report these. However, this is not very useful. In a typical case, the lowest value gives a lower bound for how fast your machine can run the given code snippet; higher values in the result vector are typically not caused by variability in Python’s speed, but by other processes interfering with your timing accuracy. So the min() of the result is probably the only number you should be interested in. After that, you should look at the entire vector and apply common sense rather than statistics.

Your Meta post says that you want to perform & report on other micro-optimization experiments, so you might be interested in taking a look at some code I posted a few months ago that does time tests on various implementations of the factorial function.