Does Python optimize lambda x: x

Question

So I wrote some code for a max/min that assumes a bottleneck on generating the data (else I'd just use max and min), and it takes a key function, which if not given uses an identity function:

if key is None:
    key = lambda x: x

and then later:

for i in iterable:
    key_i = key(i)

And since the bottleneck is on the generator, the question might be moot, but if there's no key, I call lambda x: x for every item. I would assume that Python could optimize this identity function away. Can someone tell me if it does? Or if it doesn't, how expensive is it? Is there a way to do this better without doubling my line count (e.g. ternary operators)?

Answer 1

Good question ! An optimizer could see that foo might be an identity function under certain predictable conditions and create an alternative path to replace it's invocation by it's known result

Let's see the opcodes :

>>> def foo(n):
...     f = lambda x:x
...     return f(n)
... 
>>> import dis
>>> dis.dis(foo)
  2           0 LOAD_CONST               1 (<code object <lambda> at 0x7f177ade7608, file "<stdin>", line 2>) 
              3 MAKE_FUNCTION            0 
              6 STORE_FAST               1 (f) 

  3           9 LOAD_FAST                1 (f) 
             12 LOAD_FAST                0 (n) 
             15 CALL_FUNCTION            1 
             18 RETURN_VALUE         

CPython (2.7 and 3.3 tested) does not seem to optimize out the lambda call. Perhaps another implementation does ?

>>> dis.dis(lambda x:x)
  1           0 LOAD_FAST                0 (x) 
              3 RETURN_VALUE   

The identity function doesn't do much. So you basically have 2 LOAD_FAST, 1 CALL_FUNCTION, and 1 RETURN_VALUE to optimize out every time you call the identity function, versus the creation of a reliable alternative path (which might be more complicated than it appears for the interpreter as @viraptor says).

Maybe an else path in the python code is just better.

The real optimization you did on your min/max example was to reduce the number of invocations of the function by storing it's result. It's now called n times instead of n*4, and thats a fair gain !

Answer 2

Performance Check

No one's done a performance check here yet, so here's what I think is likely to be the better alternatives: use a ternary operation or separate control flow (I'm pretty sure separating control flow will be the best solution).

To test them, in Python 3:

import timeit

setup = """
def control_flow(iterable, key=None):
    if key is None:
        for i in iterable:
            pass
    else:
        for i in iterable:
            key_i = key(i)

def identity_lambda(iterable, key=None):
    if key is None:
        key = lambda x: x
    for i in iterable:
        key_i = key(i)

def ternary(iterable, key=None):
    for i in iterable:
        key_i = key(i) if key else i
"""
print('Testing no lambda')
timeit.timeit('control_flow(range(100))', setup=setup)
timeit.timeit('identity_lambda(range(100))', setup=setup)
timeit.timeit('ternary(range(100))', setup=setup)
print('Testing with lambda')
timeit.timeit('control_flow(range(100), lambda x: -x)', setup=setup)
timeit.timeit('identity_lambda(range(100), lambda x: -x)', setup=setup)
timeit.timeit('ternary(range(100), lambda x: -x)', setup=setup)

And here's results:

Testing no lambda
1.8421741100028157
10.212458187001175
3.39080909700715

Testing with lambda
14.262093641998945
14.405747531011002
14.198169080002117

And so I think the best alternative is to separate control flow, effectively doubling the code under each branch, instead of using lambda x: x, at least in this situation. What I think can most importantly be learned here is that Python does not optimize for identity functions, and that sometimes performance improvements can be had for more lines of code, although at the cost of less maintainability and greater possibility of errors.

Answer 3

Unfortunately, lambda x: x just created some function, which—when looking from the outside—we have no idea about what it does. Of course, at that point, we theoretically can realize that it’s just an identity function, making its computation rather redundant. But even then, we just store this function in a variable and be done with it for now.

Then later, we call the name, executing the underlying function. Because it’s a function, and we don’t know anything about the function, we can’t tell what it does, so we just have to execute it. An optimizer technically could see that it’s an identity function and skip the call, returning just the value directly, but it would be difficult to do this in Python. The Peephole optimizer already takes some bytecode instructions out when it sees some possibilities, but in this case, this would be hard to do:

A call of a name is usually a LOAD_FAST followed by loads for parameters, and then a CALL_FUNCTION. This immediately follows from the syntax of something(args). So a theoretical optimizer would have to skip the first load and the call function. But to even consider this, it would have to know that the name loaded at first refers to an identity function.

Now, the way the Peephole optimizer works, it doesn’t work on dynamic variable content. Even if we had some kind of flag we could attach to the function so we could quickly check if it’s an identity function or not, the optimizer still wouldn’t be able to read that because it doesn’t operate on the underlying data. It only operates on bytecode operations, reducing stuff like LOAD_GLOBAL True to LOAD_CONST True.

And to be honest, introducing such flags for an identity function would be rather odd. Identity functions are already rare; and if we were to optimize that, we could just as well inline all lambdas we have and just reduce the overhead of function calls completely. But that’s simply not what the Peephole optimizer or any (?) optimizer for an interpreted language does. The overhead during the run-time would probably just be too big and negatively impact the overall performance for a micro-optimization.

Because more often than not, such a level of optimization is simply not worth it. Such a function call is rarely a bottleneck for your application, and if it is, you will have to consider optimizing it differently anyway.

Answer 4

CPython does not optimize that out. How could it? It can't know that that's an identity function until it's called.