How PyMalloc Allocates Memory for Small Objects

This article explores PyMalloc, CPython's specialized memory allocator designed to handle small object allocations efficiently. Standard system allocators incur significant performance overhead and memory fragmentation when handling the frequent, short-lived, small allocations typical in Python programs. PyMalloc solves this by introducing a tiered memory hierarchy consisting of arenas, pools, and blocks, which caches memory requests for objects 512 bytes or smaller to maximize speed and minimize system call overhead.

The Small Object Problem in CPython

Everything in Python is an object, from simple integers and floating-point numbers to short strings and tuples. A typical Python runtime creates and destroys millions of these small data structures. If CPython relied solely on standard C library allocators (malloc and free) for every single object, two main issues would arise:

1. System Call and Bookkeeping Overhead: Standard allocators store metadata (such as allocation size) adjacent to every allocated block, often adding 8 to 16 bytes of overhead per object. For an 8-byte integer, doubling or tripling the memory footprint for metadata is highly inefficient.
2. Memory Fragmentation: Constant allocation and deallocation of varied tiny sizes leads to external fragmentation, leaving the operating system unable to allocate contiguous blocks despite having sufficient total free memory.

The Three-Tier Architecture: Arenas, Pools, and Blocks

PyMalloc avoids general-purpose allocation overhead by pre-allocating large chunks of system memory and slicing them into uniform partitions. It manages this through three distinct abstractions:

1. Blocks

A block is the smallest unit of memory returned to an application requesting space. PyMalloc restricts its operations to objects up to 512 bytes (in 64-bit systems). Blocks are grouped into fixed-size classes spaced 8 bytes apart: 8 bytes, 16 bytes, 24 bytes, up to 512 bytes (providing 64 distinct size classes). When Python requests memory for an object, PyMalloc rounds the request up to the nearest size class and assigns an appropriately sized block.

2. Pools

A pool is a 4 KB block of memory—typically matching the system's virtual memory page size. Each pool is dedicated exclusively to a single size class. For instance, one pool may only manage 32-byte blocks, while another exclusively manages 64-byte blocks.

Key pool optimizations include:

• Embedded Free Lists: Pools track free blocks using a singly linked list embedded directly within the unused blocks themselves, eliminating extra memory tracking structures.
• Pool States: A pool is categorized as empty, used, or full. Pools of the same size class with the used state are linked together in a doubly linked list. When an allocation request arrives, PyMalloc immediately grabs the first available block from the head pool in that size class's list in \(O(1)\) time.

3. Arenas

An arena is a 256 KB memory chunk allocated directly from the system heap using malloc (or mmap). An arena acts as a container for 64 pools (each 4 KB). Arenas provide the boundary between Python's custom allocator and the host operating system. When all pools within an arena become completely empty, the entire 256 KB arena can be returned to the operating system, mitigating long-term memory bloat.

How Allocations and Deallocations Work

When an object requires memory:

1. Size Check: If the requested allocation is greater than 512 bytes, PyMalloc delegates the request directly to the standard system allocator (malloc).
2. Pool Selection: For allocations \(\le\) 512 bytes, the size is mapped to its corresponding size class index. PyMalloc checks the linked list of used pools for that class.
3. Block Extraction: PyMalloc retrieves a free block from the active pool's free list in constant time (\(O(1)\)) and marks the block as occupied. If the pool becomes full, it is removed from the active list. If no used pool exists, an empty pool within an arena is initialized for that size class.

When an object is destroyed:

1. PyMalloc identifies which pool the block belongs to using bitmask operations on the memory address, avoiding lookups in global hash tables.
2. The block is added back to the pool's free list in \(O(1)\) time.
3. If the pool was previously marked as full, it is moved back into the active used list for its size class.
4. If freeing the block leaves the entire pool empty, the pool is made available to be repurposed for any size class within its arena.

By bypassing kernel-level memory management for small structures, enforcing uniform block sizes, and handling allocation logic via lightweight linked lists, PyMalloc minimizes metadata overhead, prevents fragmentation, and maintains predictable, constant-time performance for Python's memory operations.