934
def main():
    for i in xrange(10**8):
        pass
main()

This piece of code in Python runs in (Note: The timing is done with the time function in BASH in Linux.)

real    0m1.841s
user    0m1.828s
sys     0m0.012s

However, if the for loop isn't placed within a function,

for i in xrange(10**8):
    pass

then it runs for a much longer time:

real    0m4.543s
user    0m4.524s
sys     0m0.012s

Why is this?

8
  • 18
    How did you actually do the timing? Jun 28, 2012 at 9:21
  • 56
    Just an intuition, not sure if it's true: I would guess it's because of scopes. In the function case, a new scope is created (i.e. kind of a hash with variable names bound to their value). Without a function, variables are in the global scope, when you can find lot of stuff, hence slowing down the loop.
    – Scharron
    Jun 28, 2012 at 9:22
  • 5
    @Scharron That doesn't seem to be it. Defined 200k dummy variables into the scope without that visibly affecting the running time.
    – Deestan
    Jun 28, 2012 at 9:27
  • 61
    @Scharron you're half correct. It is about scopes, but the reason it's faster in locals is that local scopes are actually implemented as arrays instead of dictionaries (since their size is known at compile-time).
    – Katriel
    Jun 28, 2012 at 10:31
  • 4
    @AndrewJaffe The output would suggest linux' time command. Jun 28, 2012 at 15:35

3 Answers 3

712

Inside a function, the bytecode is:

  2           0 SETUP_LOOP              20 (to 23)
              3 LOAD_GLOBAL              0 (xrange)
              6 LOAD_CONST               3 (100000000)
              9 CALL_FUNCTION            1
             12 GET_ITER            
        >>   13 FOR_ITER                 6 (to 22)
             16 STORE_FAST               0 (i)

  3          19 JUMP_ABSOLUTE           13
        >>   22 POP_BLOCK           
        >>   23 LOAD_CONST               0 (None)
             26 RETURN_VALUE        

At the top level, the bytecode is:

  1           0 SETUP_LOOP              20 (to 23)
              3 LOAD_NAME                0 (xrange)
              6 LOAD_CONST               3 (100000000)
              9 CALL_FUNCTION            1
             12 GET_ITER            
        >>   13 FOR_ITER                 6 (to 22)
             16 STORE_NAME               1 (i)

  2          19 JUMP_ABSOLUTE           13
        >>   22 POP_BLOCK           
        >>   23 LOAD_CONST               2 (None)
             26 RETURN_VALUE        

The difference is that STORE_FAST is faster (!) than STORE_NAME. This is because in a function, i is a local but at toplevel it is a global.

To examine bytecode, use the dis module. I was able to disassemble the function directly, but to disassemble the toplevel code I had to use the compile builtin.

11
  • 183
    Confirmed by experiment. Inserting global i into the main function makes the running times equivalent.
    – Deestan
    Jun 28, 2012 at 9:33
  • 55
    This answers the question without answering the question :) In the case of local function variables, CPython actually stores these in a tuple (which is mutable from the C code) until a dictionary is requested (e.g. via locals(), or inspect.getframe() etc.). Looking up an array element by a constant integer is much faster than searching a dict.
    – dmw
    Jun 28, 2012 at 21:53
  • 4
    @gkimsey I agree. Just wanted to share two things i) This behaviour is noted in other programming languages ii) The causal agent is more the architectural side and not the language itself in true sense
    – codejammer
    Jul 19, 2012 at 13:28
  • 3
    @Pratik see the documentation for the dis module: docs.python.org/library/dis.html
    – ecatmur
    Oct 24, 2013 at 7:28
  • 3
    @manty write dis.dis(compile('for i in xrange(10**8):\n pass', 'main.py', 'exec'))
    – ecatmur
    Jan 15, 2015 at 18:18
589

You might ask why it is faster to store local variables than globals. This is a CPython implementation detail.

Remember that CPython is compiled to bytecode, which the interpreter runs. When a function is compiled, the local variables are stored in a fixed-size array (not a dict) and variable names are assigned to indexes. This is possible because you can't dynamically add local variables to a function. Then retrieving a local variable is literally a pointer lookup into the list and a refcount increase on the PyObject which is trivial.

Contrast this to a global lookup (LOAD_GLOBAL), which is a true dict search involving a hash and so on. Incidentally, this is why you need to specify global i if you want it to be global: if you ever assign to a variable inside a scope, the compiler will issue STORE_FASTs for its access unless you tell it not to.

By the way, global lookups are still pretty optimised. Attribute lookups foo.bar are the really slow ones!

Here is small illustration on local variable efficiency.

