What is the time complexity of a function lookup operation in Python

Question

I'm wondering, since one common optimization strategy is to "cache" the lookup inside a variable and then call the method/function using that variable, how expensive is the lookup action?

This is what I mean by "caching" the lookup in case it's not the right term:

class TestClass:

    def myMethod(self):
       printMethod = self.printMethod
       for i in range(0, 1000):
          printMethod(i)

    def printMethod(self, i):
       print i

Answer 1

The savings doesn't come in time complexity, it comes in actual time. Looking up a function name in a namespace is just looking up a key in a dictionary, which is already O(1). Looking up an attribute on an object is also a dict lookup, which is again O(1). There is an optimized opcode for looking up local variables by name, but that still can't be any faster than O(1).

In your example, looking up self.printMethod looks up a local (self) and then an attribute (printMethod). That's two lookups. If you store it in a local, then every subsequent access to the local variables printMethod is just one lookup instead of two. That's still O(1), but it's faster because it's a smaller constant.

This question has some further discussion of how name lookups work in Python.

Answer 2

Here is some code you can use to time the difference:

http://pastebin.com/svBN5NZ9

And some timing results:

In [2]: %timeit Class1().runCached(10000)
1000 loops, best of 3: 1.74 ms per loop

In [3]: %timeit Class1().runNormal(10000)
100 loops, best of 3: 2.92 ms per loop

In [4]: %timeit Class10().runCached(10000)
1000 loops, best of 3: 1.7 ms per loop

In [5]: %timeit Class10().runNormal(10000)
100 loops, best of 3: 6.01 ms per loop

In [6]: %timeit Class100().runCached(10000)
1000 loops, best of 3: 1.7 ms per loop

In [7]: %timeit Class100().runNormal(10000)
10 loops, best of 3: 42.9 ms per loop

So in general caching the method is faster and the method lookup time depends on the depth of the class inheritance hierarchy.

But note that you might get different results if you use a tracing JIT like pypy since tracing might effectively cache the method pointer for you.

Answer 3

Two O(1) operations can take very different times. Both instance attribute lookup (self.printMethod) and local variables are O(1), but local variable access is optimized so that no dictionary lookup is required, so it's quicker. Look at the bytecode for access to a local variable vs an instance variable in CPython:

>>> import dis
>>> class MyClass:
...   def printMethod(self):
...     pass
...   def code(self):
...     pm = self.printMethod
...     self.printMethod()
...     pm()
...
>>> dis.dis(MyClass.code)
  5           0 LOAD_FAST                0 (self)
              3 LOAD_ATTR                0 (printMethod)
              6 STORE_FAST               1 (pm)

  6           9 LOAD_FAST                0 (self)
             12 LOAD_ATTR                0 (printMethod)
             15 CALL_FUNCTION            0
             18 POP_TOP

  7          19 LOAD_FAST                1 (pm)
             22 CALL_FUNCTION            0
             25 POP_TOP
             26 LOAD_CONST               0 (None)
             29 RETURN_VALUE
>>>

You can see that accessing pm takes a simple LOAD_FAST operation, which loads a value from a fixed numerical offest in the local stack frame, while accessing self.printMethod requires an additional LOAD_ATTR operation.

Of course it does take time to establish the value of the local variable, so it has to be used multiple times (as it is in your code sample) to see any performance benefit.

As @user5402 points out, your mileage may vary depending on the implementation you use due to optimizations on the part of the compiler.