CPython's tuple Implementation in C: Immutable, Inline, and Recycled

TL;DR: A CPython tuple stores its items inside the object’s own allocation — no backing array, no indirection. Its length is also its capacity, its hash is cached in ob_hash, and sizes 1..20 are recycled through per-size freelists.

Python’s tuple is an immutable sequence of object pointers. In CPython it’s PyTupleObject in Objects/tupleobject.c. Unlike list, a tuple never over-allocates: its length and its capacity are the same. Let’s trace the representation and the hot paths through the 3.15 source.

The object struct

Every Python object starts with PyObject_VAR_HEAD (ob_refcnt, ob_type, and ob_size). For tuples the payload adds a cached hash and the item vector:

c
// Include/cpython/tupleobject.h
typedef struct {
    PyObject_VAR_HEAD
    /* Cached hash.  Initially set to -1. */
    Py_hash_t ob_hash;
    /* ob_item contains space for 'ob_size' elements.
       Items must normally not be NULL, except during construction when
       the tuple is not yet visible outside the function that builds it. */
    PyObject *ob_item[1];
} PyTupleObject;

The trailing ob_item[1] is the classic C “struct hack”: the real object is allocated with ob_size slots, and ob_item is treated as a flexible array. The type object declares this with tp_basicsize and tp_itemsize:

c
// Objects/tupleobject.c
PyTypeObject PyTuple_Type = {
    ...
    sizeof(PyTupleObject) - sizeof(PyObject *),   /* tp_basicsize */
    sizeof(PyObject *),                            /* tp_itemsize */
    ...
};

tp_basicsize is the size of the header minus one slot, and tp_itemsize is the size of one slot, so PyObject_GC_NewVar(..., size) allocates exactly sizeof(PyTupleObject) - sizeof(PyObject *) + size * sizeof(PyObject *) bytes.

The items therefore live in the same allocation as the object header – no separate backing array and no indirection.

Memory layout

text

+---------------------------+  <- PyObject_GC_NewVar result
| ob_refcnt                 |
+---------------------------+
| *ob_type  (&PyTuple_Type) |
+---------------------------+
| ob_size   (len)           |
+---------------------------+
| ob_hash   (cached hash)   |
+---------------------------+
| ob_item[0] (PyObject *)   |
| ob_item[1] (PyObject *)   |
| ...                       |
| ob_item[ob_size - 1]      |
+---------------------------+

Because there’s no allocated field, a tuple’s memory is exactly its length. Shrinking or growing means reallocating the whole object (see _PyTuple_Resize).

The empty-tuple singleton

The empty tuple is a statically allocated singleton, not GC-tracked, and its hash is precomputed at compile time:

c
// Include/internal/pycore_runtime_structs.h
struct {
    _PyGC_Head_UNUSED _tuple_empty_gc_not_used;
    PyTupleObject tuple_empty;
    ...
} singletons;

// Include/internal/pycore_runtime_init.h
.tuple_empty = {
    .ob_base = _PyVarObject_HEAD_INIT(&PyTuple_Type, 0),
    .ob_hash = _PyTuple_HASH_EMPTY,
},

Every call asking for an empty tuple returns the same object:

c
// Objects/tupleobject.c
static inline PyObject *
tuple_get_empty(void)
{
    return (PyObject *)&_Py_SINGLETON(tuple_empty);
}

PyObject *
PyTuple_New(Py_ssize_t size)
{
    PyTupleObject *op;
    if (size == 0) {
        return tuple_get_empty();
    }
    ...
}

tuple_dealloc guards the singleton against being freed:

c
// Objects/tupleobject.c
if (Py_SIZE(op) == 0) {
    if (op == &_Py_SINGLETON(tuple_empty)) {
#ifdef Py_DEBUG
        _Py_FatalRefcountError("deallocating the empty tuple singleton");
#else
        return;
#endif
    }
}

Subclasses don’t share the singleton; tuple_subtype_new may allocate its own empty instance.

Free list (tuple reuse)

Exact PyTupleObjects of sizes 1..20 are recycled through a per-size free list, each holding up to 2000 entries:

c
// Include/internal/pycore_freelist_state.h
#  define PyTuple_MAXSAVESIZE 20     // Largest tuple to save on freelist
#  define Py_tuple_MAXFREELIST 2000  // Maximum number of tuples of each size

