vault

The pymalloc Allocator

15 min read

The pymalloc Allocator

pymalloc is CPython’s specialized allocator for small objects — every request of 512 bytes or fewer (the SMALL_REQUEST_THRESHOLD). Rather than hand each tiny allocation to the C library’s malloc, pymalloc carves large memory regions from the operating system once and then satisfies the flood of small PyObject allocations out of pre-segregated free lists, almost always without touching the system allocator at all. Its whole reason to exist is that a Python program allocates and frees small objects constantly — integers, tuples, dict entries, frames — and a general-purpose malloc is both too slow and too prone to fragmentation for that workload. This note covers the policy and the allocation fast path; the three-level arena/pool/block data structures it manages are covered in its sibling, Arenas Pools and Blocks. (Verified against Objects/obmalloc.c and Include/internal/pycore_obmalloc.h in CPython 3.14.)

pymalloc is the implementation behind the PYMEM_DOMAIN_OBJ allocator domain — the one CPython uses for every PyObject_Malloc / PyObject_Free call (see The Memory Allocator Domains). It sits above the raw system allocator and below the object-specific Free Lists that types like int, float, and list keep for themselves. It is the default object allocator unless CPython was built --without-pymalloc or the PYTHONMALLOC=malloc environment variable redirects the object domain to plain malloc.

Why pymalloc Exists

A running Python interpreter is an allocation storm. Almost every operation creates short-lived PyObjects: evaluating a + b may allocate a new int; building a list comprehension allocates the list and possibly many elements; calling a function allocates a frame and argument tuple. These objects are overwhelmingly small — most are well under 512 bytes — and they are created and destroyed at enormous rates. The obmalloc.c design comment states the allocator “is called for every object allocation and deallocation (PyObject_New/Del), unless the object-specific allocators implement a proprietary allocation scheme” (per the pycore_obmalloc.h comment).

Routing each of those through the system malloc would hurt in three ways:

  1. Per-call overhead. A general-purpose malloc must handle requests from one byte to gigabytes, with thread safety, coalescing of freed neighbors, and search through size-segregated bins. That machinery is overkill for a 24-byte tuple, and the fixed cost per call dominates when the payload is tiny.
  2. Bookkeeping waste. Many malloc implementations attach a header (size, flags) to every allocation. For a 16-byte object an 8- or 16-byte header is 50–100% overhead. pymalloc stores zero per-block bookkeeping — a block is just raw bytes; all metadata lives once per 16 KiB pool (see Arenas Pools and Blocks).
  3. Fragmentation. A stream of interleaved small allocations and frees of mixed sizes leaves a general allocator’s heap pocked with unusable gaps. pymalloc sidesteps this with simple segregated storage: each size class has its own free list, so a freed 32-byte block can only ever be reused for another 32-byte request — no gaps form within a size class. The design comment names this explicitly: the strategy “is a variant of what is known as ‘simple segregated storage based on array of free lists’” (per the design abstract). See Memory Fragmentation in CPython for the residual fragmentation pymalloc cannot eliminate.

The trade-off pymalloc accepts is that it manages memory in coarse chunks and can be slow to return memory to the OS — a topic the sibling note develops. For the small-object workload it targets, the comment notes the “technique is quite efficient for memory intensive programs which allocate mainly small-sized blocks.”

Mental Model

Think of pymalloc as a gatekeeper with a bank of vending machines. Every allocation request arrives at the gate. The gatekeeper checks one number — the request size — and makes a single binary decision: small enough (≤ 512 bytes) goes to the vending machines; anything larger is waved through to the system malloc. Each vending machine dispenses blocks of exactly one fixed size (one size class); the gatekeeper computes which machine to use by a couple of integer shifts, with no searching. Pull the lever and you get the block at the front of that machine’s tray; the next block slides forward. Returning a block just drops it back on the front of the tray.

