How Many Lines of C it Takes to Execute a + b in Python?

Understand the mechanics of dynamic dispatch implementation in CPython

Dec 06, 2023

Welcome back to the CPython internals series. In the previous article we explored the PyObject structure, and its role as the header for all CPython runtime objects. This structure plays a crucial role in enabling inheritance and polymorphism in the CPython object system. But that was just the tip of the iceberg

In this article we will go one level deeper, and look at what exactly goes on behind the scenes in the Python runtime to execute something as simple as “a + b”. In other words, we will learn the implementation details behind types, operators, and dynamic dispatch in CPython.

Note that, even though we will be following the implementation of dynamic dispatch for a specific operator, the same ideas apply for all the operators supported by CPython. So effectively, with this knowledge you could implement your own new operator, or your own new type.

If you are a recent subscriber, I’ve written quite a few articles on CPython internals, that you might enjoy. You can find them all here.

a blurry photo of a cell phone with a blue background — Photo by NIKHIL on Unsplash

High Level Design of Dynamic Dispatch in CPython

When we write code such as a + b in Python, the types of a and b determine the exact behavior of the + operation. Every type in Python has its own implementation of the + operator (if that type supports +) and the Python interpreter figures out the right implementation to call based on the type of the operands. This whole process is called dynamic dispatch in programming languages. The following diagram gives a high level overview of how it works in CPython:

High level flow of operator execution in the CPython VM

Let’s briefly discuss the various parts:

The Python code gets compiled to bytecode, which is executed by a stack based virtual machine (VM) in CPython. The BINARY_OP instruction is responsible for executing the + operation on the two operands, a and b.
The VM itself does not know how to perform + on two objects. Instead, it delegates this to an abstract object interface to deal with it.
The abstract object interface in CPython defines an interface supporting all the common object level operations in CPython. This gives the VM a single unified way of executing all the operators without knowing any implementation details of the object system. The abstract interface dispatches the execution to the concrete implementation within the types via the function pointer table lookup in the object header (more on this later).

In the previous article, we briefly explored a part of this flow by looking at the implementation of the BINARY_OP instruction in the CPython VM. This time our goal is to properly understand how the dynamic dispatch happens. For this reason, we are going to follow a bottom up approach.

We will start by looking at how the different types implement various operators, then we will look at the abstract object interface and see how it calls those concrete implementations, and finally, we will see how the CPython VM integrates with the abstract object interface.

Dissecting the PyTypeObject Structure

The PyTypeObject struct is the second building block of the CPython object system (first being PyObject). It contains the runtime type information about an object. Before we look at dynamic dispatch in CPython, we should first understand what’s inside PyTypeObject.

But first, let’s just recap, and see the definition of PyObject, which is where PyTypeObject comes into picture:

Also, every type definition in CPython includes PyObject as its first field as a header. For instance, this is the definition of the float type:

This means that every such object can be typecast to PyObject (see the previous article on PyObject to understand how), and because PyObject includes a pointer to PyTypeObject, the CPython runtime has all the type related information about the object available to it at all the times.

Now, let’s look inside PyTypeObject. It’s a very large object with dozens of fields. The following figure shows its full definition:

The PyTypeObject struct stores the runtime type details about the object, such as the type name, type size, functions to allocate and deallocate an object of that type.

Apart from that, it also stores function pointer tables for supporting various type specific behaviors. For instance, the tp_as_number field is one such table. It is a pointer to an object of type PyNumberMethods that defines a function pointer table for numeric operations.

Since we are interested in understanding how CPython executes the binary add (+) operator, we will zoom in and look at what’s inside PyNumberMethods. The following figure shows its definition:

Looking inside PyNumberMethods struct. The left side box is zoomed in definition of PyTypeObject, highlighting the PyNumberMethods field. The right side box is a partial definition of PyNumberMethods

Every type implementation in CPython needs to create an instance of PyNumberMethods struct and populate it with pointers to the functions that it implements for supporting numeric operators. If a type does not support numeric operations, it can simply set the tp_as_number field in PyTypeObject to NULL, which would tell the CPython runtime that this object does not support any of these operations.

Next, as a concrete example, let’s see how the float type implements these functions and then instantiates the PyTypeObject when creating a new float object.

Instantiating Float Types with PyNumberMethods

The following figure shows the code from Objects/floatobject.c which contains the implementation of the float type in CPython.

How the float type implements numeric operators and populates the function pointer table in its instance of PyTypeObject, called PyFloat_Type

Let’s break it down:

The left most side box shows the functions which implement the add, subtract and multiply operations.
Next, the middle box shows an instance of the PyNumberMethods struct (called float_as_number) for the float data type. Notice how it includes the function pointers for the add, multiply and subtract functions.
The right most box shows an instance of the PyTypeObject for creating objects of float type. Notice how it includes a pointer to the float_as_number object.

And, a pointer to float_as_number is included in every float object’s header (i.e. as the value of the ob_type field in PyObject). The following figure shows the function PyFloat_FromDouble, which creates new float type objects, and uses float_as_number to initialize the object header.

