Free Lists

A free list (CPython spells the struct _Py_freelist) is a per-type cache of dead-but-not-freed objects. When a small, frequently churned object such as a float or a short tuple is deallocated, instead of returning its memory to the object-domain allocator, CPython pushes the object onto a singly linked list of free objects of that exact type. The next time a new object of that type is requested, the allocation routine pops one off the free list and reinitialises it in place — skipping the PyObject_Malloc/PyObject_Free round-trip entirely (verified in Objects/floatobject.c and Objects/tupleobject.c). For workloads that create and destroy millions of throwaway floats or tuples — numeric loops, comprehensions, unpacking — this turns a relatively expensive allocator call into a couple of pointer assignments. As of CPython 3.14 the historically scattered, per-type free lists have been consolidated into one struct, _Py_freelists, held per-interpreter in the GIL build and per-thread in the free-threaded build.

This note is about free lists as a layer: what they cache, which types use them, the 3.12/3.13 consolidation, the size caps, and how free-threading reshapes them. The allocator they sit on top of is in The Memory Allocator Domains and The pymalloc Allocator.

Mental Model: A Recycling Bin in Front of the Allocator

A free list is best understood as a small recycling bin that sits between a type’s constructor/destructor and the general allocator. The destructor, instead of throwing the object away, drops it in the bin (up to a capacity limit). The constructor checks the bin first; only if it is empty does it ask the allocator for fresh memory. Because every object in the bin is already the right size and the right type, “reusing” one is just: pop the head, write the new field values, hand it back. No size computation, no pool lookup, no system call.

flowchart LR
    new["PyFloat_FromDouble(x)"] --> pop{"free list<br/>empty?"}
    pop -->|"no"| reuse["pop head,<br/>set ob_fval = x"]
    pop -->|"yes"| alloc["PyObject_Malloc(...)<br/>+ _PyObject_Init"]
    reuse --> live["live float"]
    alloc --> live
    live --> dead["refcount hits 0<br/>float_dealloc"]
    dead --> full{"free list<br/>full?<br/>(size >= MAXFREELIST)"}
    full -->|"no"| push["push onto free list<br/>(stays allocated)"]
    full -->|"yes"| free["PyObject_Free(obj)<br/>(real deallocation)"]
    push -.->|"next alloc"| pop

Figure: the life-cycle of a freelisted float. The insight: an object only reaches the real allocator (PyObject_Malloc/PyObject_Free) on the cold path — when the bin is empty on allocation or full on deallocation. The hot path is pure pointer shuffling, which is why free lists matter for allocation-heavy code even though they save nothing on memory and add a fixed cap of retained objects.

How a Free List Actually Works

The unit of the consolidated design is the _Py_freelist struct, verified in Include/internal/pycore_freelist_state.h:

struct _Py_freelist {
    void *freelist;     /* head of an intrusive singly linked list of dead objects */
    Py_ssize_t size;    /* current count, or -1 when the free list is disabled */
};

The list is intrusive: there is no separate node allocation. A dead object’s own memory is reused to store the “next” pointer — for most types the first word of the freed object (its ob_type/ob_fval/first slot) is overwritten with the address of the next free object. The size field tracks how many objects the list currently holds so the push path can compare against the per-type cap, and the special value -1 marks a free list that has been disabled (used during interpreter finalization so that late deallocations go straight to the allocator instead of repopulating a list that is about to be torn down).

All the individual lists are bundled into one aggregate, struct _Py_freelists, holding one _Py_freelist per cached type (and, for tuples, an array of them indexed by length). Access goes through a single accessor macro, _Py_freelists_GET(), whose definition is the heart of the free-threading story (verified in Include/internal/pycore_freelist.h):

/* GIL-disabled (free-threaded) build: */
#define _Py_freelists_GET()  (&((_PyThreadStateImpl*)tstate)->freelists)
/* GIL-enabled build: */
#define _Py_freelists_GET()  (&tstate->interp->object_state.freelists)

In a normal GIL build the free lists live in the per-interpreter state (tstate->interp->object_state.freelists); every thread in that interpreter shares them, which is safe because the GIL serialises access. In a free-threaded build, sharing them would require locking on the hottest allocation path in the runtime, so they move to the per-thread state (_PyThreadStateImpl->freelists) — each OS thread gets its own private free lists, no synchronisation needed. This is the resolution of issue gh-111968, “Use per-thread freelists in --disable-gil builds,” which states the problem plainly: freelists “are generally stored in the per-interpreter state, which is not thread-safe without the GIL,” so “in --disable-gil builds, the freelists should be stored in the per-thread state (i.e., PyThreadState).”

The push/pop/free operations are uniform macros:

/* pop a reusable object, or NULL if the list is empty: */
_Py_FREELIST_POP(TYPE, NAME)
    -> _Py_CAST(TYPE*, _PyFreeList_Pop(&_Py_freelists_GET()->NAME))
