Performance of any()

Question

This is mostly an exercise in learning Python. I wrote this function to test if a number is prime:

def p1(n):
    for d in xrange(2, int(math.sqrt(n)) + 1):
        if n % d == 0:
            return False
    return True

Then I realized I can make easily rewrite it using any():

def p2(n):
    return not any((n % d == 0) for d in xrange(2, int(math.sqrt(n)) + 1))

Performance-wise, I was expecting p2 to be faster than, or at the very least as fast as, p1 because any() is builtin, but for a large-ish prime, p2 is quite a bit slower:

$ python -m timeit -n 100000 -s "import test" "test.p1(999983)"
100000 loops, best of 3: 60.2 usec per loop

$ python -m timeit -n 100000 -s "import test" "test.p2(999983)"
100000 loops, best of 3: 88.1 usec per loop

Am I using any() incorrectly here? Is there a way to write this function using any() so that it's as far as iterating myself?

Update: Numbers for an even larger prime

$  python -m timeit -n 1000 -s "import test" "test.p1(9999999999971)"
1000 loops, best of 3: 181 msec per loop

$  python -m timeit -n 1000 -s "import test" "test.p2(9999999999971)"
1000 loops, best of 3: 261 msec per loop

Answer 1

The performance difference is minimal, but the reason it exists is that any incurs building a generator expression, and an extra function call, compared to the for loop. Both have identical behaviors, though (shortcut evaluation).

As the size of your input grows, the difference won't diminish (I was wrong) because you're using a generator expression, and iterating over it requires calling a method (.next()) on it and an extra stack frame. any does that under the hood, of course.

The for loop is iterating over an xrange object. any is iterating over a generator expression, which itself is iterating over an xrange object.

Either way, use whichever produces the most readable/maintainable code. Choosing one over the other will have little, if any, performance impact on whatever program you're writing.