Memory Management in Python

Memory is an Empty Book

13 min readOct 1, 2019

You can begin by thinking of a computer’s memory as an empty book intended for short stories. There’s nothing written on the pages yet. Eventually, different authors will come along. Each author wants some space to write their story in.

Since they aren’t allowed to write over each other, they must be careful about which pages they write in. Before they begin writing, they consult the manager of the book. The manager then decides where in the book they’re allowed to write.

Since this book is around for a long time, many of the stories in it are no longer relevant. When no one reads or references the stories, they are removed to make room for new stories.

Here in this analogy:

Empty book. 🡺 Computer memory In fact, it’s common to call fixed-length contiguous blocks of memory pages, so this analogy holds pretty well.

The author’s 🡺 applications or processes that need to store data in memory. The manager 🡺 plays the role of a memory manager of sorts.

The person who removed the old stories 🡺garbage collector.

Memory Management: From Hardware to Software

Memory management is the process by which applications read and write data. A memory manager determines where to put an application’s data. Since there’s a finite chunk of memory, like the pages in our book analogy, the manager has to find some free space and provide it to the application. This process of providing memory is generally called memory allocation.

On the flip side, when data is no longer needed, it can be deleted, or freed. But freed to where? Where did this “memory” come from?

Somewhere in your computer, there’s a physical device storing data when you’re running your Python programs. There are many layers of abstraction that the Python code goes through before the objects actually get to the hardware though.

One of the main layers above the hardware (such as RAM or a hard drive) is the operating system (OS). It carries out (or denies) requests to read and write memory.

Above the OS, there are applications, one of which is the default Python implementation (included in your OS or downloaded from python.org.) Memory management for your Python code is handled by the Python application. The algorithms and structures that the Python application uses for memory management is the focus of this article.

The Default Python Implementation

The default Python implementation, CPython, is actually written in the C programming language.

You also need something to actually execute interpreted code on a computer. The default Python implementation fulfills both of those requirements. It converts your Python code into instructions that it then runs on a virtual machine.

Python is an interpreted programming language. Your Python code actually gets compiled down to more computer-readable instructions called bytecode. These instructions get interpreted by a virtual machine when you run your code.

Have you ever seen a .pyc file or a __pycache__ folder? That’s the bytecode that gets interpreted by the virtual machine.

It’s important to note that there are implementations other than CPython. IronPython compiles down to run on Microsoft’s Common Language Runtime. Jython compiles down to Java bytecode to run on the Java Virtual Machine. Then there’s PyPy, but that deserves its own entire article, so I’ll just mention it in passing.

I’ll focus on the memory management done by the default implementation of Python, CPython.

NOTE: —

CPython is written in C, which does not natively support object-oriented programming. Because of that, there are quite a bit of interesting designs in the CPython code.

You may have heard that everything in Python is an object, even types such as int and str. Well, it’s true on an implementation level in CPython. There is a struct called a PyObject, which every other object in CPython uses.

The PyObject, the grand-daddy of all objects in Python, contains only two things:

ob_refcnt: reference count
ob_type: pointer to another type

The reference count is used for garbage collection. Then you have a pointer to the actual object type. That object type is just another struct that describes a Python object (such as a dict or int).

Each object has its own object-specific memory allocator that knows how to get the memory to store that object. Each object also has an object-specific memory deallocator that “frees” the memory once it’s no longer needed.

However, there’s an important factor in all this talk about allocating and freeing memory. Memory is a shared resource on the computer, and bad things can happen if two different processes try to write to the same location at the same time.

The Global Interpreter Lock (GIL)

The GIL is a solution to the common problem of dealing with shared resources, like memory in a computer. When two threads try to modify the same resource at the same time, they can step on each other’s toes. The end result can be a garbled mess where neither of the threads ends up with what they wanted.

One solution to this problem is a single, global lock on the interpreter when a thread is interacting with the shared resource (the page in the book). In other words, only one author can write at a time.

Python’s GIL accomplishes this by locking the entire interpreter, meaning that it’s not possible for another thread to step on the current one. When CPython handles memory, it uses the GIL to ensure that it does so safely.

Garbage Collection

