Well, my first step was to set the two tests up independently to ensure that this is not a result of e.g. the order in which the functions are defined.
>python -mtimeit "x=[34534534, 23423523, 77645645, 345346]" "[e for e in x]"
1000000 loops, best of 3: 0.638 usec per loop
>python -mtimeit "x=[34534534, 23423523, 77645645, 345346]" "list(e for e in x)"
1000000 loops, best of 3: 1.72 usec per loop
Sure enough, I can replicate this. OK, next step is to have a look at the bytecode to see what's actually going on:
>>> import dis
>>> x=[34534534, 23423523, 77645645, 345346]
>>> dis.dis(lambda: [e for e in x])
1 0 LOAD_CONST 0 (<code object <listcomp> at 0x0000000001F8B330, file "<stdin>", line 1>)
3 MAKE_FUNCTION 0
6 LOAD_GLOBAL 0 (x)
9 GET_ITER
10 CALL_FUNCTION 1
13 RETURN_VALUE
>>> dis.dis(lambda: list(e for e in x))
1 0 LOAD_GLOBAL 0 (list)
3 LOAD_CONST 0 (<code object <genexpr> at 0x0000000001F8B9B0, file "<stdin>", line 1>)
6 MAKE_FUNCTION 0
9 LOAD_GLOBAL 1 (x)
12 GET_ITER
13 CALL_FUNCTION 1
16 CALL_FUNCTION 1
19 RETURN_VALUE
Notice that the first method creates the list directly, whereas the second method creates a genexpr
object and passes that to the global list
. This is probably where the overhead lies.
Note also that the difference is approximately a microsecond i.e. utterly trivial.
Other interesting data
This still holds for non-trivial lists
>python -mtimeit "x=range(100000)" "[e for e in x]"
100 loops, best of 3: 8.51 msec per loop
>python -mtimeit "x=range(100000)" "list(e for e in x)"
100 loops, best of 3: 11.8 msec per loop
and for less trivial map functions:
>python -mtimeit "x=range(100000)" "[2*e for e in x]"
100 loops, best of 3: 12.8 msec per loop
>python -mtimeit "x=range(100000)" "list(2*e for e in x)"
100 loops, best of 3: 16.8 msec per loop
and (though less strongly) if we filter the list:
>python -mtimeit "x=range(100000)" "[e for e in x if e%2]"
100 loops, best of 3: 14 msec per loop
>python -mtimeit "x=range(100000)" "list(e for e in x if e%2)"
100 loops, best of 3: 16.5 msec per loop
I believe the difference here is entirely in the cost of 1000000 additions. Testing with 64-bit Python.org 3.3.0 on Mac OS X:
In [698]: %timeit len ([None for n in range (1, 1000000) if n%3 == 1])
10 loops, best of 3: 127 ms per loop
In [699]: %timeit sum (1 for n in range (1, 1000000) if n%3 == 1)
10 loops, best of 3: 138 ms per loop
In [700]: %timeit sum ([1 for n in range (1, 1000000) if n%3 == 1])
10 loops, best of 3: 139 ms per loop
So, it's not that the comprehension is faster than the genexp; they both take about the same time. But calling len
on a list
is instant, while summing 1M numbers adds another 7% to the total time.
Throwing a few different numbers at it, this seems to hold up unless the list is very tiny (in which case it does seem to get faster), or large enough that memory allocation starts to become a significant factor (which it isn't yet, at 333K).
Best Answer
First of all: generator expressions are memory efficient, not necessarily speed efficient.
Your compact
genexp()
version is slower for two reasons:Generator expressions are implemented using a new scope (like a new function). You are producing N new scopes, one for for each
any()
test. Creating a new scope and tearing it down again is relatively expensive, certainly when done in a loop and then compared with code that doesn't do this.The
sum()
andany()
names are additional globals to be looked up. In the case ofany()
, that's an additional N global lookups per test. Globals must be looked up in a dictionary, versus locals which are looked up by index in a C-array (which is very fast).The latter is but a small component, most of the cost lies in creating and destroying frames (scopes); if you create a version where
_any
and_sum
are locals to the function you get but a small improvement in performance:I didn't create a local for
xrange
to keep that aspect the same. Technically speaking, the_any
name is looked up as a closure, not a local, by the generator expression code object, which are not as slow as global lookups but not quite as speedy as a local lookup either.