CPython Memory Allocator Hierarchy & PyMalloc

Python creates and destroys millions of small objects (such as integers, short strings, and tuple pairs) throughout a typical application lifecycle.

Routing all of these tiny allocations directly to the operating system's general-purpose heap allocator (malloc and free) would cause severe memory fragmentation and heavy kernel syscall overhead.

To achieve high throughput, CPython incorporates PyMalloc: a specialized small-object memory allocator layered directly above the system heap.

PyMalloc Small Object BoundaryMemory Domain

<= 512 B

Allocations of 512 bytes or smaller are handled by PyMalloc; larger requests route to system malloc.

1. The Three Allocation Domains#

CPython divides memory allocations into three distinct size domains based on request size $S$ bytes:

\mathbf{PyMalloc} & \text{if } 1 \le S \le 512 \text{ bytes} \quad (\text{Fast Small Object Allocator}) \\ \mathbf{PyMem\_Raw} & \text{if } S > 512 \text{ bytes} \quad (\text{Direct OS Heap Wrapper: } \text{malloc}/\text{realloc}) \\ \mathbf{PyObject\_Arena} & \text{for internal 256 KB aligned memory allocations}

Architecture Diagram

Rendering diagram...

2. The 3-Tier PyMalloc Hierarchy#

PyMalloc structures heap memory into a strict three-tier hierarchy: Arenas, Pools, and Blocks.

Architecture Diagram

Rendering diagram...

1. Blocks (The Allocation Unit)#

A block is a chunk of contiguous memory formatted to a specific size class. PyMalloc defines 64 size classes, spanning 8 bytes to 512 bytes in increments of 8:

\text{Size Classes}: 8, 16, 24, 32, 40, \dots, 512 \text{ bytes}

\text{Size Class Index } I = \left\lfloor \frac{S - 1}{8} \right\rfloor \in [0, 63]

2. Pools (The Page Unit)#

A pool is a single $4 \text{ KB}$ virtual memory page. Every pool is dedicated exclusively to one single size class. A pool configured for 32-byte blocks contains only 32-byte blocks. Each pool is managed by a pool_header struct containing:

Size class index.
Number of free blocks available.
freeblock: Pointer to the head of a singly-linked list of available unallocated blocks.

3. Arenas (The Operating System Chunk)#

An arena is a large $256 \text{ KB}$ memory block requested from the operating system via malloc(). Each arena contains exactly 64 pools ( $64 \times 4\text{ KB} = 256\text{ KB}$ ). Arenas are tracked in a doubly-linked list sorted by available free pools.

3. Fast Path Allocation: $O(1)$ Mechanics#

How does PyMalloc allocate a small object in constant time?

Step 1: Compute Size Class Index

Given request size $S$ , PyMalloc calculates size class index $I = (S - 1) \gg 3$ .

Step 2: Query `usedpools` Array

PyMalloc maintains a global lookup array usedpools containing pointers to active pools that have available space for each size class. It looks up pool = usedpools[I * 2].

Step 3: Pop from Singly-Linked Freeblock List

The pool->freeblock pointer references the first available memory block in the pool. PyMalloc extracts this block, advances freeblock to the next block, and returns the pointer immediately:

1
2
block = pool->freeblock;
pool->freeblock = *(uchar **)block;

This fast path executes in just a handful of CPU instructions without acquiring OS kernel mutex locks!

4. Pool Occupancy & Memory Deallocation#

When an object is freed, PyMalloc returns the block to the pool's freeblock list:

\text{Pool State} \in \{\text{Empty } (\eta = 0), \text{ Partially Used } (0 < \eta < 1), \text{ Full } (\eta = 1)\}

Where pool occupancy ratio $\eta$ is:

\eta = \frac{N_{\text{allocated\_blocks}}}{N_{\text{total\_blocks}}} \in [0, 1]

When all pools inside an arena become empty ( $\eta = 0$ for all 64 pools), PyMalloc releases the entire 256 KB arena back to the operating system kernel via free().

Memory Fragmentation and Retained RAM

If an arena contains even a single 16-byte object that remains alive inside one pool, the operating system cannot reclaim that 256 KB arena! This explains why Python process memory may not immediately drop after deleting large collections.

5. Concept Verification#

Test your understanding of CPython memory allocators:

Concept check

What is the maximum object request size handled by CPython's specialized PyMalloc allocator before falling back to system malloc?