Python 2.0b1 List comprehensions are slow

[Alex Martelli]

"Skip Montanaro" <skip at mojam.com> wrote in message
news:14778.60326.721002.701285 at beluga.mojam.com...
>
>     Robin> seems to me that this kind of code could be optimised by using
>     Robin> the map idiom. To me
>     Robin>         [expr for x in L] seems to correspond to
>     Robin>         map(lambda vars: expr,L)
>
> Yes, except that all expressions in list comprehensions have access to the
> current local scope.  Anything pushed into a lambda would lose that scope.
> Generation of the lambda would have to know the details of the local and
> global variables referenced in the expression and build the lambda
> accordingly.  I think that would require more information than the current
> code generator has at its disposal.

Would it...?  The codeobject corresponding to the lambda does seem to
have all of this info at its disposal...:

>>> lam=lambda x,y,z=12: x+y+z+t+u
>>> lam.func_code.co_varnames
('x', 'y', 'z')
>>> lam.func_code.co_names
('x', 'y', 'z', 't', 'u')
>>>

The codeobject doesn't know about default values (which local variables
are them, and what those values are), but it does seem to know about
non-local identifiers referenced in the code (those in co_names that
are not also in co_varnames).  What am I missing...?

>
> (thinking out loud... on the other hand, could you maybe generate a
special
> anonymous function that refers to the locals of the function in which it
was
> defined?)

Yes, new.function should allow that.

I'm not _quite_ sure, as the whole new module is deliberately
underdocumented
and a better understanding of the Python runtime internals would help, but
this does appear to work...:

Python 2.0b1 (#4, Sep  7 2000, 02:40:55) [MSC 32 bit (Intel)] on win32
Type "copyright", "credits" or "license" for more information.
IDLE 0.6 -- press F1 for help
>>> import new
>>> def makadder(increment):
 def adder(x):
  return x+increment
 return new.function(adder.func_code, locals())

>>> p3=makadder(3)
>>> p3(102)
105
>>> p5=makadder(5)
>>> p3(100)
103
>>> p5(100)
105
>>>

It's not truly 'anonymous', but I don't think that hurts things...:

>>> dir(p3)
['__doc__', '__name__', 'func_code', 'func_defaults', 'func_doc',
'func_globals', 'func_name']
>>> p3.func_name
'adder'
>>> p3.__name__
'adder'
>>> p3.func_globals
{'increment': 3, 'adder': <function adder at 00B502DC>}
>>> p5.func_globals
{'increment': 5, 'adder': <function adder at 00B58F9C>}
>>>

And although the function-object 'adder' ends up existing in two
versions, the code object is, as predictable and desirable, shared:

>>> p3.func_code
<code object adder at 00B53840, file "<pyshell#5>", line 2>
>>> p5.func_code
<code object adder at 00B53840, file "<pyshell#5>", line 2>
>>>


I'm sure there are good and sound reasons to keep module new "mostly
underdocumented", but some parts of it appear to provide crucial and
highly desired (and desirable) features, so it would be know to hear
more about them (particularly, what's _guaranteed_ to work, what only
_happens_ to work because of to-be-one-day-removed implementation
quirks, and what will already break today in strange/obscure cases...);
maybe one of Those Truly In The Know will deign to write an essay on
it for us humble peons out here...?

In particular, new.function seems to be extremely useful for higher
order functions (aka 'functionals') that need to generate new
function-objects on the fly (particularly for 'closure' purposes,
where the needed code-object is all ready, and one only needs to do
the bindings appropriately...).

However, the performance implications are also unclear to me.
Consider a few 'equivalent' definitions, such as:

>>> def withlambda(n):
 return map(lambda x: x*x, range(n))
>>> def withcompre(n):
 return [x*x for x in range(n)]
>>> def withlocfun(n):
 def square(x):
  return x*x
 return map(square, range(n))
>>> def square(x):
 return x*x
>>> def withglofun(n):
 return map(square, range(n))

Performance appears to be roughly like (best-out-of-3 for each):
>>> profile.run('junk=withlambda(10000)')
         10003 function calls in 0.886 CPU seconds
>>> profile.run('junk=withcompre(10000)')
         3 function calls in 0.063 CPU seconds
>>> profile.run('junk=withlocfun(10000)')
         10003 function calls in 0.883 CPU seconds
>>> profile.run('junk=withglofun(10000)')
         10003 function calls in 0.877 CPU seconds

So, there appears to me to be no significant difference between
the various map versions (lambda, local function, global function),
while the list-comprehension is over an order of magnitude faster
by avoiding the function-calls that map always needs.

If the function-call is used anyway...:
>>> def withcomfun(n):
 return [square(x) for x in range(n)]

then the comprehension does become slower than map, by a repeatable
10%-or-slightly-more:
>>> profile.run('junk=withcomfun(10000)')
         10003 function calls in 0.995 CPU seconds

but if the function-call can be avoided thanks to the comprehension,
the performance advantage is _huge_, as we've seen.

Sometimes the function-calls can be avoided with a lookup table:
>>> tab=[x*x for x in range(10000)]
>>> def withcomtab(n):
 return [tab[x] for x in range(n)]
>>> profile.run('junk=withcomtab(10000)')
         3 function calls in 0.067 CPU seconds
This may seem pointless here, but could be precious if the
sequence to be mapped or comprehended was more complex than
just range(n), such maps/comprehensions had to be repeated
often, and the computations per-element were complex:-).


Alex