An X-ray of Python

In Chapter 32 you were the processor of Iskra-8, and then you wrote programs for it in assembly language: every variable lives in one of four registers and you have to remember which, a loop is a jump to a label, and multiplying two numbers takes a dozen lines. Before that, for thirty-odd chapters, you wrote for x in a: without wondering what the line turns into. Somebody has to stand between s += x and the transistors of Chapter 29 and translate. Who is it, and what does the translation cost?

This chapter is an X-ray room. The patient is a five-line function that sums a list. We will X-ray it layer by layer: the bytecode Python turns it into, the same function in C, the machine code of an x86 processor and, finally, Iskra-8. Each X-ray shows something the others hide: who carries out the instructions, where the variables are kept, what a single addition costs. Last comes a timing run. It shows why a Python loop is tens of times slower than a loop in C, and what you get in return.

Five X-rays of one function

Before reading the X-rays one at a time, lay them side by side. On the left of the widget is the Python source, on the right the layer you choose. Colors mark which code does which job: setting up s = 0, walking the list, the addition, returning the answer. Tap a line or a colored tag, and everything doing that job lights up on the other X-ray. The “One element” button plays what runs for a single element of the list.

Go through the layers and compare the counts per element. The single line s += x became three bytecode instructions, one line of C, one x86 machine instruction and two Iskra-8 instructions. At first glance bytecode is not much longer than machine code: six instructions per element against four. The catch is who carries them out. Machine code is run by the processor itself, but the processor has never heard of bytecode: another program reads it. That program is where we begin.

X-ray one: bytecode

In Chapter 15 we already looked inside Python with the dis module and saw it translate the expression (a + b) * c into reverse Polish notation for a stack machine. That was an expression with no variables and no loops. This time we X-ray a whole function.

Each line of the output is one instruction. The first column is the number of the source line it belongs to; then comes a label (L1 and L2 mark the places that jumps land on), the name of the instruction, its numeric argument and, in parentheses, what the argument means. A list of instructions like this for a virtual machine is called bytecode: every instruction here takes two bytes, which we will come back to shortly.

Now read the X-ray. LOAD_CONST 0 pushes a zero onto the stack, and STORE_FAST s pops it and stores it in the variable s. A function’s variables are not kept in a dictionary but in a small array inside the call’s frame, each under its own number: a is 0, s is 1, x is 2. The instruction’s numeric argument is that number, which is why LOAD_FAST is quick: no lookup by name, one access to an array slot. Hence the FAST in its name.

Then comes the loop. GET_ITER replaces the list on top of the stack with an iterator, a bookmark that remembers how far we have got. FOR_ITER asks the bookmark for the next element and pushes it; STORE_FAST x stores it in x. The body of the loop is three instructions: LOAD_FAST_LOAD_FAST pushes s and x (in Python 3.13 two loads in a row are fused into one instruction), BINARY_OP += pops two numbers and pushes their sum, and STORE_FAST s stores it. Last, JUMP_BACKWARD jumps back to L1. Like the loops of Iskra-8, this one turns out to be a jump to an address before the current one.

When the elements run out, FOR_ITER drops the bookmark and jumps to L2, skipping two instructions at once: END_FOR and POP_TOP are there for special cases, and an ordinary loop jumps over them. All that remains is to push s and return it with RETURN_VALUE. The instruction at the top, RESUME, is housekeeping: it marks the start of the function.

In the explorer below you can walk through the same thing step by step: the source and the bytecode on the left, the value stack and the frame’s variables on the right. A counter next to each instruction shows how many times it has run, and the body of the loop soon pulls ahead of the rest.

Try gcd, Euclid’s algorithm from a task in Chapter 5. The line a, b = b, a % b becomes a little dance on the stack: push b and a, push b once more, take the remainder, and STORE_FAST_STORE_FAST deals the top two values out to the variables crosswise. There is no temporary variable: the stack stands in for one. And the condition while b appears twice in the bytecode, before the loop and at the end of the body: that is how CPython translates every while.