/* push op onto the list; returns 1 if cached, 0 if the list was full: */
_Py_FREELIST_PUSH(NAME, op, limit)
    -> _PyFreeList_Push(&_Py_freelists_GET()->NAME, _PyObject_CAST(op), limit)
/* push if room, else call freefunc to really deallocate: */
_Py_FREELIST_FREE(NAME, op, freefunc)
    -> _PyFreeList_Free(&_Py_freelists_GET()->NAME, _PyObject_CAST(op),
                        Py_##NAME##_MAXFREELIST, freefunc)

The _Py_FREELIST_FREE macro is the one a destructor calls: it pushes onto the list if there is room (below Py_##NAME##_MAXFREELIST) and otherwise invokes freefunc (e.g. PyObject_Free or PyObject_GC_Del) to do the real deallocation. This is the single decision point that bounds how much memory the free list can pin.

Worked example: floats

The cleanest case is PyFloat. Its constructor and destructor (verified in floatobject.c):

PyObject *
PyFloat_FromDouble(double fval)
{
    PyFloatObject *op = _Py_FREELIST_POP(PyFloatObject, floats);   /* try the bin first */
    if (op == NULL) {                                              /* bin empty: cold path */
        op = PyObject_Malloc(sizeof(PyFloatObject));               /* OBJ-domain allocator */
        if (!op) { return PyErr_NoMemory(); }
        _PyObject_Init((PyObject*)op, &PyFloat_Type);              /* set type, refcount=1 */
    }
    op->ob_fval = fval;                                            /* reuse: just write the value */
    return (PyObject *) op;
}
 
void
_PyFloat_ExactDealloc(PyObject *obj)
{
    assert(PyFloat_CheckExact(obj));
    _Py_FREELIST_FREE(floats, obj, PyObject_Free);                 /* recycle, or really free if full */
}

Reading the constructor line by line: _Py_FREELIST_POP pops a dead PyFloatObject if one is cached; on a cache miss it falls through to PyObject_Malloc (the OBJ domain) plus _PyObject_Init to stamp the type and reference count. Either way, the object’s ob_fval is overwritten with the new value and returned. The destructor _PyFloat_ExactDealloc simply hands the object to _Py_FREELIST_FREE, which caches it up to Py_floats_MAXFREELIST (100) and otherwise calls PyObject_Free. Note the CheckExact guard: only exact float instances are recycled — a subclass of float may have extra state and a different size, so it bypasses the free list and goes straight to tp_free.

Worked example: tuples (an array of free lists)

Tuples are more elaborate because tuple length is part of the object’s identity — a 1-tuple and a 5-tuple are different sizes. So tuples keep an array of free lists, one per length, capped by PyTuple_MAXSAVESIZE (20). The relevant fragments (verified in tupleobject.c):

/* in tuple_alloc(): */
Py_ssize_t index = size - 1;
if (index < PyTuple_MAXSAVESIZE) {
    PyTupleObject *op = _Py_FREELIST_POP(PyTupleObject, tuples[index]);
    ...
}
 
/* in maybe_freelist_push() (called from tuple_dealloc): */
Py_ssize_t index = Py_SIZE(op) - 1;
if (index < PyTuple_MAXSAVESIZE) {
    return _Py_FREELIST_PUSH(tuples[index], op, Py_tuple_MAXFREELIST);
}
return 0;

A tuple of length n is cached in tuples[n-1]; only lengths 1..20 qualify (the empty tuple is a singleton handled separately, and lengths above 20 are too rare and too large to be worth pinning). Each per-length list holds up to Py_tuple_MAXFREELIST (2000) tuples. The destructor’s maybe_freelist_push returns 0 when the tuple is too long or the list is full, and the caller then falls back to tp_free. This length-indexed scheme is why building short tuples in a tight loop (for x in it: process((x, key))) is nearly free of allocator traffic.

Lists, and the body-vs-header distinction

Lists are freelisted too, but only the header object — not the resizable element array. From listobject.c: PyList_New does _Py_FREELIST_POP(PyListObject, lists) and only calls PyObject_GC_New on a miss; list_dealloc does _Py_FREELIST_FREE(lists, op, PyObject_GC_Del) for exact lists. But before returning the header to the bin, the dealloc path frees the backing ob_item array via free_list_items(...) and sets op->ob_item = NULL. So the free list recycles the small fixed-size PyListObject struct, while the variable-size element buffer always goes back to the allocator. This is the general pattern for variable-length containers: cache the cheap, fixed-size header; never cache the variable body.

The 3.12/3.13 Consolidation

Before this work, every type rolled its own free list as loose static variables or ad-hoc per-interpreter fields, each with its own counter, cap macro, and push/pop code. Issue gh-100240 (“Use a principled, and consistent, implementation of freelists”) records the motivation bluntly: the scattered free lists “take up 3672 bytes of space, instead of the ~200 bytes they should take,” and each had subtly different, independently maintained logic. The fix was to define one _Py_freelist/_Py_freelists struct and one set of _Py_FREELIST_* macros, then migrate every type onto it. This both shrank the state and gave the free-threaded build a single place to flip the storage from per-interpreter to per-thread.

The release archaeology resolves cleanly. The naming/per-thread unification (gh-111968) landed before the 3.13 branch was cut, so 3.13 already used unified freelist names — but at v3.13.0 the storage was still a bag of per-type structs (_Py_list_freelist with a fixed items[PyList_MAXFREELIST] array and an int numfree, _Py_tuple_freelist, _Py_float_freelist, and so on, in Include/internal/pycore_freelist.h at the v3.13.0 tag). The single generic _Py_freelist {void *freelist; Py_ssize_t size;} linked-list struct with the _Py_freelists aggregate is the gh-100240 “Use a consistent implementation for freelists” work (PR #121934, merged 2024-07-22, after the 3.13 branch point of 3.13.0b1) — so the consolidated single-struct shape is a 3.14 feature, not 3.13. The shipped 2-field struct also differs from the 4-field design (head/space/current_capacity/limit_capacity) merely proposed in issue gh-100240: the proposal was simplified during implementation. The 2-field _Py_freelist/_Py_freelists shape is verified identical at the v3.14.5 tag (Include/internal/pycore_freelist.h and pycore_freelist_state.h).

Resolved (2026-06-01)

The single generic _Py_freelist/_Py_freelists struct is a 3.14 feature (gh-100240, PR #121934, merged after the 3.13 branch). At v3.13.0 the freelists were still per-type items[]-array structs; the unified naming (gh-111968) predates the 3.13 branch. The 2-field struct shape is verified at v3.14.5.

Which Types Have Free Lists, and Their Caps

The full set of caps, verified verbatim in pycore_freelist_state.h at v3.14.0:

Free list	Max retained	Notes
floats	Py_floats_MAXFREELIST = 100	exact float only
ints	Py_ints_MAXFREELIST = 100	the medium-int allocation cache — distinct from the small-int interning cache (see below)
tuples[20]	Py_tuple_MAXFREELIST = 2000 per length; PyTuple_MAXSAVESIZE = 20 lengths	array indexed by len-1
lists	Py_lists_MAXFREELIST = 80	header only; ob_item freed
dicts	Py_dicts_MAXFREELIST = 80	the dict object
dictkeys	Py_dictkeys_MAXFREELIST = 80	the separate PyDictKeysObject keys table
slices	Py_slices_MAXFREELIST = 1	only one slice cached
ranges / range_iters	6 / 6
list_iters / tuple_iters	10 / 10
contexts	Py_contexts_MAXFREELIST = 255	contextvars contexts
async_gens / async_gen_asends	80 / 80	async generators and their asend objects
futureiters	Py_futureiters_MAXFREELIST = 255	asyncio future iterators
object_stack_chunks	Py_object_stack_chunks_MAXFREELIST = 4	the GC’s object-marking stack chunks — not interpreter frames
unicode_writers	1	_PyUnicodeWriter scratch
pycfunctionobject / pycmethodobject	16 / 16	built-in function/method wrappers
pymethodobjects	20	bound method objects

Two clarifications that are easy to get wrong. First, the ints free list is not the small-integer cache. CPython interns the small integers (the canonical range is −5 through 256) as permanent singletons that are never deallocated, so they never touch a free list; Py_ints_MAXFREELIST caches the churned, non-interned PyLongObjects of a single machine-word size. Second, object_stack_chunks caches chunks of the garbage collector’s mark stack (the work list it uses while tracing reachable objects) — it has nothing to do with call frames.

There is no PyFrameObject free list in 3.14

The brief asks about a “frame freelist.” Verifying against Python/pystate.c at v3.14.0: there is no dedicated free list for frames in modern CPython. Since the 3.11 “zero-cost” frame redesign, an _PyInterpreterFrame is not an independently heap-allocated object at all — it is carved out of a per-thread data stack built from large _PyStackChunk buffers:

_PyInterpreterFrame *
_PyThreadState_PushFrame(PyThreadState *tstate, size_t size)
{
    if (_PyThreadState_HasStackSpace(tstate, (int)size)) {
        _PyInterpreterFrame *res = (_PyInterpreterFrame *)tstate->datastack_top;
        tstate->datastack_top += size;          /* bump-pointer: just advance the top */
        return res;
    }
    return (_PyInterpreterFrame *)push_chunk(tstate, (int)size);  /* grow: new chunk */
}

Pushing a frame is a pointer bump within the current chunk (datastack_top += size); only when a chunk fills does push_chunk allocate a new _PyStackChunk (via _PyObject_VirtualAlloc) and link it via a previous pointer. _PyThreadState_PopFrame rewinds datastack_top, and when a frame sits at the start of its chunk it frees that chunk with _PyObject_VirtualFree. So frame recycling is achieved by the chunked bump-allocator’s own LIFO reuse, not by a _Py_freelist. This makes the old “frame freelist” mental model obsolete for 3.11+. (A separate PyFrameObject — the Python-visible frame wrapper — is created lazily only when introspection demands it, and it too is not freelisted.)

The dedicated frame free list disappeared in Python 3.11, as part of Mark Shannon’s “Cheaper, lazy Python frames” redesign (bpo-44590). What’s New in Python 3.11 describes the change directly: the work “avoided memory allocation by generously re-using frame space on the C stack” and “streamlined the internal frame struct to contain only essential information,” so that for most user code “no frame objects are created at all.” That C-stack/datastack reuse is exactly the bump-allocated _PyStackChunk mechanism shown above, and it superseded the old per-interpreter frame free list (the one introduced by bpo-40521). The absence of any frame _Py_freelist is verified in Python/pystate.c at v3.14.5.

Resolved (2026-06-01)

The frame free list was eliminated in 3.11 by the “Cheaper, lazy Python frames” work (bpo-44590; What’s New in 3.11), which reuses frame space on the C stack instead of freelisting frames. No frame free list exists at v3.14.5.

How Free-Threading Changes Free Lists

Recapping the accessor split from above: GIL build → per-interpreter (interp->object_state.freelists), free-threaded build → per-thread (_PyThreadStateImpl->freelists). The trade-off is the classic one for thread-local caches. Per-thread free lists eliminate contention on the hottest path in the interpreter — no lock, no atomics, no false sharing between cores on the free-list head. The cost is memory: each thread now holds its own bin, so the worst-case retained-object count multiplies by the thread count (e.g. up to 100 × num_threads floats pinned instead of 100 per interpreter), and an object freed on one thread cannot be reused by another. For the typical free-threaded workload — many cores each running allocation-heavy Python — the contention saving dominates, which is why the design moved this way (per gh-111968, which enumerates float, slice, tuple, list, dict, generator, and PyContext freelists as the ones migrated to per-thread storage).

Because v3.14.0’s _Py_freelists_GET() selects the storage uniformly for all lists in the aggregate (there is no per-type override), the migration is wholesale: any type that goes through _Py_FREELIST_* gets per-thread storage in the free-threaded build.

Uncertain (dated 2026-06-01)

Verify: the worst-case retained-memory multiplier under free-threading is ”≈ MAXFREELIST × num_threads”. Reason: per-thread storage is confirmed in _Py_freelists_GET() at v3.14.5 (the Py_GIL_DISABLED branch returns ((_PyThreadStateImpl*)tstate)->freelists), so the upper bound follows from the cap being per-thread — but this is a derived bound, not a measured one; actual retention depends on how many threads populate each bin and is bounded above by the per-type cap times the live thread count. To resolve: instrument _Py_FREELIST_SIZE across threads under a representative free-threaded workload to measure typical (not worst-case) retention. #uncertain

Failure Modes and Common Misunderstandings

• “Free lists save memory.” They do not — they retain memory. A free list pins up to MAXFREELIST dead objects so they can be reused; it trades a small, bounded memory overhead for allocation speed. If you are chasing high-water-mark memory, free lists are a (small, capped) contributor, not a help.
• Confusing the int free list with the small-int cache. Py_ints_MAXFREELIST is allocation recycling; the −5..256 singletons are interning. Different mechanisms, different files, different lifetimes.
• Expecting id() stability across recycling. Because a fresh object can reuse the exact memory of a just-freed one, two objects that never coexist can share an id(). This is the well-known “id reuse” gotcha, and free lists make it more likely for floats and tuples specifically.
• Subclasses aren’t freelisted. Only exact-type instances hit the free list; class MyFloat(float) instances always go through tp_alloc/tp_free. Micro-benchmarks that subclass to “measure float allocation” measure the wrong path.
• Assuming a frame free list still exists. As shown above, it does not in 3.11+; profiling guides that mention a “frame freelist” are stale.

See Also

• The Memory Allocator Domains — the OBJ-domain allocator the free list short-circuits.
• The pymalloc Allocator — the small-block allocator beneath the free lists.
• CPython Float Internals — the PyFloatObject whose lifecycle the float free list manages.
• CPython Tuple Internals — the length-indexed tuple free list in context.
• Stack Frames and the Frame Stack — the per-thread datastack-chunk allocator that replaced the old frame free list.
• Free-Threaded CPython — why free lists became per-thread.
• Parent: Python Internals MOC §6 Memory Management.