In this blog we understand how Garbage collection is done in Python

Garbage Collection

Runtime, in all programming languages, fascinates me the most in modern software development. It’s the engine behind code efficiency and performance. It’s not just a shelter for code — it actively supervises its behavior.

Picture your code as a creature living within the runtime’s boundaries. Memory management acts as its guardian, crucial for a well-functioning application. For me, exploring a new language and its frameworks begins by understanding its runtime and memory management. This choice might deviate a bit from the usual hello world! convention (which, I argue, should be Hello word!’— but I wasn’t there, and nobody’s asking me anyway) Nevertheless, my modest experience has taught me that understanding the syntax and semantics of a language, at least in the current standards, is something to grapple with in the initial 10 days of development. However, non-optimized, leaky, and poorly designed software tends to persist even after the developer’s retirement.

Well, I recently left a company focused on Python-heavy projects and am about to join another with a strong emphasis on Node services. As is my practice, I prioritize reviewing computer science concepts relevant to the new runtime apparatus. Having a background in Android Development, transitioning previously from Dalvik to ART, I adopted a similar approach then and when entering the Python world.

I must clarify that I’m no expert, merely sharing my current understanding coming from my notes. Some references are provided at the end for further exploration. Enjoy the journey.

1. Introduction

2. How It Started

3. Memory and Sets

4. Making Memory Work on Its Own

5. Exploring Scientific Approaches to Garbage Collection

6. Using Math to Manage Memory

7. How Java Does It

8. Garbage Collection in Android’s Dalvik and ART

9. Python’s Way of Handling Garbage Collection

10. Managing Memory in Node.js

11. References

1. Introduction

In the world of computer languages, managing memory is crucial for making programs work smoothly. Garbage collection, a key part of this process, has its roots in math. This article explores how garbage collection began in math’s set theory and evolved into today’s complex memory systems. As I mentioned, the earliest notions of garbage collection can be traced back to set theory, where the concepts of reachable **and **unreachable elements draw parallels to memory allocation and deallocation in programming languages. The principle of identifying elements within a set that are no longer reachable, akin to memory that’s no longer needed, laid the groundwork for garbage collection algorithms. Early pioneers in computer science, like John McCarthy and his development of Lisp in the late 1950s, contributed to the conceptualization of automated memory management. McCarthy’s creation introduced the idea of automatic garbage collection within programming languages, aiming to alleviate developers from manual memory handling. Advancements in mathematical models further propelled the evolution of garbage collection techniques. The development of algorithms such as mark-and-sweep, reference counting, and generational garbage collection, rooted in mathematical principles, revolutionized memory management in programming languages.

2. How It Started

In the nascent stages of computer science, the concept of managing memory emerged alongside the evolution of programming languages. The genesis of automated memory management, known as garbage collection, finds its roots in the pioneering work of early computer scientists. As programming languages began to take shape, the necessity to efficiently allocate and deallocate memory became apparent. This led to the inception of concepts that aimed to automate this process, paving the way for the birth of garbage collection.

// Early memory management concept
function allocate_memory(size):
    // Allocate memory block of specified size
    return memory_block

function deallocate_memory(memory_block):
    // Deallocate memory block
    // Mark the memory as available for reuse > This pseudocode snippet showcases a simplistic approach to memory management, where memory blocks are manually allocated and deallocated. In early computer programming, developers had to explicitly request memory and release it when no longer needed. This manual process was prone to errors and memory leaks.

3. Memory and Sets

Memory management in programming shares a fundamental connection with mathematical set theory. The parallel between managing memory and the principles of sets lies in distinguishing between ‘reachable’ and ‘unreachable’ elements. Similar to how a set comprises elements that are either connected or disconnected, memory in programming languages holds data that is either accessible or no longer in use. This analogy between memory and sets forms the cornerstone of garbage collection algorithms, where identifying and handling ‘unreachable’ memory becomes crucial for efficient program execution. By applying set theory principles, programmers devise methods to identify and clear unused memory, optimizing the performance of programs.

