How Lists in Python Are Optimised Internally for Better Performance
A precise guide to internal implementation and its optimisation in python
This Article is co-authored, Muhammad Abutahiris, You can find him on linkedin and instagram.
Lists! One of the most used datatypes in the Python programming language and one of the most favorite datatypes of every python lover. Python lists are extremely simple to work with and are very flexible in nature.
Python lists unlike arrays aren’t very strict, Lists are heterogeneous which means you can store elements of different datatypes in them. The internal implementation of lists is designed in such a way that it has become a programmer-friendly datatype. The reason being the mutability nature of the list because of which allows you to perform any operation with them, like adding a single element, adding multiple elements, deletion operations, and many more!
How do lists work internally?
Lists make use of variable length arrays behind the scenes, variable-length arrays are a variant of arrays whose size is not specified initially, or whose length or size is set during runtime, you can also call them auto arrays.
This implementation is done in CPython. there are other variants like JPython and IronPython as well. Performance-wise they can slightly defer with one another, but the one which I am going to talk about is CPython.
Let’s look at the basic structure of the list in CPython.
Here PyObject **ob_item; is the pointer to elements of the list. This explains to us that lists internally stores pointers to elements rather than elements themselves! which in turn explains to us the heterogeneous nature of the list. That is storing elements of different datatypes, like a list within a list, a string, a number, and whatever comes to your mind.
What if I ask you a question like ‘What’s the size of an empty list?’. The most common answer would be Zero! but remember, size and length are two different things. If we check the size of an empty list which I am going to show you in a second, the result is 40. This can have multiple reasons, like the initial sizes of variables, the memory for garbage collection options, the memory for inbuilt functions, although they are given space in the stack memory when they are called, yet still have some variables, etc.
This is the same case when we create the empty list using built-in list() the __sizeof__() is a function that returns the size of the object in bytes.
Now if we create a list directly by placing the elements within [] we get a size that is 8 bytes multiplied by the total number of elements, keep in mind that PyObject **ob_item; takes 8 bytes per storage. This is independent of the datatype of the element which you are storing.
In the above piece of code I have created a list with two elements, one is numeric and another is a string, but we are getting 56 that is 40+8+8. Abstractly we can visualize the above code how it is demonstrated in the memory like this image below.
However, something different happens when we try to use the append() which is used to add a single element to the list. Check this out!
Wow! 72? So we just added one element, it had to be 48 40+8! but why is it 72? that’s like 40+32. Let’s understand this quickly.
Performance optimization in a list
CPython implements the concept of Over-allocation, this simply means that if you use append() or extend() or insert() to add elements to the list, it gives you 4 extra allocation spaces initially including the space for the element specified. We call this resizing of lists and it happens during runtime. 4 spaces are allocated initially including the space for element and it continues in the pattern 8,16,25,35… and so on. This resizing is done to boost the performance. I will show you how performance is increased by doing this in a moment.
Refer to the previous code in which we added an element to the list using append() This is how we can visualize the over-allocation concept of CPython. I have shown the light green boxes which aren’t accessible, although they are still present, however we can see the memory with the help of __sizeof__()This is the reason we got 72 that is 40+8+8+8+8!
Now when we append more elements, first the allocated spaces are filled, and then we resize according to a specific pattern. let’s check out the same with extend().
As you can see, I added 3 more elements but the size remained 72. This is because the already allocated spaces got filled.
This over-allocation is done for a reason. When new elements are added to the list using built-in functions, a function list_resize() is called implicitly, which is implemented in CPython, This function has to be called every time a new element is added, to avoid this to be called too many times, a resizing pattern is specified which calculates in a manner as 1.125 * new_size +3 Here the number 3 is increased to 6 when elements are more than 9.
Now if you try to append a new element to the list, the list again gets over-allocated and you get a new size, check out this below code.
As you can see, the previous spaces got filled and as you created a new element, the size increased from 72 to 104. Hence, by avoiding the repeated calling of the list_resize() we are lowering the cost in terms of stack memory and also time, hence it’s important.
Conclusion
In this article, I have discussed an in-depth explanation of the internal implementation and optimizations of lists in Python. It’s very smart that programmers used amazing ideas to enhance the performance in places where we need them because python is very slow when compared to other programming languages, hence taking these types of steps can reduce an enormous amount of pain to the programmers.
With that said, Thank you all for reading this article, Happy Learning!