How an instance of the float type is created. Notice how it passes a pointer to PyFloat_Type in the call to _PyObject_Init to set its type.

The figure is pretty detailed and annotated, so I won’t spend anymore time on it. But this is the code which is executed when you write “a = 3.14” in your Python code.

Side note: CPython maintains a cache of unused free float type objects and reuses them when it can. This possibly saves some time spent in memory allocation. There are similar caches for other objects, such as lists, tuples, dicts.

At this point, we understand that every type implements various operators as functions and uses them to populate the function pointer table in PyTypeObject, which is included in the object header. We have seen how this scheme works in the implementation of the float type.

Next, we move one layer up and see the abstract object interface, which actually performs dynamic dispatch.

The Abstract Object Interface in CPython

CPython defines an abstract object interface for unifying the access to the concrete type implementations. This keeps the VM code clean because it simply delegates the execution of an operator to this interface.

This abstract interface is defined in the file Include/abstract.h. and the following figure shows the numeric functions declared in it:

The abstract.h declares the abstract object interface, which includes functions for all the common object level operations in CPython. This figure shows a partial list of numeric operations as declared in abstract.h — The `abstract.h` header file declares the abstract object interface, which includes functions for all the common object level operations in CPython. This figure shows a partial list of numeric operations as declared in abstract.h

Now, abstract.h is a header file, so it only declares the prototypes of these functions. The implementations of these functions are in the file Objects/abstract.c. We will focus just on the implementation of the PyNumber_Add function in it, which is called by the VM to handle the + operator execution. The following figure shows its code, and the annotations explain what’s happening:

abstract.c contains implementations of the functions declared in abstrac.h. This figure shows implementation of the PyNumber_Add function

The + operation is supported by two classes of data types in Python: numeric types (int, float, complex etc.) and sequence types (list, tuple, etc.).

The PyNumber_Add function first tries to call the binary add implementation on the arguments. If those types do not support binary addition, then it tries to check if these types are sequence types, and if so, then it tries to call the concat function on them.

Let us focus on the numeric types here. For the numeric types, the PyNumber_Add function invokes the macro BINARY_OP1, which simply calls the binary_op1 function. The following figure shows binary_op1:

The rest of the implementation of PyNumber_Add in abstract.c

The function is doing quite a lot of things, but the annotations explain everything. The key takeaway is that abstract.c simply does function pointer lookup in the methods table present in the object’s header, and calls that function.

So far we have seen how a type implements various operators, and how the abstract object interface facilitates dynamic dispatch to those implementations. Now, for the final part, we will get back to the CPython VM and see where it calls the abstract object interface to execute an operator.

Connecting Operator Execution to the Abstract Object Interface in CPython VM

This is the final act where the CPython VM integrates operator execution with the abstract object interface. We discussed this partially in the previous article when understanding how the PyObject structure helps simulate polymorphism. This time, we will see it fully. But let’s start from the beginning.

The following figure shows a simple Python function and its bytecode instructions:

How the CPython stack based VM executes instructions

The bytecode instruction we are going to focus on is BINARY_OP. The following image shows how it is handled by the VM:

Implementation of the BINARY_OP instruction in the CPython VM

I won’t spend time explaining any of this, as we covered this in the previous article. However, we glossed over the actual execution of the binary op, let’s see that code because that’s where the VM delegates to abstract.c.

In the above code, we see this line of code:

res = binary_ops[oparg](lhs, rhs);

This code is doing a function pointer lookup in a table called binary_ops, using the opcode of the binary operator as the index, and calling that function. Let’s take a look at this table which is defined in the file ceval.c (which is where most of the VM execution code is implemented).

The binary_ops table in CPython VM which indexes the operator functions as defined in abstract.c using the binary operators as the index

Each function pointer in the binary_ops table points to a function which is implemented in Objects/abstract.c. In the previous section, we already saw the definition of PyNumber_Add in abstract.c, and understood how it does dynamic dispatch to the correct implementation of the operator based on the types of the operands.

So, this is how the VM delegates the execution of the binary operators to the abstract interface implementation, which ultimately performs the dynamic dispatch via function pointer lookup in the tables present in the object headers.

Summary

And, this is it! This is everything that goes on behind the scenes when you execute “a + b“ in your Python code. Let’s summarize quickly:

Each type implements functions for the operators it supports and populates the function pointer table in its header (i.e., the PyTypeObject field inside PyObject).
Based on the operator, the CPython VM calls a function in the abstract object interface.
The abstract object interface (when called from the VM) performs function pointer table lookup in the header of the operand objects, and calls the right function.

Wrapping Up

This was a short tour of ALL the CPython code which comes into action when you execute something as simple as “a + b” in your Python code. Although, this must be a lot to digest, it’s not too complex if you understand function pointers.

Equipped with this knowledge, you could implement your own operators, although for that you would also need to modify the tokenizer and parser which we have not talked about yet. Maybe we will cover those soon, if you have interest in learning more about CPython internals. Let me know via your comments, replies, likes and shares.