Data Structures and Algorithms with Object-Oriented Design Patterns in Python

Garbage Collection and the Other Kind of Heap

A Python object is an instance of a Python type. For example, all integers have the type int, all floating-point numbers have the type float, all user-defined classes have the type classobj, and all instances of user-defined classes have the type instance. Every object in a Python program occupies some memory. The manner in which a Python object is represented in memory is left up to the implementor of the Python virtual machine and, in principle, can vary from one implementation to another. However, object data typically occupy contiguous memory locations.

The region of memory in which objects are allocated dynamically is often called a heap . In Chapter we consider heaps and heap-ordered trees in the context of priority queue implementations. Unfortunately, the only thing that the heaps of Chapter and the heap considered here have in common is the name. While it may be possible to use a heap (in the sense of Definition ) to manage a region of memory, typical implementations do not. In this context the technical meaning of the term heap is closer to its dictionary definition--``a pile of many things.''

The amount of memory required to represent a Python object is determined by its type. For example, four bytes are used typically to represent the value of an int, eight bytes are used typically to represent the value of a float, 24 bytes are used typically to represent the value of a classobj, and 12 bytes are used typically to represent the value of a instance. In addition to the memory required for the value of an object, there is a fixed, constant amount of extra storage set aside in every object (eight bytes). This extra storage carries information used by the Python virtual machine to represent the type of the object and to aid the process of garbage collection.

When the Python virtual machine creates an object, it performs the following steps:

An unused region of memory large enough to hold an instance of the desired class is found.
All of the fields of the object are assigned their default initial values.
The appropriate __init__ method is run to initialize the object instance.
A reference to the newly created object is returned.