12
  • 7
    This also applies to PyPy, up to the current version (1.8 at the time of this writing.) The test code from the OP runs about four times slower in global scope compared to inside a function.
    – GDorn
    Jun 28, 2012 at 17:17
  • 2
    @Walkerneo The primary conversation going on here is the comparison between local variable lookups within a function and global variable lookups that are defined at the module level. If you notice in your original comment reply to this answer you said "I wouldn't have thought global variable lookups were faster than local variable property lookups." and they're not. katrielalex said that, although local variable lookups are faster than global ones, even global ones are pretty optimized and faster than attribute lookups (which are different). I don't have enough room in this comment for more. Jun 29, 2012 at 0:21
  • 3
    @Walkerneo foo.bar is not a local access. It is an attribute of an object. (Forgive the lack of formatting)def foo_func: x = 5, x is local to a function. Accessing x is local. foo = SomeClass(), foo.bar is attribute access. val = 5 global is global. As for speed local > global > attribute according to what I've read here. So accessing x in foo_func is fastest, followed by val, followed by foo.bar. foo.attr isn't a local lookup because in the context of this convo, we're talking about local lookups being a lookup of a variable that belongs to a function. Jun 29, 2012 at 1:57
  • 4
    @thedoctar have a look at the globals() function. If you want more info than that you may have to start looking at the source code for Python. And CPython is just the name for the usual implementation of Python -- so you probably are using it already!
    – Katriel
    Jul 6, 2012 at 14:45
  • 2
    Yes, and because most of the time the slight slowness isn't actually important to the running speed of the program.
    – Katriel
    Oct 25, 2017 at 20:12
49

Aside from local/global variable store times, opcode prediction makes the function faster.

As the other answers explain, the function uses the STORE_FAST opcode in the loop. Here's the bytecode for the function's loop:

    >>   13 FOR_ITER                 6 (to 22)   # get next value from iterator
         16 STORE_FAST               0 (x)       # set local variable
         19 JUMP_ABSOLUTE           13           # back to FOR_ITER

Normally when a program is run, Python executes each opcode one after the other, keeping track of the a stack and preforming other checks on the stack frame after each opcode is executed. Opcode prediction means that in certain cases Python is able to jump directly to the next opcode, thus avoiding some of this overhead.

In this case, every time Python sees FOR_ITER (the top of the loop), it will "predict" that STORE_FAST is the next opcode it has to execute. Python then peeks at the next opcode and, if the prediction was correct, it jumps straight to STORE_FAST. This has the effect of squeezing the two opcodes into a single opcode.

On the other hand, the STORE_NAME opcode is used in the loop at the global level. Python does *not* make similar predictions when it sees this opcode. Instead, it must go back to the top of the evaluation-loop which has obvious implications for the speed at which the loop is executed.

To give some more technical detail about this optimization, here's a quote from the ceval.c file (the "engine" of Python's virtual machine):

Some opcodes tend to come in pairs thus making it possible to predict the second code when the first is run. For example, GET_ITER is often followed by FOR_ITER. And FOR_ITER is often followed by STORE_FAST or UNPACK_SEQUENCE.

Verifying the prediction costs a single high-speed test of a register variable against a constant. If the pairing was good, then the processor's own internal branch predication has a high likelihood of success, resulting in a nearly zero-overhead transition to the next opcode. A successful prediction saves a trip through the eval-loop including its two unpredictable branches, the HAS_ARG test and the switch-case. Combined with the processor's internal branch prediction, a successful PREDICT has the effect of making the two opcodes run as if they were a single new opcode with the bodies combined.

We can see in the source code for the FOR_ITER opcode exactly where the prediction for STORE_FAST is made:

case FOR_ITER:                         // the FOR_ITER opcode case
    v = TOP();
    x = (*v->ob_type->tp_iternext)(v); // x is the next value from iterator
    if (x != NULL) {                     
        PUSH(x);                       // put x on top of the stack
        PREDICT(STORE_FAST);           // predict STORE_FAST will follow - success!
        PREDICT(UNPACK_SEQUENCE);      // this and everything below is skipped
        continue;
    }
    // error-checking and more code for when the iterator ends normally                                     

The PREDICT function expands to if (*next_instr == op) goto PRED_##op i.e. we just jump to the start of the predicted opcode. In this case, we jump here:

PREDICTED_WITH_ARG(STORE_FAST);
case STORE_FAST:
    v = POP();                     // pop x back off the stack
    SETLOCAL(oparg, v);            // set it as the new local variable
    goto fast_next_opcode;

The local variable is now set and the next opcode is up for execution. Python continues through the iterable until it reaches the end, making the successful prediction each time.

The Python wiki page has more information about how CPython's virtual machine works.

2
  • Minor update: As of CPython 3.6, the savings from prediction go down a bit; instead of two unpredictable branches, there is only one. The change is due to the switch from bytecode to wordcode; now all "wordcodes" have an argument, it's just zero-ed out when the instruction doesn't logically take an argument. Thus, the HAS_ARG test never occurs (except when low level tracing is enabled both at compile and runtime, which no normal build does), leaving only one unpredictable jump. Mar 29, 2019 at 14:56
  • Even that unpredictable jump doesn't happen in most builds of CPython, because of the new (as of Python 3.1, enabled by default in 3.2) computed gotos behavior; when used, the PREDICT macro is completely disabled; instead most cases end in a DISPATCH that branches directly. But on branch predicting CPUs, the effect is similar to that of PREDICT, since branching (and prediction) is per opcode, increasing the odds of successful branch prediction. Mar 29, 2019 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.