// Simulating memory sets using a list
list_of_memory_blocks = [block1, block2, block3, block4, block5]
list_of_reachable_memory = [block1, block2, block3]
list_of_unreachable_memory = [block4, block5]

function garbage_collect():
    for block in list_of_memory_blocks:
        if block in list_of_unreachable_memory:
            deallocate_memory(block) > This pseudocode demonstrates a simplified representation of managing memory as sets. In this example, list_of_memory_blocks represents allocated memory, while list_of_reachable_memory contains blocks currently in use and list_of_unreachable_memory contains blocks no longer needed. The garbage_collect() function iterates through all memory blocks, identifying and deallocating blocks marked as unreachable, mimicking the essence of garbage collection.

4. Making Memory Work on Its Own

The evolution of memory management witnessed a transformative phase with the advent of automated systems. The quest to relieve programmers from manual memory handling led to the development of mechanisms that could autonomously manage memory. This marked a pivotal shift as programming languages began incorporating features to automate memory allocation and deallocation. Garbage collection, arising from this pursuit, enabled systems to identify and release memory that was no longer needed. The birth of these automated memory management systems revolutionized programming, enhancing efficiency and reducing errors stemming from manual memory management.

function main():
    initialize_program()
    while program_running:
        if memory_required():
            allocate_memory()
        else if memory_not_needed():
            release_memory()

function initialize_program():
    // Initialize necessary variables and data structures
    // Set up automated memory management

function memory_required():
    // Check if additional memory is needed for operations
    // Return true if memory allocation is necessary, else false

function memory_not_needed():
    // Identify unused or unnecessary memory
    // Determine conditions to release memory
    // Return true if memory can be released, else false

function allocate_memory():
    // Allocate memory as per program requirements
    // Automate memory allocation process

function release_memory():
    // Identify and release memory that's no longer required
    // Automate memory deallocation process

5. Using Math to Manage Memory

Mathematics plays a fundamental role in optimizing memory management within programming languages. Concepts derived from mathematical models, such as graph theory and algorithms, form the backbone of various garbage collection strategies. Algorithms like mark-and-sweep and reference counting draw heavily from mathematical principles to identify and manage memory effectively. The intricate application of mathematical models aids in determining the lifespan and usage patterns of allocated memory.

6. Exploring Algorithmic Approaches to Garbage Collection

Garbage collection strategies in programming languages encompass diverse scientific methodologies governing memory management and reclamation. These approaches employ unique algorithms, tactics, and targeted domains, tailored to adapt specific language demands and system constraints.

Mark-and-Sweep Algorithm

Identifies and reclaims memory by marking reachable and unreachable objects, followed by sweeping and deallocating unreachable ones. It widely utilized in languages like Lisp, JavaScript, and Ruby.

function mark_and_sweep():
    mark_reachable_objects()
    sweep_unreachable_objects()

Reference Counting

It tracks reference counts for objects, deallocating memory when counts reach zero. it’s been implemented in languages like Python and COM.

function reference_counting(object):
    object.reference_count++
    if object.reference_count == 0:
        deallocate_memory(object)

Generational Garbage Collection

It sorts objects into generations based on age, performing garbage collection on different generations at varying frequencies. Highly effective in Java and .NET.

function generational_gc():
    for object in heap:
        if object.age >= threshold:
            promote_to_older_generation(object)

Copying Garbage Collection

It divides memory into two spaces, copying live objects from one space to another while reclaiming memory from the first. Used in Smalltalk.

function copying_gc():
    while scanning_objects:
        if object.is_live():
            copy_to_new_space(object)

Concurrent and Parallel Garbage Collection

It performs garbage collection concurrently or in parallel with the application to minimize pauses and enhance performance. Used in modern systems like Java’s G1 garbage collector and Go language.

function concurrent_gc():
    while application_running:
        if need_to_collect():
            start_concurrent_process()

