March 11, 2019 at 18:35Python memory management
- Transfer
Hello! So the long March weekend ended. We want to dedicate the first post-holiday publication to the beloved by many courses - "Python Developer" , which starts in less than 2 weeks. Go.
Content
Have you ever wondered how Python processes your data behind the scenes? How are your variables stored in memory? At what point are they removed?
In this article, we will delve deeper into the internal structure of Python to understand how memory management works.
After reading this article, you:
Knowing the internal structure of Python will provide a better understanding of the principles of its behavior. I hope you can take a look at Python from a new perspective. Behind the scenes, there are so many logical operations to make your program work properly.
Memory is an empty book.
Computer memory can be thought of as an empty book, waiting for many short stories to be written into it. There is nothing on its pages yet, but authors will soon appear who want to write their stories in it. To do this, they will need a place.
Since they cannot write one story on top of another, they need to be very careful about the pages on which they write. Before you start writing, they consult with the book manager. The manager decides where in the book authors can write down their story.
Since the book has been around for many years, many stories in it become outdated. When no one reads or addresses history, they remove it to make way for new stories.
At its core, computer memory is like an empty book. Continuous blocks of memory of a fixed length are usually called pages, so this analogy comes in handy.
Authors can be various applications or processes that need to store data in memory. A manager who decides where authors can write their stories plays the role of a memory manager - a sorter. And the one who erases old stories is a garbage collector.
Memory Management: From Hardware to Software
Memory management is the process in which software applications read and write data. The memory manager determines where to put the program data. Since the amount of memory is of course, like the number of pages in the book, accordingly, the manager needs to find free space to provide it for use by the application. This process is called “memory allocation”.
On the other hand, when data is no longer needed, it can be deleted. In this case, they talk about freeing up memory. But from what is it released and where does it come from?
Somewhere inside the computer there is a physical device that stores data when you run Python programs. Python code goes through many levels of abstraction before reaching this device.
One of the main levels lying above the equipment (RAM, hard disk, etc.) is the operating system. It manages read and write requests to memory.
Above the operating system, there is an application layer at which there is one of the Python implementations (wired to your OS or downloaded from python.org). Memory management for code in this programming language is regulated by special Python tools. The algorithms and structures that Python uses to manage memory are the focus of this article.
Basic Python implementation The basic Python
implementation, or “pure Python”, is CPython written in C.
I was very surprised when I first heard about it. How can one language be written in another language ?! Well, not literally, of course, but the idea is something like this.
The Python language is described in a special reference manual in English . However, this guide alone is not very useful. You still need a tool to interpret code written by the rules of the manual.
You will also need something to execute the code on your computer. The basic Python implementation provides both conditions. It converts Python code into instructions that are executed in a virtual machine.
Python is an interpreted programming language. Your Python code is compiled using instructions more readily understood by the computer — bytecode . These instructions are interpreted by the virtual machine when you run the code.
Have you ever seen files with the extension .pyc or the __pycache__ folder ? This is the same bytecode that is interpreted by the virtual machine.
It is important to understand that there are other implementations besides CPython, for example IronPython , which compiles and runs in the Microsoft Common Language Runtime (CLR). Jython compiles to Java bytecode to run in a Java virtual machine. And there is PyPyabout which you can write a separate article, so I will only mention it in passing.
In this article, we will focus on memory management using CPython tools.
Note: Python versions are updated and anything can happen in the future. At the time of writing, the latest version was Python 3.7 .
Ok, we have CPython written in C that interprets Python bytecode. How does this relate to memory management? To begin with, algorithms and structures for managing memory exist in CPython code, in C. To understand these principles in Python, you need a basic understanding of CPython.
CPython is written in C, which in turn does not support object-oriented programming. Because of this, CPython code has a rather interesting structure.
You must have heard that everything in Python is an object, even types like int and str, for example. This is true at the CPython implementation level. There is a structure called PyObject that every object in CPython uses.
Note: A structure in C is a user-defined data type that groups different types of data in itself. We can draw an analogy with object-oriented languages and say that a structure is a class with attributes, but without methods.
PyObject is the progenitor of all objects in Python, containing only two things:
A reference counter is required for garbage collection. We also have a pointer to a specific type of object. An object type is just another structure that describes objects in Python (such as dict or int).
Each object has an object-oriented memory allocator that knows how to allocate memory and store the object. Each object also has an object-oriented resource liberator that cleans up the memory if its contents are no longer needed.
There is one important factor in talking about memory allocation and its cleansing. Memory is a shared computer resource, and a rather unpleasant thing can happen if two processes try to write data to the same memory location at the same time.
Global Interpretation Lock (GIL)
GIL is a solution to the general problem of sharing memory between shared resources such as computer memory. When two threads try to change the same resource at the same time, they step on each other's heels. As a result, a complete mess is formed in the memory and no process will finish its work with the desired result.
Returning to the analogy with the book, suppose that of the two authors, each decides that it is he who should write his story on the current page at this particular moment. Each of them ignores the other's attempts to write a story and begins to stubbornly write on the page. As a result, we have two stories, one on top of the other, and an absolutely unreadable page.
One of the solutions to this problem is precisely GIL, which blocks the interpreter while the thread interacts with the allocated resource, thus allowing one and only one thread to write to the allocated memory area. When CPython allocates memory, it uses the GIL to make sure that it does it right.
This approach has both many advantages and many disadvantages, so the GIL causes strife in the Python community. To learn more about GIL, I suggest reading the following article .
Garbage collector
Let us return to our analogy with the book and imagine that some stories in it are hopelessly outdated. Nobody reads them and addresses them. In this case, a natural solution would be to get rid of them as unnecessary, thereby freeing up space for new stories.
Such old unused stories can be compared to objects in Python whose reference count has dropped to 0. Remember that every object in Python has a reference count and a pointer to a type.
The reference count may increase for several reasons. For example, it will increase if you assign one variable to another variable.
It will also increase if you pass the object as an argument.
In the last example, the reference count will increase if you include the object in the list.
Python lets you know the current value of the reference counter using the sys module. You can use
In any case, if the object in your code is still needed, its value of its reference counter will be more than 0. And when it drops to zero, a special memory cleaning function will be initiated, which will free it and make it available for other objects.
But what does it mean to “free memory” and how do other objects use it? Let's dive directly into memory management in CPython.
Memory Management in CPython
In this part, we will dive into the CPython memory architecture and the algorithms by which it operates.
As mentioned earlier, there is such a thing as levels of abstraction between physical equipment and CPython. An operating system (OS) abstracts physical memory and creates a level of virtual memory that applications, including Python, can access.
An OS-oriented virtual memory manager allocates a specific memory area for Python processes. In the image, the dark gray areas are the space that the Python process occupies.
Python uses a portion of memory for internal use and non-object memory. The other part is divided into the storage of objects (your int, dict , etc.) Now I speak in a very simple language, however, you can look directly "under the hood", that is, in the source code of CPythonand see how it all happens from a practical point of view.
In CPython, there is an object allocator responsible for allocating memory within an object memory area. It is in this distributor of objects that all magic is performed. It is called every time when each new object needs to occupy or free memory.
Usually, adding and removing data in Python, such as int or list, for example, does not use a lot of data at one time. That is why the architecture of the dispenser focuses on working with small amounts of data per unit time. Also, he does not allocate memory in advance, that is, until that moment until it becomes absolutely necessary.
The comments in the source code define the allocator as "a special-purpose fast memory allocator that works like the universal malloc function." Accordingly, in C, malloc is used to allocate memory.
Now let's take a look at the memory allocation strategy in CPython. First, let's talk about the three main parts and how they relate to each other.
Arenas are the largest areas of memory that occupy space up to the borders of pages in memory. The page border (page spread) is the extreme point of a continuous block of memory of a fixed length used by the OS. Python sets the system page border to 256 KB.
Inside the arenas are pools (pool), which are considered one virtual page of memory (4 Kb). They look like pages in our analogy. Pools are divided into even smaller pieces of memory - blocks.
All blocks in the pool are found in one “size class”. The size class determines the size of the block, having a certain amount of requested data. The gradation in the table below is taken directly from the comments in the source code:
For example, if 42 bytes are needed, then the data will be placed in a 48 byte block.
Pools
Pools are made up of blocks of the same size class. Each pool works on the principle of a doubly linked list with other pools of the same size class. Therefore, the algorithm can easily find the necessary place for the required block size, even among many pools.
List of used pools (
Pools are in three states: used, full, empty. The used pool contains blocks in which some information can be written. The blocks of the full pool are all distributed and already contain data. Empty pools do not contain data and can be broken down into what size classes are suitable if necessary.
The list of empty pools (
Let's say your code needs a memory area of 8 bytes. If there are no pools in the list of used pools with a class size of 8 bytes, then a new empty pool is initialized as storing blocks of 8 bytes. Then the empty pool is added to the list of used pools and can be used in the following queries.
A full pool frees up some blocks when this information in them is no longer needed. This pool will be added to the list used according to its size class. You can observe how the pools change their states and even size classes according to the algorithm.
Blocks
As can be seen from the figure, the pools contain pointers to free blocks of memory. There is a slight nuance in their work. According to the comments in the source code, the allocator “strives to never touch any memory area at any of the levels (arena, pool, block) until it is needed.”
This means that a block can have three states. They can be defined as follows:
The freeblock pointer is a single-linked list of free memory blocks. In other words, this is a list of free places where you can write information. If more memory is needed than there is in free blocks, then the allocator uses the untouched blocks in the pool.
As soon as the memory manager frees blocks, these blocks are added to the top of the list of free blocks. The actual list may not contain a continuous sequence of memory blocks, as in the first “successful” figure.
Arenas
Arenas contain pools. Arenas, unlike pools, do not have explicit state divisions.
They themselves are organized into a doubly linked list called a list of usable arenas (usable_arenas). This list is sorted by the number of free pools. The fewer free pools, the closer the arena to the top of the list.
This means that the most complete arena will be selected to record even more data. But why exactly? Why not write data to where the most free space is?
This brings us to the idea of completely freeing memory. The fact is that in some cases, when memory is freed, it still remains inaccessible to the operating system. The Python process keeps it distributed and uses it later for new data. Full memory deallocation returns memory to the operating system.
Arenas are not the only areas that can be completely vacated. Thus, we understand that those arenas that are on the “closer to empty” list should be freed. In this case, the memory area can really be completely freed, and accordingly, the total memory capacity of your Python program is reduced.
Conclusion
Memory management is one of the most important parts in working with a computer. One way or another, Python performs virtually all of its operations in stealth mode.
From this article you learned:
Python abstracts out the many small nuances of working with a computer. This makes it possible to work at a higher level and get rid of the headache on the topic of where and how bytes of your program are stored.
So we learned about memory management in Python. Traditionally, we are waiting for your comments, and we also invite you to an open day at the Python Developer course, which will be held on March 13
Content
- Memory is an empty book.
- Memory Management: From Hardware to Software
- Python base implementation
- Global Interpreter Lock (GIL) concept
- Garbage collector
- Memory Management in CPython:
- Pools
- Blocks
- Arenas
- Conclusion
Have you ever wondered how Python processes your data behind the scenes? How are your variables stored in memory? At what point are they removed?
In this article, we will delve deeper into the internal structure of Python to understand how memory management works.
After reading this article, you:
- Learn more about low-level operations, especially memory.
- Understand how Python abstracts low-level operations.
- Learn about memory management algorithms in Python.
Knowing the internal structure of Python will provide a better understanding of the principles of its behavior. I hope you can take a look at Python from a new perspective. Behind the scenes, there are so many logical operations to make your program work properly.
Memory is an empty book.
Computer memory can be thought of as an empty book, waiting for many short stories to be written into it. There is nothing on its pages yet, but authors will soon appear who want to write their stories in it. To do this, they will need a place.
Since they cannot write one story on top of another, they need to be very careful about the pages on which they write. Before you start writing, they consult with the book manager. The manager decides where in the book authors can write down their story.
Since the book has been around for many years, many stories in it become outdated. When no one reads or addresses history, they remove it to make way for new stories.
At its core, computer memory is like an empty book. Continuous blocks of memory of a fixed length are usually called pages, so this analogy comes in handy.
Authors can be various applications or processes that need to store data in memory. A manager who decides where authors can write their stories plays the role of a memory manager - a sorter. And the one who erases old stories is a garbage collector.
Memory Management: From Hardware to Software
Memory management is the process in which software applications read and write data. The memory manager determines where to put the program data. Since the amount of memory is of course, like the number of pages in the book, accordingly, the manager needs to find free space to provide it for use by the application. This process is called “memory allocation”.
On the other hand, when data is no longer needed, it can be deleted. In this case, they talk about freeing up memory. But from what is it released and where does it come from?
Somewhere inside the computer there is a physical device that stores data when you run Python programs. Python code goes through many levels of abstraction before reaching this device.
One of the main levels lying above the equipment (RAM, hard disk, etc.) is the operating system. It manages read and write requests to memory.
Above the operating system, there is an application layer at which there is one of the Python implementations (wired to your OS or downloaded from python.org). Memory management for code in this programming language is regulated by special Python tools. The algorithms and structures that Python uses to manage memory are the focus of this article.
Basic Python implementation The basic Python
implementation, or “pure Python”, is CPython written in C.
I was very surprised when I first heard about it. How can one language be written in another language ?! Well, not literally, of course, but the idea is something like this.
The Python language is described in a special reference manual in English . However, this guide alone is not very useful. You still need a tool to interpret code written by the rules of the manual.
You will also need something to execute the code on your computer. The basic Python implementation provides both conditions. It converts Python code into instructions that are executed in a virtual machine.
Note: Virtual machines are similar to physical computers, but they are embedded in the software. They process basic instructions similar to assembly code .
Python is an interpreted programming language. Your Python code is compiled using instructions more readily understood by the computer — bytecode . These instructions are interpreted by the virtual machine when you run the code.
Have you ever seen files with the extension .pyc or the __pycache__ folder ? This is the same bytecode that is interpreted by the virtual machine.
It is important to understand that there are other implementations besides CPython, for example IronPython , which compiles and runs in the Microsoft Common Language Runtime (CLR). Jython compiles to Java bytecode to run in a Java virtual machine. And there is PyPyabout which you can write a separate article, so I will only mention it in passing.
In this article, we will focus on memory management using CPython tools.
Note: Python versions are updated and anything can happen in the future. At the time of writing, the latest version was Python 3.7 .
Ok, we have CPython written in C that interprets Python bytecode. How does this relate to memory management? To begin with, algorithms and structures for managing memory exist in CPython code, in C. To understand these principles in Python, you need a basic understanding of CPython.
CPython is written in C, which in turn does not support object-oriented programming. Because of this, CPython code has a rather interesting structure.
You must have heard that everything in Python is an object, even types like int and str, for example. This is true at the CPython implementation level. There is a structure called PyObject that every object in CPython uses.
Note: A structure in C is a user-defined data type that groups different types of data in itself. We can draw an analogy with object-oriented languages and say that a structure is a class with attributes, but without methods.
PyObject is the progenitor of all objects in Python, containing only two things:
- ob_refcnt : reference counter;
- ob_type : pointer to another type.
A reference counter is required for garbage collection. We also have a pointer to a specific type of object. An object type is just another structure that describes objects in Python (such as dict or int).
Each object has an object-oriented memory allocator that knows how to allocate memory and store the object. Each object also has an object-oriented resource liberator that cleans up the memory if its contents are no longer needed.
There is one important factor in talking about memory allocation and its cleansing. Memory is a shared computer resource, and a rather unpleasant thing can happen if two processes try to write data to the same memory location at the same time.
Global Interpretation Lock (GIL)
GIL is a solution to the general problem of sharing memory between shared resources such as computer memory. When two threads try to change the same resource at the same time, they step on each other's heels. As a result, a complete mess is formed in the memory and no process will finish its work with the desired result.
Returning to the analogy with the book, suppose that of the two authors, each decides that it is he who should write his story on the current page at this particular moment. Each of them ignores the other's attempts to write a story and begins to stubbornly write on the page. As a result, we have two stories, one on top of the other, and an absolutely unreadable page.
One of the solutions to this problem is precisely GIL, which blocks the interpreter while the thread interacts with the allocated resource, thus allowing one and only one thread to write to the allocated memory area. When CPython allocates memory, it uses the GIL to make sure that it does it right.
This approach has both many advantages and many disadvantages, so the GIL causes strife in the Python community. To learn more about GIL, I suggest reading the following article .
Garbage collector
Let us return to our analogy with the book and imagine that some stories in it are hopelessly outdated. Nobody reads them and addresses them. In this case, a natural solution would be to get rid of them as unnecessary, thereby freeing up space for new stories.
Such old unused stories can be compared to objects in Python whose reference count has dropped to 0. Remember that every object in Python has a reference count and a pointer to a type.
The reference count may increase for several reasons. For example, it will increase if you assign one variable to another variable.
It will also increase if you pass the object as an argument.
In the last example, the reference count will increase if you include the object in the list.
Python lets you know the current value of the reference counter using the sys module. You can use
sys.getrefcount(numbers), but remember that a call getrefcount()will increase the reference counter by another one. In any case, if the object in your code is still needed, its value of its reference counter will be more than 0. And when it drops to zero, a special memory cleaning function will be initiated, which will free it and make it available for other objects.
But what does it mean to “free memory” and how do other objects use it? Let's dive directly into memory management in CPython.
Memory Management in CPython
In this part, we will dive into the CPython memory architecture and the algorithms by which it operates.
As mentioned earlier, there is such a thing as levels of abstraction between physical equipment and CPython. An operating system (OS) abstracts physical memory and creates a level of virtual memory that applications, including Python, can access.
An OS-oriented virtual memory manager allocates a specific memory area for Python processes. In the image, the dark gray areas are the space that the Python process occupies.
Python uses a portion of memory for internal use and non-object memory. The other part is divided into the storage of objects (your int, dict , etc.) Now I speak in a very simple language, however, you can look directly "under the hood", that is, in the source code of CPythonand see how it all happens from a practical point of view.
In CPython, there is an object allocator responsible for allocating memory within an object memory area. It is in this distributor of objects that all magic is performed. It is called every time when each new object needs to occupy or free memory.
Usually, adding and removing data in Python, such as int or list, for example, does not use a lot of data at one time. That is why the architecture of the dispenser focuses on working with small amounts of data per unit time. Also, he does not allocate memory in advance, that is, until that moment until it becomes absolutely necessary.
The comments in the source code define the allocator as "a special-purpose fast memory allocator that works like the universal malloc function." Accordingly, in C, malloc is used to allocate memory.
Now let's take a look at the memory allocation strategy in CPython. First, let's talk about the three main parts and how they relate to each other.
Arenas are the largest areas of memory that occupy space up to the borders of pages in memory. The page border (page spread) is the extreme point of a continuous block of memory of a fixed length used by the OS. Python sets the system page border to 256 KB.
Inside the arenas are pools (pool), which are considered one virtual page of memory (4 Kb). They look like pages in our analogy. Pools are divided into even smaller pieces of memory - blocks.
All blocks in the pool are found in one “size class”. The size class determines the size of the block, having a certain amount of requested data. The gradation in the table below is taken directly from the comments in the source code:
For example, if 42 bytes are needed, then the data will be placed in a 48 byte block.
Pools
Pools are made up of blocks of the same size class. Each pool works on the principle of a doubly linked list with other pools of the same size class. Therefore, the algorithm can easily find the necessary place for the required block size, even among many pools.
List of used pools (
usedpools list) keeps track of all pools that have some kind of free space available for data of each size class. When the requested block size is requested, the algorithm checks the list of used pools to find a suitable pool for it. Pools are in three states: used, full, empty. The used pool contains blocks in which some information can be written. The blocks of the full pool are all distributed and already contain data. Empty pools do not contain data and can be broken down into what size classes are suitable if necessary.
The list of empty pools (
freepools list) contains, respectively, all pools in an empty state. But at what point are they used?Let's say your code needs a memory area of 8 bytes. If there are no pools in the list of used pools with a class size of 8 bytes, then a new empty pool is initialized as storing blocks of 8 bytes. Then the empty pool is added to the list of used pools and can be used in the following queries.
A full pool frees up some blocks when this information in them is no longer needed. This pool will be added to the list used according to its size class. You can observe how the pools change their states and even size classes according to the algorithm.
Blocks
As can be seen from the figure, the pools contain pointers to free blocks of memory. There is a slight nuance in their work. According to the comments in the source code, the allocator “strives to never touch any memory area at any of the levels (arena, pool, block) until it is needed.”
This means that a block can have three states. They can be defined as follows:
- Untouched : areas of memory that have not been allocated;
- Free : memory areas that were allocated but later freed by CPython because they did not contain relevant information;
- Distributed : memory areas that currently contain current information.
The freeblock pointer is a single-linked list of free memory blocks. In other words, this is a list of free places where you can write information. If more memory is needed than there is in free blocks, then the allocator uses the untouched blocks in the pool.
As soon as the memory manager frees blocks, these blocks are added to the top of the list of free blocks. The actual list may not contain a continuous sequence of memory blocks, as in the first “successful” figure.
Arenas
Arenas contain pools. Arenas, unlike pools, do not have explicit state divisions.
They themselves are organized into a doubly linked list called a list of usable arenas (usable_arenas). This list is sorted by the number of free pools. The fewer free pools, the closer the arena to the top of the list.
This means that the most complete arena will be selected to record even more data. But why exactly? Why not write data to where the most free space is?
This brings us to the idea of completely freeing memory. The fact is that in some cases, when memory is freed, it still remains inaccessible to the operating system. The Python process keeps it distributed and uses it later for new data. Full memory deallocation returns memory to the operating system.
Arenas are not the only areas that can be completely vacated. Thus, we understand that those arenas that are on the “closer to empty” list should be freed. In this case, the memory area can really be completely freed, and accordingly, the total memory capacity of your Python program is reduced.
Conclusion
Memory management is one of the most important parts in working with a computer. One way or another, Python performs virtually all of its operations in stealth mode.
From this article you learned:
- What is memory management and why is it important;
- What is CPython, a basic Python implementation;
- How data structures and algorithms work in CPython's memory management and store your data.
Python abstracts out the many small nuances of working with a computer. This makes it possible to work at a higher level and get rid of the headache on the topic of where and how bytes of your program are stored.
So we learned about memory management in Python. Traditionally, we are waiting for your comments, and we also invite you to an open day at the Python Developer course, which will be held on March 13