vault

CPython Tuple Internals

12 min read

CPython Tuple Internals

A CPython tuple is an immutable fixed-length sequence whose elements are stored inline, in the same memory block as the object header. Unlike a list — which is a header plus a separately allocated pointer array (two allocations) — a tuple is a single allocation: the PyObject* slots live in a flexible array member (ob_item) at the tail of the PyTupleObject struct. Immutability has consequences that ripple through the whole language: tuples are hashable (so they can be dict keys and set members), they are safely shareable without defensive copies, the empty tuple is a process-wide singleton, per-size free lists recycle dead tuples, and a tuple literal of constants like (1, 2, 3) is folded into a single constant at compile time. (Verified against CPython 3.14: Objects/tupleobject.c, Include/cpython/tupleobject.h, and behavioral disassembly on Python 3.14.5.)

Mental Model

The defining difference from a list is layout. A list points out to its element array; a tuple holds its element array within itself. Picture a tuple as one solid block on the heap: header fields first, then the cached hash, then the PyObject* slots packed immediately after — all reachable through a single pointer and freed in a single deallocation.

graph TB
    subgraph Tuple["PyTupleObject — ONE allocation"]
        T1["ob_refcnt"]
        T2["ob_type → PyTuple_Type"]
        T3["ob_size = 3"]
        T4["ob_hash (cached, init -1)"]
        T5["ob_item[0] ●──→ int 1"]
        T6["ob_item[1] ●──→ int 2"]
        T7["ob_item[2] ●──→ int 3"]
    end
    subgraph List["PyListObject — TWO allocations (contrast)"]
        L1["header + ob_item ptr ──┐"]
        L2["[separate array] [a][b][c]"]
        L1 --> L2
    end

Diagram: a 3-element tuple (left) is one contiguous block — header, cached hash, then the three pointer slots inline. A list (right) is a header that points out to a separate array. The insight: a tuple costs one allocation and one cache-friendly block, but its size is fixed at birth because the slots are part of the object; a list costs two allocations but can grow because its array is external.

The PyTupleObject Struct

From 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;

Field by field:

  • PyObject_VAR_HEAD — the variable-object header: reference count, type pointer (&PyTuple_Type), and ob_size, which for a tuple is its fixed length.
  • ob_hash — a cached hash value, initialized to -1 meaning “not yet computed.” Caching the hash in the struct is what makes a tuple cheap to use as a dict key after first hashing (see below). Its placement in the struct is a 3.14-relevant detail: the hash is stored on every tuple, not computed afresh on each lookup.
  • PyObject *ob_item[1] — the flexible array member. Declared as length 1 in C, but the object is allocated with enough trailing space for ob_size pointers, so ob_item[0..ob_size-1] are all valid. This is the inline storage: tuple[i] is ob_item[i], and those slots are part of the tuple object itself. The accessor macro is PyTuple_GET_ITEM(op, i), expanding to _PyTuple_CAST(op)->ob_item[(i)] — a raw, unchecked array index with no bounds check or refcount change, used on hot paths inside the interpreter.

The single-allocation layout is the direct consequence of immutability: because a tuple can never change length, its element array never needs to be reallocated, so there is no reason to keep it separate. CPython exploits that to fuse header and array into one block — fewer allocations, better locality, and one fewer pointer indirection per element access than a list.

Allocation: One Block, via PyObject_GC_NewVar

New tuples are built in tuple_alloc in Objects/tupleobject.c:

static PyTupleObject *
tuple_alloc(Py_ssize_t size)
{
    /* ... size checks ... */
    assert(size != 0);
    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;
        }
    }
    /* overflow check ... */
    PyTupleObject *result = PyObject_GC_NewVar(PyTupleObject, &PyTuple_Type, size);
    if (result != NULL) {
        _PyTuple_RESET_HASH_CACHE(result);
    }
    return result;
}
  • For sizes within the free-list range, it first tries to reuse a dead tuple of exactly the right size (see free lists below), resetting its cached hash to -1.
  • Otherwise it calls PyObject_GC_NewVar(PyTupleObject, &PyTuple_Type, size). The NewVar allocator computes sizeof(PyTupleObject) + (size - 1) * sizeof(PyObject*) — the base struct plus enough trailing room for all size inline slots — and allocates that as one block. This is the single-allocation property in code: the slots are part of the same malloc as the header. (Contrast: a list does PyObject_GC_New for the header and a separate PyMem_Malloc for ob_item.)
  • _PyTuple_RESET_HASH_CACHE sets ob_hash back to -1 so a recycled tuple does not return a stale hash.