Bytes

What dis prints is a decoding. The bytecode itself is made of bytes, and they are kept in the attribute __code__.co_code, next to the table of constants and the names of the variables. Here they are, cut into pairs.

Thirty-six bytes. In each pair the first byte is the number of the operation and the second is the argument: 149 0 is RESUME, and 83 1 is LOAD_CONST with constant number 1 (number 0 is where Python keeps None). This is built like the machine code of Iskra-8 in Chapter 32: an opcode and an operand, except that on Iskra not every instruction has an operand. The strange pairs 0 0 named CACHE are never executed: they are reserved slots where the interpreter writes notes to itself, right inside the bytecode. What the notes are for, you will see two sections from now.

A loop inside a loop

The processor doesn’t understand these bytes: it has its own instruction set, and 149 means nothing to it. The bytecode is run by the program you start with the word python. It is called CPython, it is written in C, and at its heart is a loop: take the next instruction, read its opcode, go to the piece of the program that performs that operation, repeat. This is the fetch–decode–execute cycle of Chapter 32, done by a program instead of wires. What you get is a processor made of software, with its own instruction set and its own memory: a virtual machine. A program that carries out another program’s instructions one after another, without translating the whole thing in advance, is called an interpreter.

A virtual machine is easy to write yourself. Here is a stack machine in a dozen lines: it has four instructions, and a program for it is a list of “operation, argument” pairs.

Press “Steps”: pc runs along the program while the stack grows and shrinks, as in the explorer. In CPython itself the main loop lives in the file Python/ceval.c, and since version 3.12 the bodies of the instructions are described separately, in Python/bytecodes.c, from which C code is generated. There are over a hundred ordinary instructions in it, plus some seventy specialized versions that we will meet in a moment, but they all work the same way. In the task at the end of the chapter you will give your machine variables and jumps, and it will learn to run loops.

Now you can see where the time goes. The processor runs the interpreter’s machine code, and for every bytecode instruction the interpreter fetches it, decodes it, jumps to the right handler and only then does the work itself. For LOAD_FAST the work is one read from an array, and the machinery around it costs more than the read. That machinery is the cost of interpretation, and it is paid on every instruction.

Python adapts

Interpretation has a second, less visible cost. The instruction BINARY_OP += doesn’t know what it is adding. The bytecode for 1 + 2, "ab" + "cd", [1] + [2] and 0.5 + 1.5 is the same, yet the actions are completely different. So at every addition the interpreter has to check the types and choose what to do. C has no such checks: the type of every variable is known in advance, and the compiler puts in the right machine instruction straight away.

Since version 3.11 CPython has had a way around this. It is called the specializing adaptive interpreter (PEP 659, by Mark Shannon and the Faster CPython project). Once an instruction has run a couple of times, the interpreter looks at the types it works with and swaps it, right in the bytecode, for a specialized version: for integers, for floats, for lists. The CACHE slots we saw among the bytes serve as its notepad. You can catch the swap in the act: dis with adaptive=True shows the bytecode in its current, adapted form.

BINARY_OP has turned into BINARY_OP_ADD_INT, and FOR_ITER into FOR_ITER_LIST. The specialized version still checks the types, but with a single quick test: are both integers? If so, it adds at once; if not, it falls back to the general path and in time adapts again. Change [1, 2, 3] in the warm-up to [0.5, 1.5] and run the cell again, and you will see BINARY_OP_ADD_FLOAT. Python adapts to the way a program is used in practice, but it can never drop the check altogether: next time someone may pass the function strings.

X-ray two: C

To see the same sum without an interpreter, we have to rewrite it in a language that translates straight into machine code. The best-known such language was born together with the operating system that the server of this course runs on today.

Here is our patient in C.

The C code here is a string inside Python: the sandbox module cs.c hands it to the tcc compiler, which translates it into machine code in memory and runs it. Compare it with Python. Every variable is declared with its type: long is a 64-bit integer, the size of a processor register. The list has become an array, and an array doesn’t know its own length, so n has to be passed separately. And the parameter a is not even an array but the address of its first element. The asterisk in const long *a reads like this: “a is an address where a long is stored.”

