Dict comprehensions - improvement to docs?

[Ian Kelly]

On Wed, Mar 18, 2015 at 2:01 AM, Frank Millman <frank at chagford.com> wrote:
>
> "Ian Kelly" <ian.g.kelly at gmail.com> wrote in message
> news:CALwzidmNDcSvER7S6inEaVZA=DHUrDX1KzL-WRVwhd=o3_LvWA at mail.gmail.com...
>> On Tue, Mar 17, 2015 at 12:44 AM, Frank Millman <frank at chagford.com>
>> wrote:
>>> Thanks for the explanation. I'll try not to make that mistake again.
>>>
>>> However, to go back to the original example, we want to compare a dict
>>> comprehension with a dict() constructor using a generator expression.
>>>
>>> Let's see if I have got this one right -
>>>
>>> C:\>python -m timeit -s "x=range(65, 91); y=[chr(z) for z in x]"
>>> "dict((a,
>>> b) for a, b in zip(x, y))"
>>> 10000 loops, best of 3: 49.6 usec per loop
>>>
>>> C:\>python -m timeit -s "x=range(65, 91); y=[chr(z) for z in x]" "{a: b
>>> for
>>> a, b in zip(x, y)}"
>>> 10000 loops, best of 3: 25.8 usec per loop
>>
>> Why did you revert back to the no-op generator expression in the first
>> case instead of the more efficient dict(zip(x, y))?
>
> Firstly, I just want to emphasise that I am not trying to prove anything
> here, I am trying to learn something.
>
> Why do you call it a no-op? I understood your previous point that a
> generator in the setup statement is exhausted after the first execution, but
> this is in the run-time statement, so I thought it would be executed every
> time.

I call it a no-op because it does not perform any transformation on
the iterable stream. It takes as input a sequence of 2-tuples, and it
yields the same tuples in the same sequence. It does however add a
non-trivial amount of code to perform that lack of work: for every
tuple in the sequence, it unpacks it, builds a new tuple, and yields
the result.

> I read Lele's post where he pointed out that part of the difference is
> explained by the fact that dict() involves a function call, whereas {} does
> not. However, this does not seem to explain the entire difference.

The dict call may be part of it, but I think it has more to do with
differences in the compiled loop. All the major work done by the
dict() function has to be done just the same by the comprehension. In
my own timing, the version with no comprehension and the dict
comprehension are very similar in speed, whereas the generator
expression is substantially slower. This points to the generator
expression being the bottleneck, not the dict call (which is a
function call, but at least it's implemented in C).

The bytecode for the generator expression looks like this:

>>> dis.dis(compile('((a,b) for a,b in zip(x,y))', '', 'eval').co_consts[0])
  1           0 LOAD_FAST                0 (.0)
        >>    3 FOR_ITER                23 (to 29)
              6 UNPACK_SEQUENCE          2
              9 STORE_FAST               1 (a)
             12 STORE_FAST               2 (b)
             15 LOAD_FAST                1 (a)
             18 LOAD_FAST                2 (b)
             21 BUILD_TUPLE              2
             24 YIELD_VALUE
             25 POP_TOP
             26 JUMP_ABSOLUTE            3
        >>   29 LOAD_CONST               0 (None)
             32 RETURN_VALUE

while the bytecode for the dict comprehension looks like this:

>>> dis.dis(compile('{a:b for a,b in zip(x,y)}', '', 'eval').co_consts[0])
  1           0 BUILD_MAP                0
              3 LOAD_FAST                0 (.0)
        >>    6 FOR_ITER                21 (to 30)
              9 UNPACK_SEQUENCE          2
             12 STORE_FAST               1 (a)
             15 STORE_FAST               2 (b)
             18 LOAD_FAST                2 (b)
             21 LOAD_FAST                1 (a)
             24 MAP_ADD                  2
             27 JUMP_ABSOLUTE            6
        >>   30 RETURN_VALUE

The major difference between the two is that where the former has
BUILD_TUPLE followed by YIELD_VALUE, the latter just has MAP_ADD. That
looks to be more efficient on two counts: one, that it avoids building
a tuple on every iteration; two, that it invokes code to contribute to
the dict directly, versus going through all the machinery of yielding
a value to be consumed by the dict() function.