Immutability and Its Consequences

A tuple has no methods that mutate it — no append, no item assignment. The C type simply does not implement sq_ass_item for arbitrary writes after construction. From this single fact, several language-level guarantees follow.

Hashability. An object is hashable if it has a stable __hash__ over its lifetime. A mutable container cannot offer that — if its contents changed, its hash would change and it would be lost in a hash table. A tuple’s contents are fixed, so its hash is stable provided its elements are themselves hashable. The hash is computed lazily by tuple_hash and cached in ob_hash:

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)          /* already cached */
        return acc;
    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)     /* element unhashable */
            return -1;
        acc += lane * _PyTuple_HASH_XXPRIME_2;
        acc = _PyTuple_HASH_XXROTATE(acc);
        acc *= _PyTuple_HASH_XXPRIME_1;
    }
    acc += len ^ (_PyTuple_HASH_XXPRIME_5 ^ 3527539UL);
    if (acc == (Py_uhash_t)-1)          /* avoid the sentinel */
        acc = 1546275796;
    FT_ATOMIC_STORE_SSIZE_RELAXED(v->ob_hash, acc);
    return acc;
}
  • The first lines return the cached ob_hash if it is not the -1 “uncomputed” sentinel — so a tuple is hashed at most once and is thereafter free to look up.
  • The loop mixes each element’s own hash (PyObject_Hash(item[i])) into an accumulator using the xxHash prime/rotate scheme (_PyTuple_HASH_XXPRIME_*, _PyTuple_HASH_XXROTATE). Because element hashes are combined, a tuple containing an unhashable element (e.g. a list) returns -1, which propagates a TypeError — that is precisely why {(1, [2])} raises unhashable type: 'list'. Immutability of the tuple is necessary but not sufficient: every element must also be hashable.
  • The final guard rewrites a result of -1 (the error/uncomputed sentinel) to a fixed non--1 value so a legitimate hash can never collide with the sentinel.

Use as a dict key / set member. Because they hash stably, tuples of hashable elements work as dict keys and set members — the canonical reason to reach for a tuple over a list. d[(x, y)] = ... is idiomatic; d[[x, y]] is a TypeError.

Shareability without copies. Since no one can mutate a tuple, the interpreter and library code can hand the same tuple to many holders without defensive copying. Default argument tuples, the co_consts of a code object, and *args are all tuples for exactly this reason.

Per-Size Free Lists

Tuples are created and discarded constantly (every function call packs *args; every multiple-return builds one), so CPython keeps free lists segregated by size. The constants are in 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 to save

and the per-size array of free lists is declared in the shared free-list state struct:

struct _Py_freelists {
    /* ... */
    struct _Py_freelist tuples[PyTuple_MAXSAVESIZE];
    struct _Py_freelist lists;
    /* ... */
};

So there are 20 independent free lists — one for each tuple length from 1 up to 20 — and each can retain up to 2000 dead tuples. Why segregate by size? Because tuple storage is inline and fixed: a recycled length-3 tuple has room for exactly 3 inline slots and cannot serve a request for length 5. A list free list can be a single pool (it only recycles the fixed-size header), but a tuple free list must bucket by size to match inline capacity. Allocation indexes the array by size - 1:

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;
}

On deallocation a tuple of size ≤ 20 is pushed onto tuples[size-1] (until that bucket holds 2000); a tuple larger than 20, or a subclass instance (Py_IS_TYPE guards against subclasses), is freed normally. On allocation tuple_alloc pops from the same bucket. The net effect: in tight loops the same memory blocks are reused for new tuples of the same shape, sidestepping the allocator almost entirely.

In 3.14 these per-size free lists live in the per-interpreter / per-thread _Py_freelists state (reached via _Py_freelists_GET()), not in old global C arrays — so sub-interpreters and free-threaded threads each get their own, avoiding contention.

The Empty-Tuple Singleton

The empty tuple () is special-cased to a single, statically allocated, immortal object — there is only ever one of it per interpreter. tuple_alloc and the public constructors short-circuit size 0:

static inline PyObject *
tuple_get_empty(void) {
    return (PyObject *)&_Py_SINGLETON(tuple_empty);
}

and deallocation explicitly refuses to free it:

if (Py_SIZE(op) == 0) {
    /* The empty tuple is statically allocated. */
    if (op == &_Py_SINGLETON(tuple_empty)) {
#ifdef Py_DEBUG
        _Py_FatalRefcountError("deallocating the empty tuple singleton");
#endif
    }
    /* ... */
}