tuple_alloc pops from the matching bucket before allocating:

c
// Objects/tupleobject.c
static PyTupleObject *
tuple_alloc(Py_ssize_t size)
{
    if (size < 0) { ... }
    assert(size != 0);    // The empty tuple is statically allocated.
    Py_ssize_t index = size - 1;
    if (index < PyTuple_MAXSAVESIZE) {
        PyTupleObject *op = _Py_FREELIST_POP(PyTupleObject, tuples[index]);
        if (op != NULL) {
            _PyTuple_RESET_HASH_CACHE(op);
            return op;
        }
    }
    ...
    PyTupleObject *result = PyObject_GC_NewVar(PyTupleObject, &PyTuple_Type, size);
    if (result != NULL) {
        _PyTuple_RESET_HASH_CACHE(result);
    }
    return result;
}

On deallocation, maybe_freelist_push returns the object to its bucket instead of freeing it:

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

Because a recycled object may have been tracked by the GC before, _PyTuple_Recycle re-tracks it and resets the hash cache when it’s reused:

c
// Include/internal/pycore_tuple.h
static inline void
_PyTuple_Recycle(PyObject *op)
{
    _PyTuple_RESET_HASH_CACHE(op);
    if (!_PyObject_GC_IS_TRACKED(op)) {
        _PyObject_GC_TRACK(op);
    }
}

Creation

PyTuple_New allocates and zeroes the slots, then tracks the object:

c
// Objects/tupleobject.c
PyObject *
PyTuple_New(Py_ssize_t size)
{
    PyTupleObject *op;
    if (size == 0) {
        return tuple_get_empty();
    }
    op = tuple_alloc(size);
    if (op == NULL) {
        return NULL;
    }
    for (Py_ssize_t i = 0; i < size; i++) {
        op->ob_item[i] = NULL;
    }
    _PyObject_GC_TRACK(op);
    return (PyObject *) op;
}

PyTuple_Pack builds a tuple from varargs and only enables GC tracking if at least one item may itself be tracked:

c
// Objects/tupleobject.c
PyObject *
PyTuple_Pack(Py_ssize_t n, ...)
{
    ...
    PyTupleObject *result = tuple_alloc(n);
    ...
    for (i = 0; i < n; i++) {
        o = va_arg(vargs, PyObject *);
        if (!track && maybe_tracked(o)) {
            track = true;
        }
        items[i] = Py_NewRef(o);
    }
    if (track) {
        _PyObject_GC_TRACK(result);
    }
    return (PyObject *)result;
}

maybe_tracked is a conservative check: any GC-capable type makes the tuple tracked. _PyTuple_MaybeUntrack later untracks a tuple once all of its items are non-GC objects, which keeps short-lived tuples of plain values off the collector’s radar:

c
// Objects/tupleobject.c
void
_PyTuple_MaybeUntrack(PyObject *op)
{
    if (!PyTuple_CheckExact(op) || !_PyObject_GC_IS_TRACKED(op))
        return;
    ...
    for (i = 0; i < n; i++) {
        PyObject *elt = PyTuple_GET_ITEM(t, i);
        if (!elt || _PyObject_GC_MAY_BE_TRACKED(elt))
            return;   // still potentially cyclic
    }
    _PyObject_GC_UNTRACK(op);
}

PySequence_Tuple special-cases exact tuples (returns the same object) and exact lists (PyList_AsTuple), then falls back to iterating, buffering the first 8 items on the stack and spilling into a list.

tuple.__new__ returns the empty singleton for no argument, and otherwise delegates to PySequence_Tuple. For a tuple argument this returns the same object – tuples are immutable, so sharing is safe.

Hashing

The hash is computed lazily and cached in ob_hash. -1 is the “not yet computed” sentinel, so a real hash of -1 is remapped to 1546275796. The algorithm is a single-accumulator simplification of xxHash:

c
// Objects/tupleobject.c
static Py_hash_t
tuple_hash(PyObject *op)
{
    PyTupleObject *v = _PyTuple_CAST(op);

    Py_uhash_t acc = FT_ATOMIC_LOAD_SSIZE_RELAXED(v->ob_hash);
    if (acc != (Py_uhash_t)-1) {
        return acc;          // cached
    }

    Py_ssize_t len = Py_SIZE(v);
    PyObject **item = v->ob_item;
    acc = _PyTuple_HASH_XXPRIME_5;
    for (Py_ssize_t i = 0; i < len; i++) {
        Py_uhash_t lane = PyObject_Hash(item[i]);
        if (lane == (Py_uhash_t)-1) {
            return -1;       // propagate error
        }
        acc += lane * _PyTuple_HASH_XXPRIME_2;
        acc = _PyTuple_HASH_XXROTATE(acc);
        acc *= _PyTuple_HASH_XXPRIME_1;
    }

    /* Add input length, mangled to keep the historical value of hash(()). */
    acc += len ^ (_PyTuple_HASH_XXPRIME_5 ^ 3527539UL);

    if (acc == (Py_uhash_t)-1) {
        acc = 1546275796;
    }

    FT_ATOMIC_STORE_SSIZE_RELAXED(v->ob_hash, acc);
    return acc;
}

The cache is reset to -1 whenever a tuple is recycled (_PyTuple_RESET_HASH_CACHE), and tuple_richcompare relies on immutability to reuse vlen/wlen across comparison calls.

Immutability

Immutability is enforced at the type level: tp_as_sequence has no sq_ass_item or sq_ass_slice slots, so tuple[i] = x raises TypeError.

The only mutation paths are internal, and they require a uniquely referenced, exact PyTuple_Type instance:

PyTuple_SetItem stores a pointer without increfing the new item (but decrefing the replaced one), and only succeeds when _PyObject_IsUniquelyReferenced(op) holds:

c
// Objects/tupleobject.c
int
PyTuple_SetItem(PyObject *op, Py_ssize_t i, PyObject *newitem)
{
    ...
    if (!PyTuple_Check(op) || !_PyObject_IsUniquelyReferenced(op)) {
        Py_XDECREF(newitem);
        PyErr_BadInternalCall();
        return -1;
    }
    ...
    p = ((PyTupleObject *)op) -> ob_item + i;
    Py_XSETREF(*p, newitem);
    return 0;
}

_PyTuple_Resize can grow or shrink a uniquely referenced exact tuple by reallocating the object in place. It decrefs deleted items on shrink and zeroes new slots on grow; the empty tuple is never resized in place (it’s the singleton):

c
// Objects/tupleobject.c
int
_PyTuple_Resize(PyObject **pv, Py_ssize_t newsize)
{
    ...
    if (newsize == 0) {
        Py_DECREF(v);
        *pv = tuple_get_empty();
        return 0;
    }
    if (oldsize == 0) {
        /* The empty tuple is statically allocated so we never
           resize it in-place. */
        Py_DECREF(v);
        *pv = PyTuple_New(newsize);
        return *pv == NULL ? -1 : 0;
    }
    ...
    sv = PyObject_GC_Resize(PyTupleObject, v, newsize);
    ...
}

Because tuples are immutable, operations like slicing, concatenation, and repetition can share or reuse objects: a full slice of an exact tuple returns the same object, and tuple * 1 / tuple + () return the original.

The real win: immutability is what lets CPython hand out the same tuple object in a dozen places instead of copying it. tuple(a) is a is True for a tuple.

Key takeaways

tuple is a PyObject_VAR_HEAD plus a cached ob_hash and an embedded ob_item array; ob_size is both the length and the capacity.
Items are stored in the same allocation as the header (flexible array via tp_basicsize/tp_itemsize); there’s no separate buffer.
The empty tuple is a statically allocated, non-GC singleton with a precomputed hash.
Exact tuples of sizes 1..20 are recycled through per-size freelists of up to 2000 entries; recycled objects are re-tracked and have their hash reset.
GC tracking is conservative: a tuple is only tracked if at least one item may be a GC object, and it can be untracked later via _PyTuple_MaybeUntrack.
The hash is a single-accumulator xxHash variant, computed once and cached (with -1 remapped to avoid clashing with the sentinel).
Immutability is enforced by the type (no sq_ass_item); internal mutation (PyTuple_SetItem, _PyTuple_Resize) is allowed only for uniquely referenced exact tuples.