How Garbage Collection Works: Let's Build One From Scratch

Introduction: Your program creates numerous objects during runtime, such as when calling functions, iterating in loops, or parsing JSON responses. Most of these objects are not manually deleted by developers, and the application continues to function despite not exhausting all available RAM. The entity responsible for cleaning up unused memory is the garbage collector, a background component that determines which objects are no longer needed and makes that memory available for future use.

Developers typically only notice the garbage collector when issues arise, like unexpected pauses, memory leaks, or out-of-memory errors. Grasping how the garbage collector operates can turn these perplexing situations into solvable problems. Moreover, the fundamental algorithm is straightforward enough to implement yourself.

The Memory Problem: Each time your program creates an object, the runtime allocates a segment of memory to store it. Objects such as strings, dictionaries, and class instances all require memory, which comes from a region known as the heap – a pool of memory that the program utilizes as it runs. When an object is created, the runtime identifies a suitable location in the heap and reserves it.

When the object is no longer required, the slot should be released to make it available for new objects. In languages like C, managing memory is done manually – you allocate memory when needed and free it when done. This approach provides control but can lead to two common issues. Overwriting memory too soon results in a dangling pointer – a reference to memory that is now being utilized by something else.

Failing to free memory altogether leads to a memory leak, causing the program to gradually consume more and more memory until it runs out of it. Automatic memory management aims to eliminate these failure modes. Rather than depending on programmers to track every allocation and release, the runtime monitors program behavior and performs cleanup on its behalf. The question remains: how does it know what's safe to clean up?

The Simplest Idea: Reference Counting: The most intuitive approach is reference counting, which involves tracking how many references point to each object. A runtime that employs reference counting keeps a count of the number of references currently pointing to an object. When this count reaches zero, nothing in the program can access the object any longer, and the runtime can reclaim its memory immediately.

Python's standard implementation, CPython, uses reference counting as its primary mechanism. Each Python object carries a reference count; when a new reference is created, the count increases, and when a reference is removed or goes out of scope, the count decreases. When the count hits zero, memory is released immediately without waiting for a separate collection phase.

Python exposes reference counts via the sys.getrefcount() function. For example, creating a new list x and assigning it to y would result in an increased reference count for x. Deleting y would decrease the reference count for x back to its original value. However, reference counting has its limitations. Consider two objects, A and B, each holding a reference to the other.

In such a scenario, both objects will have a reference count of one even after their variables are deleted, leading to a circular reference problem. Neither object can be freed because they keep referencing each other, causing memory leakage. This limitation can be addressed by using a cyclic garbage collector that searches for isolated reference cycles among container objects and reclaims them periodically.

Reference counting is a simple and elegant solution to automatic memory management, but it's not the only approach. Another general algorithm, called mark-and-sweep, handles cycles naturally.