Python 2.0b1 List comprehensions are slow

[Skip Montanaro]

    Kevin> Unfortunately, I'm a little concerned about the speed of the new
    Kevin> list feature.  According to the web site, "[a comprehension] is
    Kevin> more efficient than map() with a lambda."  However, this is not
    Kevin> true in my test programs - they show comprehensions to be 50%
    Kevin> slower than map with a lambda.

That's a mistake (in my opinion) that nobody noticed before the 2.0b1
release.  I'd treat it as a documentation bug.  For other interested
parties, the relevant page that needs to be edited is

    http://www.pythonlabs.com/tech/python2.0/news.html

In the tutorial it states:

    List comprehensions provide a concise way to create lists without
    resorting to use of map(), filter() and/or lambda.  The resulting list
    definition tends often to be clearer than lists built using those
    constructs.

If you look at the bytecode generated by a list comprehension it should be
about the same as that generated for an equivalent set of nested for and if
statements.  One of the reasons to use map instead of a for loop is that it
is often more efficient (essentially pushing the loop indexing machinery
from the Python VM into C).  This isn't going to change with list
comprehensions, certainly not in the short term.

I modified your test to include test functions that use regular for loops.
Not too surprisingly, list comprehensions are slightly faster than for
loops:

    Many repeated calls on small lists:
    map + operator: 10.16 cpu seconds
    map + lambda: 9.26 cpu seconds
    comprehensions: 13.44 cpu seconds
    for loops: 16.47 cpu seconds

    One call on a large list:
    map + operator: 6.12 cpu seconds
    map + lambda: 4.83 cpu seconds
    comprehensions: 8.86 cpu seconds
    for loops: 10.51 cpu seconds

This is Python compiled with OPT=-g on a recent Mandrake system (450MHz PIII
laptop, gcc 2.95.2).

    Kevin> I hope this can be resolved before 2.0 is released.  :-)

Here's the URL to submit a patch to Python at SF:

    http://sourceforge.net/patch/?func=addpatch&group_id=5470

:-)

Seriously, inputs on how to improve the generated code are welcome, though
I'm skeptical there's much that can be done (the list's append method is
already cached as I recall, which is where the speedup over for loops comes
from), certainly before 2.0final.  If a significant speedup was possible
without a major reworking of the Python VM, I think we'd have seen it by now
in the bytecode generated for for loops.

-- 
Skip Montanaro (skip at mojam.com)
http://www.mojam.com/
http://www.musi-cal.com/