The Algorithm used for Garbage Collection (GC) in python is called Reference Counting. Whereas Java uses Mark and Sweep Algorithm. Where the objects are marked ASAP they are dead periodically not immediately.

Both the algorithm has their own advantages. For example, when the dead objects are there in the main memory there is always optimal memory utilization this is advantageous when the memory is limited however this slows down the speed of execution due to frequent invoke of Garbage Collection.

Let’s revisit the book analogy and assume that some of the stories in the book are getting very old. No one is reading or referencing those stories anymore. If no one is reading something or referencing it in their own work, you could get rid of it to make room for new writing.

Remember that every object in Python has a reference count and a pointer to a type. The reference count gets increased for a few different reasons. For example, the reference count will increase if you assign it to another variable:

The methods are executed in stack memory. By default, program begins its execution under main method stack.
The objects are created in Heap memory whereas references are created in stack memory.

How is reference count calculated?

Here, input to the getrefcount() can be a variable name, value, function, class and anything else comes under Python object.

This means the integer value ‘1556778’ is used 3 times.

You might be curious… how does it comes 3 times, even if you have used the value only once?

How is the reference count calculated?

Reference Count from Bytecode:

When you run any Python program, it gets interpreted into the bytecode. The reference count of the object is calculated based on the number of times object is used in the bytecode (not from your high-level program code)

2. Reference Count from other parts of the Code:

If the same object is used in the other part of the code, it will be counted in the reference count of the given object. Even, there are multiple cumbersome operations goes running in background Python. It may possible that this object is used in the background of your running program. It is also counted as a reference to the object. The output (reference count) may vary from system to system.

Reference Count for Variable and Function:

When you pass the variable as a parameter to the function, reference count for the variable object is incremented. When the control goes out of the function, the reference count is decremented.

Note: Reference count is shown as 19 instead of 18 because of variable ‘a’ is used two times in function- as a parameter to the function func(); as a parameter to the function sys.getrefcount().

Reference Count for Python List

Along with the list object, every element in the list has a separate reference count. When you delete a list or if the lifetime of the list expires, the reference count of each element in the list goes down by one.

When does the reference count increase?

while assigning operator
while passing the value as an argument to the function
appending object to the list

Use of the reference count for Memory Management in Python:

Python uses dynamic memory allocation.

There are two questions arises…

While creating the object, what if the object already exists in memory?
While deleting the object, how the system will know if the object is no more used?

And, here comes the use of reference count.

Python count the reference for each object. When you use that object again, the reference count is incremented. When the reference object comes out of scope, the reference count is decremented. When the reference count reaches zero, means the Python object is not in use. The memory which is assigned to the object gets deleted. And we know that integer is immutable datatype in Python. So we cannot change the value of the integer. The new value is stored in different memory with the new reference count.

To find the pattern for a number of times Python object is used, we can plot the graph for a range of input objects.

Write a program to plot a graph based on reference count for integer values (say 1 to 500) used in the Python.

From the graphs, it is clear that there are more numbers of reference count for smaller numbers. A couple of initial smaller values have a reference count more than 3000. Means, smaller numbers are used widely running Python in the background.

Similarly, let’s plot the reference counts graph for 26 English letters.

We are more obsessed with the letter ‘x’ and it is used for many variable declarations. If you look at the graph it holds true. The ‘x’ as the object is used more than 1100 in Python.

Take some popular keyword in Python, count and plot the reference count.

How can we exclude “Python” itself?

Keys Points to remember about Python Reference Count:

You may get a difference reference count for the same object on the different Python system. It solely depends on the number of times object is used on your system.
If you declare the object as global (declared outside of any block, class or functions), can never have reference count zero.
Value of the reference count is always one higher than the one you expect as it also counts reference for an object passing to function sys.getrefcount() itself.

CPython’s Memory Management

There are layers of abstraction from the physical hardware to CPython. The operating system (OS) abstracts the physical memory and creates a virtual memory layer that applications (including Python) can access.

An OS-specific virtual memory manager carves out a chunk of memory for the Python process. The darker gray boxes in the image below are now owned by the Python process.

