Opensource internals

CPython's Pymalloc: A Fast Allocator for Small Objects

7 min read Jay Hubbert

Pymalloc is the segregated allocator behind every small object Python creates: arenas, pools, size classes, a free-list pop, and a radix tree that makes frees O(1).

TL;DR: Every small object CPython creates — a 56-byte str, a 56-byte int, a 64-byte list — comes from pymalloc, a segregated allocator built on arenas, pools, and size classes. The fast path is one array lookup, one comparison, and a free-list pop. No per-block size metadata, no system call, no scan.

Most Python objects are small. A 56-byte str, a 56-byte int, a 64-byte list: the interpreter allocates and frees these millions of times per second.

Going to the system allocator for each one would be slow, and it would fragment memory badly. CPython instead uses pymalloc, a segregated allocator tuned for objects up to 512 bytes. This article traces its three-level design and the handful of C tricks that keep the fast path short.

When pymalloc is used

pymalloc serves requests up to SMALL_REQUEST_THRESHOLD (512 bytes). Anything larger goes straight to the raw allocator.

It is the default obj and mem allocator in GIL builds. Free-threaded builds use mimalloc instead (see below), because pymalloc has no per-thread caches and leans on the GIL for safety.

The three levels

text 
arena (1 MiB; 2 MiB with hugepages; 256 KiB on 32-bit)
  └── pool (16 KiB on 64-bit; 4 KiB == page otherwise)
        └── block (8..512 bytes, 16-byte aligned on 64-bit)

The numbers behind that diagram:

  • ARENA_SIZE = 1 << ARENA_BITS (20, so 1 MiB).
  • POOL_SIZE = 1 << POOL_BITS (14, so 16 KiB on 64-bit).
  • SMALL_REQUEST_THRESHOLD = 512.
  • NB_SMALL_SIZE_CLASSES = 512 / ALIGNMENT = 32 (16-byte spacing).
  • Size class index: (nbytes - 1) >> ALIGNMENT_SHIFT (0..31).
  • Block size: INDEX2SIZE(i) = (i + 1) << ALIGNMENT_SHIFT.

Think of it as a sorting office: an arena is the building, a pool is a room, and a room only ever holds one kind of envelope. An arena is carved into pools, a pool is carved into blocks of a single size class, and every block in that pool is the same size.

That segregation is the whole point. Because a pool never mixes sizes, there’s no per-block size metadata to store and look up on free.

The structures that make it work

c 
// Include/internal/pycore_obmalloc.h
struct pool_header {
    union { pymem_block *_padding; uint count; } ref;  // allocated block count
    pymem_block *freeblock;   // singly-linked free list head
    struct pool_header *nextpool, *prevpool;  // circular used-pools list
    uint arenaindex;
    uint szidx;              // size class
    uint nextoffset;         // offset to next virgin block
    uint maxnextoffset;
};

struct arena_object {
    /* pool_address is the carving cursor */
    ...
    uint nfreepools, ntotalpools;
    struct pool_header *freepools;  // singly-linked empty pools
    ...
};

ref.count is simply the number of allocated blocks in the pool.

freeblock is a singly-linked free list threaded through the dead blocks themselves. Same intrusive-list trick CPython uses for its freelists, but here it’s happening inside a pool: the memory of a freed block holds the pointer to the next free block.

The usedpools fudge

_obmalloc_state holds an array usedpools with one slot per size class. Here’s the trick: the array is indexed as if each slot were a pool whose nextpool/prevpool point at itself, forming an empty circular list head:

c 
// Include/internal/pycore_obmalloc_init.h
/* usedpools[i] is really a pool_header* whose nextpool/prevpool are itself */

So the allocation path never has to special-case “no pools yet”. The empty list simply looks empty.