Addresses in hand

In Chapter 14 we dug addresses out with the ctypes microscope and derived a formula: element number $i$ lies at address $\text{start} + 8i$. Python hid addresses behind labels, and to see them we had to dissect objects. In C an address is an ordinary value: you can keep it in a variable, add to it and print it. A variable that holds an address is called a pointer.

The addresses of the elements of a go up in steps of 8, those of b in steps of 4: an int takes four bytes. The formula from Chapter 14 works for any type; only the size changes. Run the cell again and the numbers will be different. On every run the system puts the program’s stack at a new random address. This is a defense, and Chapter 61 explains it.

The last line gathers up all of pointer arithmetic. &x gives the address of x, and *p whatever lies at address p. When you add one to a pointer, C adds the size of an element to the address, so *(p + 2) is element number 2. And by the definition of the language, a[i] means *(a + i). Addition doesn’t care about order, so 2[a] is the same as a[2], and the compiler accepts it. Nobody writes that, but the oddity shows that square brackets in C are only shorthand for address arithmetic. In an expression an array turns into the address of its first element, which is why the function total receives a pointer.

X-ray three: x86-64 machine code

C is still not machine code; a compiler translates it. To see the result, we need one compromise. The course sandbox isn’t tied to one processor: it may be running on x86-64 (Intel, AMD) or on ARM, and their machine codes differ. The listings below were therefore made in advance, by the clang compiler for x86-64, in Intel assembly syntax. This architecture runs most servers and personal computers, and this is how it sees our sum.

This is the translation with -O1 (“optimize, but don’t get carried away”); the comments after # are ours. The loop takes four instructions. add rax, qword ptr [rdi + 8*rcx] reads eight bytes at the address $\text{rdi} + 8 \cdot \text{rcx}$ and adds them to rax: the address formula from Chapter 14 is written into the instruction, and the processor computes it by itself, in one step. inc rcx is i++. cmp rsi, rcx compares n and i, and jne .L4 jumps back if they differ, like JNZ loop on Iskra-8. Before the loop, two xor instructions zero i and s, while test rsi, rsi and jle send an empty array straight to the answer 0.

The compiler expects a in rdi and n in rsi because of an agreement. Functions in C are written by different people and compiled by different compilers, yet they must call one another without mistakes. So for every system there is a written calling convention. On Linux for x86-64 it says: the first six integer arguments arrive in the registers rdi, rsi, rdx, rcx, r8, r9, the rest on the stack, and the function leaves its answer in rax. That is why total has no “return s” instruction at the end: the sum has been piling up in rax from the start, and all ret has left to do is hand back control.

Now switch the optimization level. At -O0 the compiler translates every line word for word: each variable gets a place in memory, and even for i++ the variable is read from memory, incremented and written back. At -O1 the variables move into registers, and the loop shrinks to a third. At -O2 the loop grows longer again: the compiler adds numbers in pairs in the 128-bit xmm registers and handles four elements per lap. How one instruction can work on several numbers at once is the subject of Chapter 35.

The other functions hold surprises. At -O1 the recursion in fact has vanished: the compiler realized that the multiplications can be done on the way down and turned the function into a loop. In max and dist there is no jump for the if: the instructions cmovg (“move if greater”) and cmovge (“move if greater or equal”) pick a value without any branching. In swap the temporary variable t has dissolved into a register. A compiler may rewrite a program however it likes, as long as the result stays the same.

The stack frame

ret “hands back control,” but to whom? The function total may be called from a hundred places. In Chapter 5 we saw how David Wheeler solved this on EDSAC: before jumping into a subroutine, the caller told it its own address. We also saw the flaw in his method: the return address was kept in a single copy, so a subroutine could not call itself.