This is why () is () is True and () is tuple() is True — every empty tuple is the same object. It is one of CPython’s interned/immortal singletons (see Immortal Objects for the PEP 683 refcount-saturation mechanism that keeps such objects alive without refcount churn). A 0-element tuple has no inline slots to allocate, so making it a shared constant costs nothing and saves an allocation on the extremely common “no result / empty args” path.

The singleton is genuinely immortal in the PEP 683 sense, not merely statically allocated with ordinary refcounting. It is initialized once in the runtime-init table (pycore_runtime_init.h at v3.14.5) as .tuple_empty = { .ob_base = _PyVarObject_HEAD_INIT(&PyTuple_Type, 0), .ob_hash = _PyTuple_HASH_EMPTY }, and _PyVarObject_HEAD_INIT stamps the refcount with the immortal initial value rather than 1. This is directly observable live on CPython 3.14.5: sys.getrefcount(()) returns 3221225472, i.e. 0xC0000000 == 3 << 30 — the saturated immortal refcount, not a small mutable count. Because the refcount is pinned, the empty tuple is never incref-ed or decref-ed during normal operation; the Py_DEBUG-only _Py_FatalRefcountError guard above exists purely to catch a buggy build that somehow tries to deallocate it.

PyTuple_Pack — the C-Level Builder

PyTuple_Pack(n, a, b, c, ...) is the C API for “make a tuple from these n objects,” used pervasively inside the interpreter:

PyObject *
PyTuple_Pack(Py_ssize_t n, ...)
{
    /* ... */
    if (n == 0) return tuple_get_empty();
    va_start(vargs, n);
    PyTupleObject *result = tuple_alloc(n);
    /* ... */
    items = result->ob_item;
    for (i = 0; i < n; i++) {
        o = va_arg(vargs, PyObject *);
        if (!track && maybe_tracked(o)) track = true;
        items[i] = Py_NewRef(o);
    }
    va_end(vargs);
    if (track) _PyObject_GC_TRACK(result);
    return (PyObject *)result;
}
  • n == 0 returns the shared empty singleton — no allocation.
  • tuple_alloc(n) gets a single block (freelist or fresh).
  • The loop stores each argument into the inline ob_item[i] with Py_NewRef(o) — the tuple takes a new reference to each element (it now co-owns them).
  • The track/_PyObject_GC_TRACK logic only registers the tuple with the cyclic garbage collector if at least one element is itself GC-tracked (a container). A tuple of only atomic objects (ints, strings) is never tracked, because it cannot participate in a reference cycle — a small but real GC optimization.

Why (1, 2, 3) Is Folded at Compile Time

A tuple literal whose elements are all constants is computed once, at compile time, and embedded as a single constant in the bytecode — it is never built at run time. This is verifiable by disassembly on Python 3.14.5:

>>> import dis
>>> dis.dis(compile('(1,2,3)', '<eval>', 'eval'))
  1   LOAD_CONST   1 ((1, 2, 3))     # one ready-made constant tuple
      RETURN_VALUE
>>> dis.dis(compile('(1,2,x)', '<eval>', 'eval'))
  1   LOAD_SMALL_INT 1
      LOAD_SMALL_INT 2
      LOAD_NAME      0 (x)           # x is not a constant
      BUILD_TUPLE    3              # so the tuple is built at run time
      RETURN_VALUE

The first case yields a single LOAD_CONST (1, 2, 3) — the tuple object already exists in the code object’s constant pool. The second, because x is a name resolved at run time, emits three loads and a BUILD_TUPLE 3 opcode that constructs the tuple each time the line executes.

The optimization lives in the bytecode optimizer, fold_tuple_of_constants in Python/flowgraph.c. Its header comment states the rewrite directly: “Replace LOAD_CONST c1, LOAD_CONST c2 ... LOAD_CONST cn, BUILD_TUPLE n” with a single load of the pre-built constant tuple. It is invoked from the optimizer’s BUILD_TUPLE case: when the optimizer sees a BUILD_TUPLE preceded entirely by constant loads, it builds the tuple right there in C (PyTuple_SET_ITEM into a fresh PyTuple_New), interns it into the constants table, and replaces the whole sequence with one LOAD_CONST. Immutability is what makes this safe: a folded constant tuple is shared across every execution of the line, and because no one can mutate it, sharing is invisible — you can never observe the difference between “built fresh each time” and “the same constant reused.”

See Also

Graph View

Backlinks