The world’s leading publication for data science, AI, and ML professionals.

Many Python programmers cannot solve this puzzle

A brief introduction to "Python under the hood" for beginners

PROGRAMMING

Photo by Priscilla Du Preez on Unsplash
Photo by Priscilla Du Preez on Unsplash

Let me get straight to the puzzle. Are you ready?!! Okay, take a look at these two super simple codes.

Both codes do a dummy task. They take numbers between 0 and 10 million (through a for loop) and calculate their mod (remainder) of 5. So far, super easy. Now, are you interested in measuring their run time?

We only added a simple timer to both codes to measure their runtimes. Since both codes are doing the same simple task, we expect to see the same run times.

Of course, if the run times were the same, I did not write this article. Actually, the run times are 739 ms and 434 ms for Code 1 and Code 2, respectively. SURPRISE!!!!

Photo by Rhys Kentish on Unsplash
Photo by Rhys Kentish on Unsplash

This puzzle is known to some Python programmers. However, most Python programmers do not know about this puzzle because it needs a deeper understanding of how Python works. This article gives you an introduction to "what does happen when you run a python code?"

NOTE: This article is written in a simple language for Python beginners. If you are professional and need some resources go to the "additional resources" section at the end of this article.

What does happen when you run a python source code?

To make it easy, let me focus on the most popular Python implementation called CPython. If you don’t know what Python implementation you are using, there is a 90% chance that you are using CPython.

Here is what happens to your source code when you run it.

What happens when you run a Python source code.
What happens when you run a Python source code.

First, your source code is being broken into tokens through a process called "Lexing." For example, x=1 would be broken into token such as x, =, and1. The tokens are then organized into an abstract syntax tree (AST) through a process called "Parsing." After that, a "Compiler" converts everything to an abstract code called "Bytecode."

It is important to understand that in Python, unlike other languages (e.g., C, C++, Java, etc.), the compiler does not take the "source code" and convert it to the "machine code." Instead, the compiler takes the "source code" and converts it to a "Bytecode." It is the Interpreter’s task to take the bytecode and run it in the way that the machine understands it.

For those of you who are curious to see Bytecodes, sometimes they are stored (cached) as .pyc files on your disk. Believe me, you cannot understand them. Just to satisfy your curiosity!!!

Among the four steps of running a code in Python, the interpreter has the heaviest job to do, and the other three steps are not handling too much of the load. Therefore, any time you want to investigate a Python program’s performance, you should look at the interpretation step and look for some clues.

The interpreter reads the bytecode and runs its instructions. If bytecode is like a recipe, instructions are like different steps in that recipe.

If we could read the bytecode, we might have some clues about our puzzle. To take a look at the bytecode instructions, we can use the dis package. dis is a Python package to disassemble and decode bytecodes and display them in a way that human can understand it. The output of thedis.dis() has a structure like this:

Anatomy of an instruction in Python shown with dis library.
Anatomy of an instruction in Python shown with dis library.

I don’t go through the details for the dis package and focus on the one column of Operation Name. Operation name instructs Python interpreter what should be done. If you are too curious, in fact, a file called ceval.c has all the instructions (see here).

I ran dis.dis() for both codes, and to make it simple for you, I highlight the important part, which is the loop portion. The figure below shows the bytecodes for both codes.

Outputs of dis.dis() for Code 1 and Code 2
Outputs of dis.dis() for Code 1 and Code 2

As you see, both codes are very similar in terms of given instructions. But, if you look more closely, you find some subtle (but important) differences in bytecodes. In Code 1, we see STORE_NAME and LOAD_NAME, but in Code 2, we see STORE_FAST and LOAD_FAST. It seems that the run time difference is because of differences in those two types of instructions. You can take a look at ceval.c file to see the differences.

Let me make it simple and clear for you. The interpreter processes variables i and x differently in Code 1 compared to Code 2 (note to _NAME and _FAST suffixes). Both i and x are global variables in Code 1, and CPython stores those variables in a dictionary data structure, making the loading process more time-consuming compared to local variables, which are stored in a fixed-sized array. Retrieving a variable from a fixed-size array is much faster compared to a dictionary. Why does Python do that? Simply because in the main code, we don’t know how many variables will show up, but the number of variables is fixed in a function.

If this is the reason, let’s do a test. Let’s mess with the interpreter and define both x and i variables as global variables in Code 2 (the fast code) and measure the run time again. Here is code 2 after changing.

I ran Code 3, and it took 805 ms (compared to Code 2, which took 434 ms). The number is very close to Code 1 (i.e., 739 ms). It shows that, as we expected, processing on global variables takes more time compared to local variables (fixed-size array vs. dictionary).

Summary

As you see, we could solve the puzzle with a little bit of knowledge about how Python interpreter works and getting help from dis library. Some other factors, for example, "opcode prediction" also contribute to the run time difference, but for the sake of simplicity, we ignored it in this article.

If you are interested to know more about Python’s underhood. I highly recommend this blog series: https://tech.blog.aknin.name/category/my-projects/pythons-innards/

Follow me on Twitter for the latest stories: https://twitter.com/TamimiNas


Related Articles