macro shot photo of a computer RAM

Memory Management and Garbage Collection in Python

Python is a high-level interpreted, dynamically typed language. As an interpreted language, the actual Python implementation is a low level language, such as C. Your python code, which is so human friendly, is converted to machine friendly bytecode. This compiled bytecode runs inside a virtual machine that effectively translates this code to something your machine can understand and execute.

Memory management refers to allocation and deallocation of objects. While the allocation of objects depends on the programmer, such as defined functions, variables, objects, etc., most programming languages perform deallocation of such resources automatically. Python comes baked in with Garbage Collection routines that take care of cleaning up unused references and objects, and honestly also plays a major role in keeping Python developer friendly and highly adaptable. However, it still exposes functionality to let developers manually clean up memory without waiting for the automatic routines to kick in. This helps facilitate writing memory efficient programs.

In this post, we’ll take a look at how Python manages objects internally, and how the automatic garbage collection routine frees them up.


Python is a ‘dynamically-typed’ language

If you have prior programming experience in C, C++, you would be aware that specifying the type is a must when defining variables, since type information is crucial to determine the amount of memory that needs to be reserved for that variable. This also limits the amount of data you can store inside that variable. For example, lists data type require length of list during initialization and storing any extra element throws a memory overflow error.

Python, on the other hand, is dynamically-typed. All variables are references to objects stored in memory. Since they are references, they can point to basically anything. This is the reason why:

  • You never specify ‘type’ to variables in Python.
  • A variable which is an integer initially can be set to a string, or basically anything, anytime.
  • A variable is just a human-friendly handle to an object in memory, nothing else.

Behind the scenes in object creation

Let’s start with something pretty basic. We’ll define some integers and strings as follow:

int_1 = 1 int_2 = 2 int_3 = 1 str_1 = "hello" str_2 = "world" str_3 = "hello"
Code language: JavaScript (javascript)

As discussed before, the names int_1, int_2, int_3, etc. are just references. To get the actual memory location these references are pointing to, just pass the variable name as argument to id() function.

>> print("int_1 {}, int_2 {}, int_3 {}, str_1 {}, str_2 {}, str_3 {}".format(id(int_1), id(int_2), id(int_3), id(str_1), id(str_2), id(str_3))) int_1 9788992, int_2 9789024, int_3 9788992, str_1 139989231229168, str_2 139989231229296, str_3 139989231229168
Code language: CSS (css)

The returned values, 9788992 , 9789024 , etc. are the actual memory locations.

Notice how the memory locations of int_1, int_3and str_1, str_3 are exactly the same. Python tries to optimize memory usage by avoiding creating objects if such an object with same value already exists. Since the object with value 1 and hello already exist in memory, the reference for the variable pairs mentioned earlier are exactly the same.

This extends to objects stored in lists, tuples and dictionaries too. As an example, for a list containing integers 1 and 2, they’ll point individually to the exact same reference as int_1 and int_2.

>>> ls = [1,2] >>> print(id(ls[0]) == id(int_1)) True >>> print(id(ls[1]) == id(int_2)) True
Code language: PHP (php)

This applies to all immutable objects in Python but doesn’t carry forward to mutable or ‘container’ objects. For example, two lists containing the same integers during initialization do not point to the same memory reference. Optimization is done only for primitive immutable objects.

For every object, Python maintains three things internally:

  • Type: the type of object, such as int, str, bool, etc.
  • Value: the value of the object, such as 1, hello, true, etc.
  • Ref-Count: the reference count of the object i.e. how many references are pointing to that object. For a fresh new object, this is set to 1.

We can query all of the above information for any object in Python. Let’s try this on str_1 object.

>>> type(str_1) <class 'str'> >>> sys.getrefcount(str_1) 3
Code language: HTML, XML (xml)

The refcount property maintains count of references pointing to that object. For example, if we create a new reference to hello the reference count will increase by 1.

>>> str_3 = "hello" # create another reference >>> sys.getrefcount(str_1) 4
Code language: PHP (php)

Similarly deleting the new reference will decrement the count.

>>> del str_3 >>> sys.getrefcount(str_1) 3
Code language: CSS (css)

You can also change the reference of str_3 or set it to None to cause the reference count of object holding str_1 to decrease.