flowchart TD
    REQ["PyObject_Malloc(nbytes)"] --> Z{"nbytes == 0?"}
    Z -- yes --> NULLp["return NULL → fall to malloc(0)"]
    Z -- no --> T{"nbytes > 512<br/>(SMALL_REQUEST_THRESHOLD)?"}
    T -- "yes (large)" --> SYS["PyMem_RawMalloc<br/>(system allocator)"]
    T -- "no (small)" --> IDX["size = (nbytes-1) >> ALIGNMENT_SHIFT<br/>pool = usedpools[size+size]"]
    IDX --> HAS{"pool has a<br/>used pool?<br/>(pool != pool-&gt;nextpool)"}
    HAS -- yes --> POP["pop head of pool-&gt;freeblock list<br/>++pool-&gt;ref.count"]
    HAS -- no --> NEW["allocate_from_new_pool():<br/>grab a free pool from an arena"]
    POP --> DONE["return block"]
    NEW --> DONE
    POP --> EXT{"freeblock now NULL?"}
    EXT -- yes --> VIRGIN["pymalloc_pool_extend():<br/>expose next virgin block"]
    VIRGIN --> DONE

    style T fill:#fde68a
    style SYS fill:#fca5a5
    style POP fill:#bbf7d0

Figure: the pymalloc allocation decision tree. The single load-bearing insight is that the common case — a small request with a partially-used pool already on hand — is a constant-time free-list pop with no locking-free searching and no system call. The two branches that touch arenas/pools (allocate_from_new_pool, pymalloc_pool_extend) are the slow paths that occasionally refill the vending machines from the structures described in Arenas Pools and Blocks.

The 512-Byte Threshold

The routing decision hinges on one macro:

#define SMALL_REQUEST_THRESHOLD 512
#define NB_SMALL_SIZE_CLASSES   (SMALL_REQUEST_THRESHOLD / ALIGNMENT)

SMALL_REQUEST_THRESHOLD is 512 bytes. The design comment documents two invariants the build must satisfy: ALIGNMENT <= SMALL_REQUEST_THRESHOLD <= 512, and SMALL_REQUEST_THRESHOLD must be evenly divisible by ALIGNMENT (per pycore_obmalloc.h). The upper bound of 512 is deliberate: the comment notes that “a size threshold of 512 guarantees that newly created dictionaries will be allocated from preallocated memory pools on 64-bit” — that is, the threshold was chosen so the most common small containers fall inside pymalloc’s reach.

The check is the first thing the allocator does after rejecting a zero-byte request:

if (UNLIKELY(nbytes == 0)) {
    return NULL;
}
if (UNLIKELY(nbytes > SMALL_REQUEST_THRESHOLD)) {
    return NULL;
}

Returning NULL here does not mean failure — it means “pymalloc declines this request.” The caller, _PyObject_Malloc, interprets that NULL as the signal to fall back to the system allocator:

void *
_PyObject_Malloc(void *ctx, size_t nbytes)
{
    OMState *state = get_state();
    void* ptr = pymalloc_alloc(state, ctx, nbytes);   // try pymalloc
    if (LIKELY(ptr != NULL)) {
        return ptr;                                    // small: served from a pool
    }
    ptr = PyMem_RawMalloc(nbytes);                     // large (or 0): system malloc
    if (ptr != NULL) {
        raw_allocated_blocks++;                        // counted so shutdown can audit
    }
    return ptr;
}

So a 600-byte object, or a 100 KB buffer, never enters pymalloc’s pools — it goes straight to PyMem_RawMalloc, which is the system malloc (or whatever the raw domain is configured to). The raw_allocated_blocks counter lets the interpreter detect leaks of large blocks at shutdown.

Size Classes and Alignment

Within the small range, pymalloc does not allocate the exact requested size. It rounds every request up to the next multiple of ALIGNMENT, and each distinct rounded size is a size class. The alignment macros differ by pointer width:

#if SIZEOF_VOID_P > 4
#define ALIGNMENT              16               /* must be 2^N */
#define ALIGNMENT_SHIFT         4
#else
#define ALIGNMENT               8               /* must be 2^N */
#define ALIGNMENT_SHIFT         3
#endif

On a 64-bit build (SIZEOF_VOID_P > 4, i.e. an 8-byte pointer) — which is what almost everyone runs — ALIGNMENT is 16 and ALIGNMENT_SHIFT is 4. Because NB_SMALL_SIZE_CLASSES = 512 / 16, there are 32 size classes: 16, 32, 48, …, 512 bytes. On a 32-bit build, ALIGNMENT is 8 and there are 64 classes (8, 16, …, 512).

The in-file size-class table illustrates the 32-bit case