Python core uses a portion of the memory for internal use and non-object memory. The other portion is dedicated to object storage (your int, dict, and the like). Note that this was somewhat simplified.

CPython has an object allocator that is responsible for allocating memory within the object memory area. This object allocator is where most of the magic happens. It gets called every time a new object needs space allocated or deleted.

Now we’ll look at CPython’s memory allocation strategy. First, we’ll talk about the 3 main pieces and how they relate to each other.

Arenas are the largest chunks of memory and are aligned on a page boundary in memory. A page boundary is the edge of a fixed-length contiguous chunk of memory that the OS uses. Python assumes the system’s page size is 256 kilobytes.

Within the arenas are pools, which are one virtual memory page (4 kilobytes). These are like the pages in our book analogy. These pools are fragmented into smaller blocks of memory.

All the blocks in a given pool are of the same “size class.” A size class defines a specific block size, given some amount of requested data. The chart below is taken directly from the source code comments:

For example, if 42 bytes are requested, the data would be placed into a size 48-byte block.

NOTE: — here each pool contains the blocks of the same size.

Pools

Pools are composed of blocks from a single size class. Each pool maintains a double-linked list to other pools of the same size class. In that way, the algorithm can easily find available space for a given block size, even across different pools.

A usedpools list tracks all the pools that have some space available for data for each size class. When a given block size is requested, the algorithm checks this usedpools list for the list of pools for that block size.

Pools themselves must be in one of 3 states: used, full, or empty. A used pool has available blocks for data to be stored. A full pool’s blocks are all allocated and contain data. An empty pool has no data stored and can be assigned any size class for blocks when needed.

A freepools list keeps track of all the pools in the empty state. But when do empty pools get used?

Assume your code needs an 8-byte chunk of memory. If there are no pools in usedpools of the 8-byte size class, a fresh empty pool is initialized to store 8-byte blocks. This new pool then gets added to the usedpools list so it can be used for future requests.

Say a fullpools frees some of its blocks because the memory is no longer needed. That pool would get added back to the usedpools list for its size class.

You can see now how pools can move between these states (and even memory size classes) freely with this algorithm.

Blocks

As seen in the diagram above, pools contain a pointer to their “free” blocks of memory. There’s a slight nuance to the way this works. This allocator “strives at all levels (arena, pool, and block) never to touch a piece of memory until it’s actually needed,” according to the comments in the source code.

That means that a pool can have blocks in 3 states. These states can be defined as follows:

untouched: a portion of memory that has not been allocated
free: a portion of memory that was allocated but later made “free” by CPython and that no longer contains relevant data
allocated: a portion of memory that actually contains relevant data

The freeblock pointer points to a singly linked list of free blocks of memory. In other words, a list of available places to put data. If more than the available free blocks are needed, the allocator will get some untouched blocks in the pool.

As the memory manager makes blocks “free,” those now freeblocks get added to the front of the freeblock list. The actual list may not be contiguous blocks of memory, like the first nice diagram. It may look something like the diagram below:

Arenas

Arenas contain pools. Those pools can be used, full, or empty. Arenas themselves don’t have as explicit states as pools do though.

Arenas are instead organized into a doubly linked list called usable_arenas. The list is sorted by the number of free pools available. The fewer free pools, the closer the arena is to the front of the list.

This means that the arena that is the most full of data will be selected to place new data into. But why not the opposite? Why not place data where there’s the most available space?

This brings us to the idea of truly freeing memory. You’ll notice that I’ve been saying “free” in quotes quite a bit. The reason is that when a block is deemed “free”, that memory is not actually freed back to the operating system. The Python process keeps it allocated and will use it later for new data. Truly freeing memory returns it to the operating system to use.

Arenas are the only things that can truly be freed. So, it stands to reason that those arenas that are closer to being empty should be allowed to become empty. That way, that chunk of memory can be truly freed, reducing the overall memory footprint of your Python program.

Conclusion

Memory management is an integral part of working with computers. Python handles nearly all of it behind the scenes, for better or for worse.

In this article, you learned:

What memory management is and why it’s important
How the default Python implementation, CPython, is written in the C programming language
How the data structures and algorithms work together in CPython’s memory management to handle your data