c 
// Objects/obmalloc.c
uint size = (uint)(nbytes - 1) >> ALIGNMENT_SHIFT;
poolp pool = usedpools[size + size];
if (LIKELY(pool != pool->nextpool)) {   // a used pool exists
    ++pool->ref.count;
    bp = pool->freeblock;
    if (UNLIKELY((pool->freeblock = *(pymem_block**)bp) == NULL)
        pymalloc_pool_extend(pool, size);  // carve next virgin block
}
else
    bp = allocate_from_new_pool(state, size);  // empty pool / new arena

Read that again and you’ll see the whole allocator: one array lookup, one comparison, one free-list pop. No locks on the GIL path, no size metadata, no search.

Block carving is lazy

A pool is not fully initialized when it’s handed out. Only the first two blocks are set up; nextoffset and maxnextoffset track the still-virgin region.

Blocks get carved on demand as the free list empties. A pool becomes “full” implicitly when the free list is empty and nextoffset > maxnextoffset, at which point it gets unlinked from the used list.

On free, the block is prepended to freeblock. If the pool had been full, it is re-linked to the front of the used list (LRU-ish reuse, so hot sizes stay hot). If ref.count drops to zero, the pool moves to the arena’s freepools list and the arena bookkeeping is updated.

Picking an arena without a linear scan

With many arenas, searching for one with a free pool would be O(n). CPython keeps usable_arenas sorted ascending by nfreepools and uses nfp2lasta[] “search fingers” so the lookup stays O(1) instead of linear (bpo-37029).

When an arena becomes entirely free, it goes back to the OS (_PyObject_Arena.free), its radix-tree entry is cleared, and the arena_object is recycled into unused_arena_objects.

One detail worth internalizing: one wholly-free arena is deliberately retained rather than returned immediately, to avoid thrashing (bpo-37257). Handing the memory back and immediately re-requesting it is a classic allocator disaster.

The radix tree answers “is this pointer mine?” in O(1)

On free, pymalloc must decide whether a pointer belongs to it or to the raw allocator. Guessing wrong is a memory-corruption bug, not a slow path.

On 64-bit builds a three-level radix tree (arena_map_is_used) answers that in O(depth) — roughly 3 levels — without scanning the arena array at all. On 32-bit builds a single level suffices. Without the radix tree, the code reads pool->arenaindex once (volatile) and checks allarenas[ai].address.

The radix tree also handles arenas that straddle an “ideal” boundary via arena_coverage_t { tail_hi, tail_lo }, and its top/mid arrays live in BSS and are demand-paged.

Address checks and debugging

c 
static inline int pymalloc_free(OMState *state, void *ctx, void *p) {
    poolp pool = POOL_ADDR(p);
    if (UNLIKELY(!address_in_range(state, p, pool))) return 0;  // not ours
    assert(pool->ref.count > 0);
    *(pymem_block**)p = pool->freeblock;
    pool->freeblock = (pymem_block*)p;
    pool->ref.count--;
    if (LIKELY(pool->ref.count != 0)) return 1;
    insert_to_freepool(state, pool);  // may return arena to OS
    return 1;
}

Notice the shape: check ownership, push onto the free list, decrement the count, and only when the pool empties do you do anything expensive.

Debug mode wraps every allocation with padding words: [size][id+forbidden][data][forbidden tail][serial]. _PyMem_DebugCheckAddress validates the forbidden bytes and API id; a mismatch dumps the address and fatally errors.

PYTHONMALLOCSTATS=1 triggers pymalloc_print_stats (or mimalloc stats), also reachable from Python via sys._debugmallocstats().

Free-threaded builds: mimalloc plus QSBR

pymalloc leans on the GIL, so a Py_GIL_DISABLED build needs WITH_MIMALLOC and uses mimalloc for the mem and obj domains.

Mimalloc brings per-thread heaps and caches. CPython layers Python-specific pieces on top:

  • Separate heaps for GC objects (_Py_MIMALLOC_HEAP_GC, _GC_PRE) so the GC header/pre-header layout is honored.
  • Object realloc copies the PyObject header atomically, word by word, before memcpy-ing the rest.
  • QSBR delayed free: freed pointers and refcount decrements are queued in _mem_work_chunk (254 items, 4096 bytes) with a QSBR goal and processed from the eval breaker when _Py_qsbr_poll succeeds. Limits: QSBR_DEFERRED_LIMIT 127, QSBR_FREE_MEM_LIMIT 1 MiB, QSBR_PAGE_MEM_LIMIT 80 KiB. This is what prevents use-after-free when another thread is still reading a refcount.
  • Threads donate segments with live blocks on exit; other threads claim and reuse them.

Gotcha: the free-threaded allocator story is genuinely different from the GIL story. If you’re reasoning about allocator behavior, check whether your build is Py_GIL_DISABLED first.

Interpreters and huge pages

  • The main interpreter (and interpreters with Py_RTFLAGS_USE_MAIN_OBMALLOC) share obmalloc_state_main in BSS (~256 KiB, mostly the radix top array). Subinterpreters with their own state get a heap-allocated state.
  • Huge pages: with PYMALLOC_USE_HUGEPAGES and --with-pymalloc-hugepages, the arena size becomes 2 MiB via MAP_HUGETLB (Linux) or VirtualAlloc (Windows), reducing TLB misses.

Wrapping up: why pymalloc is fast

The fast path is a size-class lookup, one comparison against a self-looping list head, and a free-list pop. No size stored per block. No global lock beyond the GIL. No system call.

Segregation by size class means a pool either fits your request exactly or gets skipped entirely. The radix tree makes frees O(1) with respect to the number of arenas.

For the millions of small objects Python creates per second, that is the difference between a usable interpreter and a slow one.

The one thing to remember: pymalloc’s speed comes from not asking questions. It never has to work out how big a block is, whether it owns a pointer, or which pool to search — all of that is answered by structure instead of by computation.

If you want to see it for yourself, set PYTHONMALLOCSTATS=1 and watch the arena and pool counts move as you churn through a list of a million small tuples.

PythonCpythonInternalsMemoryPerformance