Memory Management in CPython

As mentioned earlier, Python is an interpreted programming language. The entire source code is converted to bytecode which is then interpreted by a virtual machine, and finally executed. There are several implementations, such as CPython that uses C backend for memory allocation and management, then there’s Jython that uses Java, and so on. In this article we’ll focus on CPython.

Everything in Python is an object, such as integers, strings, etc. Objects can hold other objects, such as lists, tuples, dicts, etc. In CPython, this is handled by a simple C struct called PyObject. PyObject holds two things:

  • ob_refcnt: object’s reference count (used for garbage collection)
  • ob_type: pointer to actual type, which is basically another struct defining a Python object

Every Python object has it’s own object specific functions, such as allocator, deallocator, etc.

Since objects can house other objects, this dynamic nature requires a lot of memory allocations and deallocations. Python uses PyMalloc to speed up this operation and reduce any fragmentation. The following chart shows this system as composed of hierarchical layers.

Allocation Strategy

Python sub-allocates big blocks of memory. Allocation requests greater than this threshold are routed to system’s allocator, such as the standard C Malloc. For all other allocation requests, the strategy is abstracted into three main levels, blocks, pools and arenas.

Blocks

Blocks are chunks of memory and house only one Python object of fixed predetermined size. They can be requested in multiples of 8 i.e. 8 bytes, 16 bytes up to 512 bytes, totaling 64 request classes. The 8 byte alignment ensures alignment is valid for returned memory address of a specific block.

Request in BytesSize of Allocated BlockSize Class Index
1-880
9-16161
17-24242
25-32323
33-40404
41-48485
49-56566
57-64647
65-72728
497-50450462
505-51251263
https://github.com/python/cpython/blob/760349198dbd8771629753e096a885c1aa28a1ca/Objects/obmalloc.c#L829

Blocks can hold a single Python object of a certain size which can be equal to or less than the requested block size. Any empty space in the block cannot be occupied by another object.

A block can be in one of the following three states:

  • Untouched: Block that is not allocated.
  • Free: Block that was previously allocated but now released by CPython i.e. it is now available for reallocation.
  • Allocated: Block that contains relevant data.

Blocks are the smallest memory structures managed inside pools. Every pool contains a freeblock pointer that points to a linked list of all available free blocks in a pool. The list may not be contiguous blocks of memory i.e. free blocks can be scattered randomly inside a pool. If an allocation request needs more free pools than currently available, the allocator will add new untouched blocks to the pool and append their references to front of the freeblocks list (pointed by freeblock pointer).

Untouched, Allocated, and Free Blocks in a Pool
Pools

Pools are comprised of blocks. Every block in a specific pool belong to single size class i.e. all have the same block size. Pools of same size class are maintained in a double linked list structure to make traversing between them easier during allocation.

Pools can be in three states:

  • Used: Pool that contain allocated and unallocated/free blocks
  • Full: Pool that contain no free blocks i.e. unavailable for allocation.
  • Free: Pool that is completely empty. Free blocks of a specific size class can be allocated to it.

A usedpools list is a double linked list keeps track of used pools of each size class. Similarly, freepools is a single linked list keeps track of empty pools.

Lets assume that your code requests memory allocation for 16-byte chunks. The size class is 16 bytes. If there are no pools in usedpools of this size class, a new empty pool is taken from freepools , and is initialized with blocks of requested size class.

Usedpools and Freepools Visualization
Arenas

Pools are grouped together in arenas. Unlike blocks and pools, arenas do not have a state. A double linked list usable_arenas organizes a list of all available arenas sorted by number of free pools available in each arena. The lower the number of free pools available, the closer the arena is to the front of the list.

This highlights a very interesting concept. When an allocation request is made, the arena with the lowest number of free pools available is selected. This ensures that arenas that are far away from the list (i.e. have the highest number of free pools available) can be truly freed when the data held by them is no longer required. This allows entire arenas to be easily freed, thus reducing the overall memory footprint of your Python program.

Garbage Collection in CPython

Garbage Collection refers to recycling of memory by removing objects that are no longer in use. This allows memory to be reallocated to store objects that are required.

