Python/freelist.c

cpython 3.14 @ ab2d84fe1023/Python/freelist.c ↗

Free list caches for the most frequently allocated object types: float, tuple (up to eight elements), list, dict entry arrays, and interpreter frames. Each cache is a singly-linked list of pre-allocated, reference-count-zero blocks keyed by size. When the allocator for one of these types needs a block, it pops from the appropriate list instead of calling PyObject_Malloc; when a block's reference count drops to zero, tp_dealloc pushes it back rather than freeing it. The result is that short-lived temporaries, which dominate most Python workloads, never reach the OS allocator.

All lists are stored on _PyFreeListState, a struct embedded in _PyInterpreterState. This makes each interpreter's free lists independent; there is no lock protecting them, and cross-interpreter object sharing is detected and rejected elsewhere. _Py_ClearFreeLists drains all lists at interpreter shutdown and at gc.collect() time to return memory to the OS.

Map

Lines	Symbol	Role	gopy
1-40	includes / freelist_state accessor	Pull in _PyFreeListState from pycore_freelist.h; define the inline _Py_freelists_GET() accessor.	objects/freelist.go:freelistState
40-80	_PyFloat_FromDouble fast path, _PyFloat_ExactDealloc	Pop / push float block; fall through to PyObject_Malloc on miss.	objects/freelist.go:FloatFromDouble
80-130	_PyTuple_FromArray, _PyTuple_MaybeUntrack, tuple_alloc, tuple_free	Per-size tuple free lists (0 to 8 items).	objects/freelist.go:TupleAlloc
130-165	PyList_New fast path, list_dealloc contribution	Single free list for PyListObject headers (not the item array).	objects/freelist.go:ListAlloc
165-200	_PyDictKeys_NewWithValues, dictkeys_dealloc	Free list for PyDictKeysObject / PyDictValues blocks.	objects/freelist.go:DictKeysAlloc
200-230	_PyFrame_Alloc, _PyFrame_ClearLocals contribution	Frame object free list.	objects/freelist.go:FrameAlloc
230-251	_Py_ClearFreeLists	Drain all free lists; called from GC, _Py_ClearStandardStreamEncoding, and interpreter teardown.	objects/freelist.go:ClearFreeLists

Reading

Free list structure (lines 1 to 80)

cpython 3.14 @ ab2d84fe1023/Python/freelist.c#L1-80 ↗

/* pycore_freelist.h */
typedef struct _Py_freelist {
    PyObject *items[_PyFreeList_MAXFREELIST];
    int numfree;
} _Py_freelist;

typedef struct _PyFreeListState {
    _Py_freelist floats;
    _Py_freelist tuples[PyTuple_MAXSAVESIZE];
    _Py_freelist lists;
    _Py_freelist dict_keys;
    _Py_freelist frames;
} _PyFreeListState;

Each _Py_freelist is a fixed-capacity array of pointers and a count. The array size _PyFreeList_MAXFREELIST defaults to 256 for floats and 80 for most others; it is a compile-time constant so bounds checking is a single comparison rather than a heap query. Pointers stored in the array are type-erased PyObject *; the next-pointer for the linked list is physically the object's ob_type field (which is otherwise unused for a dead object). This trick avoids adding a next pointer to every object header while keeping the free list threaded without additional allocation.

The _Py_freelists_GET() inline resolves to &tstate->interp->freelist_state, so all free list operations are pure pointer arithmetic with no locking and no function call overhead after inlining.

_PyFloat_FromDouble fast path (lines 40 to 80)

cpython 3.14 @ ab2d84fe1023/Python/freelist.c#L40-80 ↗

PyObject *
_PyFloat_FromDouble(PyInterpreterState *interp, double fval)
{
    _PyFreeListState *state = _Py_freelists_GET();
    PyFloatObject *op = (PyFloatObject *)state->floats.items[--state->floats.numfree];
    if (state->floats.numfree < 0) {
        /* list was empty */
        state->floats.numfree = 0;
        op = PyObject_Malloc(sizeof(PyFloatObject));
        if (op == NULL) {
            return PyErr_NoMemory();
        }
    }
    _PyObject_Init((PyObject *)op, &PyFloat_Type);
    op->ob_fval = fval;
    return (PyObject *)op;
}

The allocator pre-decrements numfree and reads from the slot. If numfree goes negative the list was empty; the index is reset to zero and PyObject_Malloc is called instead. On the fast path no branch is taken after the pre-decrement: the object is already in cache, and only _PyObject_Init and the ob_fval store remain. The complementary dealloc in float_dealloc checks whether numfree < _PyFreeList_MAXFREELIST before pushing:

static void
float_dealloc(PyObject *op)
{
    _PyFreeListState *state = _Py_freelists_GET();
    if (state->floats.numfree < _PyFreeList_MAXFREELIST) {
        state->floats.items[state->floats.numfree++] = op;
        return;
    }
    PyObject_Free(op);
}

A float that would overflow the cache goes directly to PyObject_Free. The cap keeps memory bounded; in practice benchmarks show that 256 slots cover the steady-state working set of all common numerical workloads.

_Py_ClearFreeLists (lines 230 to 251)

cpython 3.14 @ ab2d84fe1023/Python/freelist.c#L230-251 ↗

void
_Py_ClearFreeLists(_PyFreeListState *state, int is_finalization)
{
    /* floats */
    while (state->floats.numfree > 0) {
        PyFloatObject *op = (PyFloatObject *)
            state->floats.items[--state->floats.numfree];
        PyObject_Free(op);
    }
    /* tuples (per size 0..PyTuple_MAXSAVESIZE-1) */
    for (int i = 0; i < PyTuple_MAXSAVESIZE; i++) {
        while (state->tuples[i].numfree > 0) {
            PyTupleObject *op = (PyTupleObject *)
                state->tuples[i].items[--state->tuples[i].numfree];
            PyObject_GC_Del(op);
        }
    }
    /* lists, dict_keys, frames ... */
    _PyList_ClearFreeList(state, is_finalization);
    _PyDict_ClearFreeList(state, is_finalization);
    _PyFrame_ClearFreeList(state, is_finalization);
}

_Py_ClearFreeLists is called in three situations: by the cyclic garbage collector after a full collection (is_finalization = 0), by _Py_Finalize during interpreter shutdown (is_finalization = 1), and by _testinternalcapi.get_memory_usage in the test suite. For floats and tuples the drain loop is open-coded here because those types use a pure array structure. Lists, dict keys, and frames delegate to their own ClearFreeList helpers because those types have additional bookkeeping (for example, the list header free list is separate from the item-array allocation, and frames carry a separate GC link).

When is_finalization is set, _PyList_ClearFreeList and friends also clear any interned state that would create reference cycles, ensuring a clean shutdown even if the interpreter is re-initialized in the same process.

gopy mirror

objects/freelist.go implements the same structure using Go's sync.Pool for the float and frame lists, since Go's GC moves objects and raw pointer threading through ob_type is not possible. For tuple and list headers, which have known fixed sizes, a channel-based pool of capacity 256 is used instead of sync.Pool to avoid the per-GC-cycle clearing that sync.Pool performs (which would undermine the performance goal).

ClearFreeLists in Go is called from the gc module's collect() function and from interpreter teardown. Because Go's GC reclaims memory independently, clearing the pools is only necessary for the semantic guarantee (that memory is returned before the next collection counts objects) rather than for actual memory pressure.