How CPython Reuses Objects with Free Lists

Allocation is not free, even with a good allocator. CPython’s hot paths create and destroy the same kinds of objects over and over – a list while building a comprehension, a tuple for a function call’s argument pack, a dict for a namespace, a float for an arithmetic result. Rather than handing every one of these back to the general allocator and asking for a fresh block next time, CPython keeps small per-type caches called freelists and recycles the recently dead objects directly. This article traces that machinery through the 3.15 source.

The idea in one paragraph

A freelist is an intrusive LIFO stack of dead objects. When an object of a recyclable type dies, CPython tries to push it onto its type’s freelist instead of freeing it. The next time that type is needed, CPython pops a ready-made shell, reinitializes its first word, and skips allocation entirely. The stack is bounded (a few dozen to a few thousand entries), so memory cannot grow without limit, and it is emptied during garbage collection so recycled shells do not keep arenas alive.

The core machinery

Two headers own the whole scheme:

c
// Include/internal/pycore_freelist.h
#define _Py_FREELIST_FREE(NAME, op, freefunc) \
    _PyFreeList_Free(&_Py_freelists_GET()->NAME, _PyObject_CAST(op), \
                     Py_ ## NAME ## _MAXFREELIST, freefunc)

#define _Py_FREELIST_PUSH(NAME, op, limit) \
    _PyFreeList_Push(&_Py_freelists_GET()->NAME, _PyObject_CAST(op), limit)

#define _Py_FREELIST_POP(TYPE, NAME) \
    _Py_CAST(TYPE*, _PyFreeList_Pop(&_Py_freelists_GET()->NAME))

#define _Py_FREELIST_POP_MEM(NAME) \
    _PyFreeList_PopMem(&_Py_freelists_GET()->NAME)

c
// Include/internal/pycore_freelist_state.h
struct _Py_freelist {
    // Entries are linked together using the first word of the object.
    // For PyObjects, this overlaps with ob_refcnt (GIL build) or ob_tid
    // (free-threaded build).
    void *freelist;
    // -1 means the freelist is permanently disabled.
    Py_ssize_t size;
};

The push and pop helpers are tiny and inline:

c
// Include/internal/pycore_freelist.h
static inline int
_PyFreeList_Push(struct _Py_freelist *fl, void *obj, Py_ssize_t maxsize)
{
    if (fl->size < maxsize && fl->size >= 0) {
        FT_ATOMIC_STORE_PTR_RELAXED(*(void **)obj, fl->freelist);
        fl->freelist = obj;
        fl->size++;
        OBJECT_STAT_INC(to_freelist);
        return 1;
    }
    return 0;
}

static inline PyObject *
_PyFreeList_Pop(struct _Py_freelist *fl)
{
    PyObject *op = _PyFreeList_PopNoStats(fl);
    if (op != NULL) {
        OBJECT_STAT_INC(from_freelist);
        _Py_NewReference(op);   // resets refcount / ownership / GC bits
    }
    return op;
}

Three C tricks are already visible:

Intrusive linked list. There are no separate list nodes. While an object sits on a freelist, its first word is overwritten with the next pointer. For a PyObject that word is ob_refcnt (or ob_tid in the free-threaded build), which is dead anyway because the object has been deallocated. When the object is reused, _Py_NewReference reinitializes that word.
LIFO. Recently freed objects are the hottest in cache, so reusing them first is good for locality.
Bounded. size < maxsize is the whole guard. When a freelist is full the push fails and the object is really freed, so a tight loop cannot pin unbounded memory.

_Py_FREELIST_POP_MEM is the variant for plain C structs that are not PyObjects (for example PyDictKeysObject): it pops a block but does not call _Py_NewReference.

What gets recycled, and how much

The limits live in Include/internal/pycore_freelist_state.h:

c
#define PyTuple_MAXSAVESIZE 20
#define Py_tuple_MAXFREELIST 2000
#define Py_lists_MAXFREELIST 80
#define Py_list_iters_MAXFREELIST 10
#define Py_tuple_iters_MAXFREELIST 10
#define Py_dicts_MAXFREELIST 80
#define Py_dictkeys_MAXFREELIST 80
#define Py_floats_MAXFREELIST 100
#define Py_complexes_MAXFREELIST 100
#define Py_ints_MAXFREELIST 100
#define Py_slices_MAXFREELIST 1
#define Py_ranges_MAXFREELIST 6
#define Py_range_iters_MAXFREELIST 6
#define Py_pymethodobjects_MAXFREELIST 20

The container types are where the savings are largest, so they get the biggest limits. Tuples are special: instead of one freelist there are twenty, one for each size from 1 to 20.

list

c
// Objects/listobject.c
PyListObject *op = _Py_FREELIST_POP(PyListObject, lists);
if (op == NULL) {
    op = PyObject_GC_New(PyListObject, &PyList_Type);
    ...
}
...
// dealloc
if (PyList_CheckExact(op)) {
    _Py_FREELIST_FREE(lists, op, PyObject_GC_Del);
}

Only exact list (not subclasses) is recycled, and the items array is freed before the shell is pushed, so a recycled list is empty. Limit: 80.

tuple

c
// Objects/tupleobject.c
Py_ssize_t index = size - 1;
if (index < PyTuple_MAXSAVESIZE) {
    PyTupleObject *op = _Py_FREELIST_POP(PyTupleObject, tuples[index]);
    ...
}

c
// Objects/tupleobject.c
static inline int
maybe_freelist_push(PyTupleObject *op)
{
    if (!Py_IS_TYPE(op, &PyTuple_Type)) {
        return 0;
    }
    Py_ssize_t index = Py_SIZE(op) - 1;
    if (index < PyTuple_MAXSAVESIZE) {
        return _Py_FREELIST_PUSH(tuples[index], op, Py_tuple_MAXFREELIST);
    }
    return 0;
}

Twenty buckets by size, 2000 entries each. The empty tuple is an immortal singleton and is never freelist-recycled. Contents are decref’d before the shell is pushed.

dict

c
// Objects/dictobject.c
PyDictObject *mp = _Py_FREELIST_POP(PyDictObject, dicts);
...
// keys: only minimum-size unicode keys
if (log2_size == PyDict_LOG_MINSIZE && unicode) {
    dk = _Py_FREELIST_POP_MEM(dictkeys);
}

c
// Objects/dictobject.c
if (Py_IS_TYPE(mp, &PyDict_Type)) {
    _Py_FREELIST_FREE(dicts, mp, Py_TYPE(mp)->tp_free);
}
...
if (DK_LOG_SIZE(keys) == PyDict_LOG_MINSIZE &&
    keys->dk_kind == DICT_KEYS_UNICODE) {
    _Py_FREELIST_FREE(dictkeys, keys, PyMem_Free);
}

The dict object freelist holds 80 shells. The keys freelist holds 80, but only for minimum-size Unicode-key tables; larger or shared keys are freed normally. PyFrozenDict is not recycled.

float and int

c
// Objects/floatobject.c
PyFloatObject *op = _Py_FREELIST_POP(PyFloatObject, floats);
if (op == NULL) {
    op = PyObject_Malloc(sizeof(PyFloatObject));
    ...
    _PyObject_Init((PyObject*)op, &PyFloat_Type);
}
op->ob_fval = fval;

c
// Objects/longobject.c
if (ndigits == 1) {
    result = (PyLongObject *)_Py_FREELIST_POP(PyLongObject, ints);
}

c
// Objects/longobject.c
void _PyLong_ExactDealloc(PyObject *self) {
    assert(PyLong_CheckExact(self));
    if (_PyLong_IsSmallInt((PyLongObject *)self)) {
        _Py_SetImmortal(self);
        return;
    }
    if (_PyLong_IsCompact((PyLongObject *)self)) {
        _Py_FREELIST_FREE(ints, self, PyObject_Free);
        return;
    }
    PyObject_Free(self);
}

Floats get 100 slots. Ints get 100, but only for compact, exact, non-small single-digit ints; small ints are immortal and multi-digit ints are freed. The small-int cache is a separate, larger mechanism described in another article.

Frames are the exception

CPython 3.15 does not have a PyFrameObject freelist. frame_dealloc ends with PyObject_GC_Del(f). Instead, interpreter frames are allocated from a per-thread chunked stack, with a single cached chunk reused:

c
// Python/pystate.c
_PyInterpreterFrame *_PyThreadState_PushFrame(PyThreadState *tstate, size_t size) {
    if (_PyThreadState_HasStackSpace(tstate, (int)size)) {
        _PyInterpreterFrame *res = (_PyInterpreterFrame *)tstate->datastack_top;
        tstate->datastack_top += size;
        return res;
    }
    return (_PyInterpreterFrame *)push_chunk(tstate, (int)size);
}

So frames avoid per-object allocation by being slices of a reusable arena, which is a different trick from a freelist but serves the same purpose.

Thread safety

Where the freelist state lives depends on the build:

c
// Include/internal/pycore_freelist.h
static inline struct _Py_freelists *
_Py_freelists_GET(void)
{
#ifdef Py_GIL_DISABLED
    PyThreadState *tstate = _PyThreadState_GET();
    return &((_PyThreadStateImpl*)tstate)->freelists;   // per-thread
#else
    PyInterpreterState *interp = _PyInterpreterState_GET();
    return &interp->object_state.freelists;             // per-interpreter
#endif
}

GIL build: freelists are per-interpreter and protected by the GIL. Plain loads and stores.
Free-threaded build: freelists are per-thread, so no cross-thread sharing and no locks. Object ownership is encoded in ob_tid; _Py_NewReference sets it on reuse. Push uses FT_ATOMIC_STORE_PTR_RELAXED to publish the link.

Clearing differs accordingly: one interpreter freelist in the GIL build, versus walking every thread state in the free-threaded build. Pushes also use the relaxed atomic store in both builds so the link publication is consistent with the free-threaded memory model.

Finalization and garbage collection

c
// Objects/object.c
static void clear_freelist(struct _Py_freelist *freelist, int is_finalization,
                           freefunc dofree) {
    void *ptr;
    while ((ptr = _PyFreeList_PopNoStats(freelist)) != NULL) {
        dofree(ptr);
    }
    assert(freelist->size == 0 || freelist->size == -1);
    if (is_finalization) {
        freelist->size = -1;   // disable
    }
}

Setting size = -1 permanently disables a freelist, which matters during shutdown so a recycled shell is never reused after its type’s deallocator has been torn down.

Objects on freelists are untracked by the GC and empty, so they hold no references. During the highest-generation collection all freelists are cleared (_PyGC_ClearAllFreeLists) so recycled shells do not keep pymalloc arenas, and therefore memory, alive longer than necessary.

Why this is fast

The whole scheme is one idea repeated: reuse the first word of a dead object as the next pointer of an intrusive LIFO stack, bounded by a small per-type limit, and reinitialize the object with _Py_NewReference on reuse. There are no separate list nodes, no hashing, and no locking on the GIL path. For types that are created and destroyed millions of times per second – tuples for calls, floats for arithmetic, ints for indexing – skipping the allocator on most operations is a large, measurable win, and it is the reason CPython’s object creation is as cheap as it is.