Python has an automatic garbage collection mechanism. This means that programmers don’t have to worry about deleting objects, removing dangling pointers, memory leaks, etc. and can instead focus on functionality and features of the program itself. While it is convenient for programmer, automatic GC requires extra memory usage by the runtime to keep track of objects, references, etc. so that memory can be released when such objects are not needed.

There are two ways Python handles garbage collection; Reference Counting and Generational Garbage Collection.

Reference Counting

The main garbage collection mechanism in CPython is Reference Counting. As discussed in the first section, when you create an object, Python internally maintains the object’s type, value and reference count. When the object is referenced by another variable, the reference count is incremented. Similarly when a variable is deleted, the reference count of the object is decremented. The object is freed by the garbage collection when the reference count of that object reaches zero.

While reference counting is extremely easy to implement, it doesn’t work on cyclic references. A cyclic reference occurs when an object refers to itself. See the Python code snippet below:

>>> ls: list = [] >>> ls.append(ls) >>> ls [[...]]
Code language: PHP (php)

In the above example, we created a new list ls. We then appended this created list, to the list itself. So even if we call the del instruction on this list, the actual object will never be deleted since the list is referring to itself. For such cases the second collection mechanism – Generational GC is used.

Generational Garbage Collection

Generational GC is a trace-based garbage collection mechanism, and can delete objects stuck in a cyclic reference nightmare. There are two main concepts in Generational Garbage Collection:

  • Generation
  • Threshold

Python maintains three lists of objects or three generations to keep track of objects in memory.

Generation 0

It contains all objects that are ‘newly’ created and are not examined by the Garbage Collection routine. The ‘thresholds’ define the size of each generation. Whenever a threshold is surpassed on a generation, a collection routine is called, that promotes objects to upper generations.

For example, lets assume the threshold for Generation 0 is 5 objects. Lets create 5 new objects. So, the Generation 0 will look like below:

12345
Generation 0
Generation 1

We now create another object, object 6. As it is a new object, it will be a part of Generation 0. Since the threshold is now surpassed, a collection is triggered. The collection process causes garbage objects, lets say objects 1,2 and 3 to be deallocated. Since objects 4 and 5 survived the collection process, they’ll be promoted to Generation 1. We’ll assume that threshold for Generation 1 is 10 objects.

24
Generation 1

The collection process on Generation 1 will not be called until is threshold value is surpassed. Let’s fast-forward to several object creations and collection processes. The generations now look like below:

25810111213151617
Generation 1
1819202223
Generation 0
Generation 2

We now create another object, object 24. The threshold on Generation 0 is surpassed, so a collection process is called. Lets say objects 18, 19 and 20 were deleted. This will cause objects 22 and 23 to be promoted to Generation 1. Since the threshold of Generation 1 is also now surpassed, a collection process on Generation 1 will be called. This will delete all garbage objects in Generation 1. Objects that survive the collection process will be promoted to Generation 2.

258101617
Generation 2
18192022
Generation 1
24
Generation 0

Thus, the Generation Garbage Collection ensures that newly created objects have more probability to be collected. As object promote to upper generations, they become less likely to be part of the collection process.

Conclusion

In this article we delved deeper into how Python manages, stores, collects and discards objects, especially in the CPython implementation. We started by discussing what happens behind the scenes when objects are created and what type of information Python stores and manages about objects. We talked about references and counting and also looked at some Python snippets to see that information. We then delved into how CPython handles the underlying system memory to store Python objects. We discussed Pools, Arenas and Blocks, the three fundamental structures that represent memory for the Python runtime. Finally, we talked about garbage collection, and how Python uses Reference Counting and Generational Counting to free up memory from deleted and garbage objects.

Subscribe to our mailing list to receive new articles directly in your inbox! If you’ve a suggestion, query or a question, shoot it in the comments section below!

Total
0
Shares
Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Prev
Let’s Understand Smart Contracts in Blockchain
Understanding smart contracts

Let’s Understand Smart Contracts in Blockchain

A smart contract is essentially a set of legal rules

Next
3 Best Libraries for Fuzzy Matching In Python
Fuzzy matching in python

3 Best Libraries for Fuzzy Matching In Python

Learn about 3 of the most used fuzzy matching libraries in Python

You May Also Like