The large explanatory table in pycore_obmalloc.h (“Request in bytes / Size of allocated block / Size class idx”) lists rows 1-8 → 8 → idx 0 through 505-512 → 512 → idx 63, and the prose says classes are “spaced 8 bytes apart.” That table depicts the 32-bit configuration (ALIGNMENT = 8, 64 classes). On a 64-bit build the macros yield 16-byte alignment and 32 classes (idx 0 = 16 bytes … idx 31 = 512 bytes). The runtime always follows the macros — INDEX2SIZE and the fast-path shift below both use ALIGNMENT_SHIFT — so on 64-bit the effective table is 16,32,…,512. I verified this against the macro definitions and the fast-path code; only the comment’s worked example reflects the older 8-byte case. (source)

Two helper macros convert between a size-class index I and its block size in bytes:

/* Return the number of bytes in size class I, as a uint. */
#define INDEX2SIZE(I) (((pymem_uint)(I) + 1) << ALIGNMENT_SHIFT)

INDEX2SIZE(I) computes (I+1) << ALIGNMENT_SHIFT. On 64-bit (ALIGNMENT_SHIFT = 4, i.e. multiply by 16): INDEX2SIZE(0) = 1 << 4 = 16, INDEX2SIZE(1) = 2 << 4 = 32, …, INDEX2SIZE(31) = 32 << 4 = 512. The +1 is what makes index 0 the 16-byte class rather than a zero-byte class — there is no zero-size class because a zero-byte request is rejected before this point.

The consequence of size-class rounding is internal fragmentation: a request for 17 bytes consumes a 32-byte block (on 64-bit), wasting 15 bytes. This waste is bounded by ALIGNMENT - 1 bytes per allocation and is the price of never having to search or coalesce. It is distinct from the external fragmentation that pymalloc’s pool design is built to avoid — see Memory Fragmentation in CPython.

The Allocation Fast Path

The heart of pymalloc is pymalloc_alloc. Having passed the threshold check, it computes a size-class index and indexes the usedpools table — pymalloc’s free-list-of-pools — in two integer operations:

uint size = (uint)(nbytes - 1) >> ALIGNMENT_SHIFT;
poolp pool = usedpools[size + size];
pymem_block *bp;

size = (nbytes - 1) >> ALIGNMENT_SHIFT is the size-class index. The -1 then right-shift is integer “round up to the next class”: for nbytes in 1–16 the result is 0; for 17–32 it is 1; and so on (on 64-bit). This is the inverse of INDEX2SIZE. There is no division, no table lookup, no branch — two ALU operations turn a byte count into a class index.

usedpools[size + size] is the per-class entry in the pool table, a “headed, circular, doubly-linked list of partially used pools” (per the pycore_obmalloc.h comment). The index is doubled (size + size) because of a deliberate space optimization: each conceptual entry stores only two pointers (nextpool and prevpool) rather than a whole pool_header, so the array is laid out so that usedpools[i+i] “acts like” a genuine pool pointer when only those two members are referenced. The comment itself calls this a “Major obscurity” and admits “It’s unclear why the usedpools setup is so convoluted” beyond minimizing the cache footprint of this “heavily-referenced table.” The mechanics of that table — the structure — belong to Arenas Pools and Blocks; here we only need that usedpools[size+size] yields the head pool for the size class.

From there the fast path forks:

if (LIKELY(pool != pool->nextpool)) {
    /* There is a used pool for this size class. */
    ++pool->ref.count;
    bp = pool->freeblock;
    assert(bp != NULL);
    if (UNLIKELY((pool->freeblock = *(pymem_block **)bp) == NULL)) {
        // Reached the end of the free list, try to extend it.
        pymalloc_pool_extend(pool, size);
    }
}
else {
    /* There isn't a pool of the right size class immediately available:
       use a free pool. */
    bp = allocate_from_new_pool(state, size);
}
return (void *)bp;

Walking it:

  • pool != pool->nextpool is the test for “is there a usable pool for this class?” Because the list is circular and headed, an empty list is one where the head points to itself — so pool == pool->nextpool means no pool, and the LIKELY inequality means there is one. The LIKELY/UNLIKELY macros are branch-prediction hints; the compiler lays out the common case (a pool exists) as the fall-through.
  • ++pool->ref.count records one more outstanding block in this pool. ref.count is how the free path later knows when a pool has become empty.
  • bp = pool->freeblock grabs the block at the head of the pool’s free list. This pointer is the returned memory.
  • pool->freeblock = *(pymem_block **)bp advances the free list. A free block’s first word is reused to store the pointer to the next free block — the free list is threaded through the free blocks themselves, costing zero extra memory. Reading *(pymem_block **)bp follows that link.
  • If advancing makes freeblock NULL, the pool’s linked free list is exhausted but the pool may still contain virgin blocks never yet handed out. pymalloc_pool_extend exposes the next virgin block by bumping the pool’s nextoffset — the lazy carving described in Arenas Pools and Blocks. The point worth holding here: even this “slow” branch is still pure pointer arithmetic within an already-mapped pool, with no system call.
  • allocate_from_new_pool is the genuinely slow path, taken only when no pool exists for the class. It pulls a fresh pool from an arena’s free-pool list, allocating a new arena from the OS if necessary. That machinery — usable_arenas, freepools, new_arena, mmap — is entirely the subject of Arenas Pools and Blocks.