7. Python’s Way of Handling Garbage Collection

Python, known for its simplicity and versatility, employs an automatic garbage collection mechanism that alleviates developers from manual memory management. Python’s memory management system primarily revolves around reference counting, augmented by a cyclic garbage collector, ensuring efficient memory usage and timely reclamation of unused objects. Python’s fundamental approach to garbage collection relies on reference counting. Each object in Python carries a reference count, indicating the number of references pointing to it. When the count reaches zero, implying no active references, Python’s interpreter automatically deallocates the memory associated with that object. While simple and efficient for handling short-lived objects, reference counting might struggle with cyclic references, where objects reference each other, resulting in memory leaks.

# Example showcasing reference counting in Python

import sys

# Creating objects and checking reference counts
a = [1, 2, 3]
b = a  # Both a and b reference the same list

print(sys.getrefcount(a))  # Display reference count of 'a'
del b  # Removing one reference to the list

print(sys.getrefcount(a))  # Display updated reference count of 'a' > In this Python example, a is a list, and b references the same list as a. The sys.getrefcount() function allows checking the reference count of an object. Initially, both a and b reference the list, and the reference count is incremented accordingly. When b is deleted, reducing the references to the list, the reference count decreases.

To address cyclic references and occasional memory leaks, Python incorporates a cyclic garbage collector. This collector identifies and clears cyclically referenced objects by traversing the object graph and marking objects as unreachable, breaking cyclic dependencies. The garbage collector initiates collection cycles periodically or when the number of allocations surpasses a predefined threshold, thus supplementing reference counting to manage more complex memory scenarios. Python’s garbage collector implements a generational approach, dividing objects into different generations based on their age. Younger objects reside in the younger generations, undergoing more frequent and faster garbage collection cycles, whereas long-lived objects get promoted to older generations and undergo less frequent collection cycles. This approach, inspired by generational garbage collection algorithms, optimizes memory management by focusing garbage collection efforts where they’re most effective.

# Example illustrating cyclic garbage collection in Python

import gc

class Node:
    def __init__(self):
        self.next = None

# Creating cyclic references
node1 = Node()
node2 = Node()
node1.next = node2
node2.next = node1

# Triggering cyclic garbage collection manually
gc.collect() > This Python example demonstrates cyclic references between two Node objects, node1 and node2, where each node refers to the other. The gc.collect() function manually triggers the garbage collector to identify and clear cyclically referenced objects, breaking the cycle and allowing their memory to be reclaimed.

Python’s garbage collector allows for tuning and optimization through various mechanisms. Developers can control the garbage collector’s behavior using the **gc** module, adjusting thresholds, disabling or enabling garbage collection, or fine-tuning collection frequency. Additionally, Python provides memory profiling tools like **objgraph** and gc module functions (**get_stats**(), **set_threshold**()) to analyze memory usage, detect leaks, and optimize memory management strategies.

# Example showcasing generational garbage collection in Python

import gc

# Creating objects in different generations
young_objects = [i for i in range(1000)]  # Young objects
older_objects = [i for i in range(1000)]  # Old objects

# Manually triggering garbage collection
gc.collect()

# Checking generation information for objects
print(gc.get_count())  # Get the number of collections by generation > This Python example creates two sets of objects, one representing younger objects and the other representing older objects. The gc.collect() function manually initiates garbage collection. The gc.get_count() function retrieves the number of collections performed for each generation, indicating how many garbage collection cycles were executed for the different object generations.

Python’s automatic garbage collection alleviates manual memory management burdens, enhancing developer productivity and reducing the likelihood of memory leaks. However, the overhead incurred by garbage collection mechanisms might marginally impact performance, especially in applications dealing with real-time constraints. By offering flexibility in tuning and optimization, Python enables developers to strike a balance between memory efficiency and performance, making it a preferred choice for a wide range of applications.

8. References

• “Garbage Collection in Python” — Python Documentation

• “Understanding Python’s Garbage Collection” — Real Python