Modern processors keep the return address on the stack. The instruction call f pushes the address of the instruction that follows it and jumps to f. The instruction ret pops that address off the stack and jumps to it. Each call pushes its own return address, so calls can nest as deep as you like, as long as the stack holds out. Next to the return address a function keeps its variables and the saved values of registers. The whole stretch of stack that belongs to one call is called a stack frame. We drew such frames in Chapter 5; now each of them has an address in memory.

Step through the “call” program one line of C at a time. main calls sum_sq, which calls square twice. Every call pushes a return address, and every function begins with the same pair: push rbp saves the frame pointer of its caller, and mov rbp, rsp makes the current top of the stack the start of a new frame. Then sub rsp, … sets aside room for the variables, which means moving the top of the stack down. On return everything happens in reverse. The frame of the second call to square lands where the first one was and overwrites the garbage it left. To free a frame is to move the top of the stack, without erasing anything.

In the “recursion” program, fact(3) calls fact(2), which calls fact(1), and the stack holds three frames of the same function at once, each with its own n and its own return address. This is what the call stack of Chapter 9 looks like in memory. If a recursion never stops, Python notices: it keeps track of the depth and raises RecursionError after a thousand frames. C keeps track of nothing.

Signal 11 is SIGSEGV, a memory access violation. The frames grew downward until they hit the edge of the region set aside for the stack, the processor reported an attempt to touch memory that didn’t belong to the program, and the system killed it. No traceback, no line number.

Past the end of the array

A frame is a tightly packed strip of memory: the variables, the saved rbp and the return address lie right next to one another. What happens if a program writes more elements into an array than it has room for? Python answers with an IndexError: before every write by index it checks the bounds. C doesn’t check. That would cost an extra instruction on every access, and the language was made for speed.

In the “past the end” program, the function work sets up an array buf of four numbers and asks fill to write k sevens into it. Move the slider and step through the program. With k = 5 the fifth seven lands in empty padding that the compiler left between the variables, and nothing happens. With k = 6 it overwrites work’s own variable k; with k = 7, the saved frame pointer of main. The program still finishes as if nothing were wrong: it never needs the spoiled values again. But with k = 8 the seven lands on the return address, and ret jumps to address 7, where there is no code at all.

The worst of it is the silence. A mistake in one place corrupts memory in another, and the program crashes (or doesn’t) much later and somewhere else altogether. The C standard says plainly that writing past the end of an array is undefined behavior: anything may happen, and the compiler owes you nothing. Here is the same thing without a stack: an array in a struct, and the variable next to it.

One extra iteration, and secret has become zero. Now suppose the data being written came from outside, from the network or a file, and was chosen so that the return address pointed wherever an attacker wanted. That is how, in 1988, the Morris worm got into computers, among other ways through a buffer overflow in the finger network service. Chapter 61 has more about this class of bugs and the defenses against it. For now one conclusion is enough: bounds checking in Python is part of the price it pays to make such mistakes loud.

X-ray four: Iskra-8

The last X-ray goes deepest: on it you can see the wires. Here is our function once more, now for Iskra-8 from Chapter 32, written by hand the way a compiler would write it. The pointer to the array arrives in R0, the length in R1, and the answer goes back in R2: we made up this calling convention ourselves, and it is no worse than Linux’s.

Put the x86 listing at -O1 next to it. The single instruction add rax, qword ptr [rdi + 8*rcx] splits in two on Iskra: LDR reads a byte at the address held in a register, and ADD adds it. Iskra has no address formula, so instead of an index i we move the pointer itself: INC R0 is a++. The step is 1, not 8, because an element takes one byte. The counter runs down to zero, and DEC sets the Z flag on its own, so no separate comparison is needed. CALL and RET work as on the big processor: the return address goes onto the stack at SP, the Wheeler jump in hardware from Chapter 32.

Change the data to .byte 200, 100 and the length in R1 to 2. Iskra prints 44: its registers are eight bits wide, and the sum is taken modulo 256. This is the overflow of Chapter 11, in eight bits instead of sixteen. In Python you never have to think about it, since its integers grow as large as they need to. That is one more check it makes for you on every addition.