The deallocation fast path is the mirror image, in pymalloc_free: it rounds the freed pointer down to its pool header with POOL_ADDR(p), verifies the address belongs to pymalloc with address_in_range, then pushes the block back onto the front of pool->freeblock and decrements ref.count. Most frees are exactly that — three writes and a decrement. Only when a free empties a pool, or un-fills a previously full one, does pymalloc touch the pool-table or arena structures (those transitions are documented in Arenas Pools and Blocks).

Common Misunderstandings

  • “pymalloc replaces malloc.” It does not. It is a cache in front of the system allocator for small objects, and every large allocation and every arena still goes to malloc/mmap. Disabling pymalloc (PYTHONMALLOC=malloc) sends all object allocations to the system allocator — useful when running under tools like Valgrind or AddressSanitizer, which want to see every raw allocation.
  • “512 bytes is the object size cutoff.” The threshold is on the raw byte request passed to PyObject_Malloc, not on the Python-visible object. A Python object’s C struct includes its header (PyObject / PyVarObject), so the threshold maps to objects somewhat smaller than 512 user-visible bytes. The routing test is purely on nbytes.
  • “A small allocation always hits a pool.” Only if the build has pymalloc enabled and the request is in (0, 512]. A zero-byte request returns NULL from pymalloc and goes to malloc(0); this is why even empty allocations have defined behavior.
  • “The size-class table in the source is the real table.” On 64-bit it is not — see the note above. Trust the macros (ALIGNMENT = 16, 32 classes), not the comment’s 8-byte worked example.

Alternatives and When to Choose Them

pymalloc is one configurable layer. CPython lets you swap it out:

  • PYTHONMALLOC=malloc routes the object domain straight to the C library malloc/free, bypassing pools. Slower for typical workloads but transparent to memory debuggers.
  • PYTHONMALLOC=pymalloc_debug wraps pymalloc with the debug allocator, which adds guard bytes, fills freed memory with a recognizable pattern, and detects buffer overruns and use-after-free at the block level.
  • --without-pymalloc at build time removes pymalloc entirely.
  • A custom allocator can be installed via PyMem_SetAllocator, which can replace any of the three domains — PYMEM_DOMAIN_RAW, PYMEM_DOMAIN_MEM, or PYMEM_DOMAIN_OBJ (per the C-API memory docs) — so embedders can substitute jemalloc or mimalloc for the whole object domain. Notably, the free-threaded build uses a mimalloc-based allocator in place of classic pymalloc for thread-safety reasons — PYTHONMALLOC=mimalloc (and mimalloc_debug) are accepted values on that build (per the C-API memory docs), and obmalloc.c itself carries mimalloc and GIL-disabled support code. The classic arena/pool/block scheme described here is the default GIL build’s allocator.

For ordinary use the default pymalloc is the right choice: it is faster than the system allocator on the small-object storm and needs no tuning.

Production Notes

You observe pymalloc indirectly. sys._debugmallocstats() (or setting PYTHONMALLOCSTATS=1) dumps per-size-class pool statistics to stderr at arena-allocation time, showing how many pools and blocks each class holds — invaluable when diagnosing why a process holds more resident memory than the live-object count suggests. The deeper diagnostic, tracemalloc and Memory Profiling, hooks the allocator domains to attribute allocations to source lines.

The pymalloc fast path is also why CPython’s memory footprint and speed are sensitive to object size distribution: a workload that allocates millions of 17-byte objects pays the 32-byte size-class rounding on every one, so shaving a field off a hot struct (or using __slots__) can cross a size-class boundary and measurably cut resident memory. See The slots Optimization and CPython Memory Management Overview.

See Also

Graph View

Backlinks