The five X-rays add up to a chain. Python compiles the text into bytecode. The bytecode is run by an interpreter, which is itself a C program compiled into machine code. The machine code is run by a processor built from gates. Translating from one language to another is a compiler’s job. In Chapter 52 you will write one of your own, for Iskra-8: lines in a small language will turn by themselves into listings like this one.

Translator and interpreter

A book in a foreign language can reach its reader in two ways. A translator translates the whole book in advance, and the reader gets a finished text without ever seeing the original. An interpreter sits beside the reader and renders it sentence by sentence, every time the book is read. The first way is a compiler: C is translated into machine code once, and after that the program runs without the compiler. The second way is an interpreter, and English uses the same word for the person and for the program. CPython combines the two: first it compiles the text into bytecode (this is quick, and for imported modules the result is also saved in a __pycache__ folder so the work isn’t repeated), and then it interprets the bytecode.

One thing that keeps Python from compiling straight to machine code is that the text doesn’t say what s += x will be adding: integers, floats or strings. That only becomes clear while the program runs. Hence a third way, JIT compilation, short for “just-in-time.” The runtime first interprets the program, watches which pieces run most often and with which types, and translates those pieces into machine code. That is how Java works, and JavaScript in your browser, and PyPy, another implementation of Python. CPython 3.13 gained an experimental JIT compiler (PEP 744), switched off by default. The specialization we caught in the bytecode section is a first step down that road.

Interpretation has a virtue too, and this chapter has already benefited from it. Bytecode is the same on every processor: dis would show the same instructions on an ARM laptop and on an x86-64 server, while machine code has to be compiled for each of them separately. That is why we prepared the x86 listings in advance but got the bytecode straight from the sandbox. It is the portability Ritchie made C for, moved one floor higher.

Timing: Python against C

Time to put a number on the cost. We take a loop that does almost nothing but arithmetic and run it three ways: in pure Python, with numpy (where the loop is written in C inside the library) and in C. The C program times itself with the clock() function; for Python we use timeit.

On the course server we got a few tens of nanoseconds per step for Python, about two for numpy and around one for C. Your numbers will differ, since they depend on the processor and on whatever else it is busy with, but the order of magnitude will hold: Python is tens of times slower. And that is against tcc, the compiler in the sandbox, which does almost no optimization. An optimizing compiler would make the C loop faster still.

Now we can account for every nanosecond. Run work through dis: each step of the loop takes ten bytecode instructions. Each of them is a lap of the interpreter’s loop: fetch, decode, jump to the handler. Each BINARY_OP checks types. The numbers i * i climb to nine trillion and don’t fit among the small integers Python keeps ready-made, so nearly every intermediate value is a new object on the heap, which has to be created and then freed when the count of references to it (the first field of the object header in Chapter 14) drops to zero. In C a step takes a couple of dozen machine instructions, and i * i is a single multiplication among them. And that is with tcc, which keeps even i and s in memory rather than in registers.

Here is a rule you can use tomorrow. If a program is slow, first find out where it spends its time, with the profiler from Chapter 13. Almost always it is one inner loop. Hand that loop to code written in C: built-in functions (sum, sorted, str.join, collections.Counter), numpy for numbers, and if nothing ready-made fits, a C extension module or some other way of compiling. Let the other ninety percent of the program stay in comfortable Python.

Tasks

What next

The cost of every layer is now visible in nanoseconds, and it may seem that we know all there is to know about speed: fewer instructions, faster program. Put that to the test with a $4096 \times 4096$ matrix stored in memory row after row. We add up its elements twice, first by rows, then by columns. The work is identical: the same sixteen million additions, the same numbers, the same code, except that the two loops have swapped places.

The sums agree, but the times don’t: for us, walking by columns came out about six times slower. The number of machine instructions is the same, so they are not to blame. Apparently memory doesn’t answer every request equally fast: some of what it holds lies near, and some lies far away. How far, and why, is the subject of Chapter 34.