CPython's enumerate Implementation in C (and zip/reversed)

Python’s enumerate, zip, and reversed are not functions that build lists. They are lazy iterator objects implemented in C. enumerate lives in Objects/enumobject.c alongside reversed; zip lives in Python/bltinmodule.c. All three follow the same broad pattern: a small struct holding iterator state, a tp_iternext that produces one item at a time, and a recycled result container to avoid per-step allocations. This article focuses on enumerate and then sketches zip and reversed.

The enumerate object

c
// Objects/enumobject.c
typedef struct {
    PyObject_HEAD
    Py_ssize_t en_index;           /* current index of enumeration */
    PyObject* en_sit;              /* secondary iterator of enumeration */
    PyObject* en_result;           /* result tuple  */
    PyObject* en_longindex;        /* index for sequences >= PY_SSIZE_T_MAX */
    PyObject* one;                 /* borrowed reference */
} enumobject;

Five fields carry all the state:

en_index is the next index to emit, stored as a C Py_ssize_t for the common case. It is read/written with relaxed atomics (FT_ATOMIC_LOAD_SSIZE_RELAXED / FT_ATOMIC_STORE_SSIZE_RELAXED) so the free-threaded build can share an enumerator across threads safely.
en_sit is the iterator over the underlying iterable. enumerate does not know anything about the iterable beyond this iterator.
en_result is a length-2 tuple reused across calls (see below).
en_longindex is only non-NULL once the counter has overflowed PY_SSIZE_T_MAX; from then on the index is a Python int.
one is a borrowed reference to the integer 1, used to step the long index without reallocating.

The type is GC-tracked (Py_TPFLAGS_HAVE_GC) and enum_traverse visits en_sit, en_result, and en_longindex.

Construction: `enum_new_impl`

c
// Objects/enumobject.c
static PyObject *
enum_new_impl(PyTypeObject *type, PyObject *iterable, PyObject *start)
{
    enumobject *en;

    en = (enumobject *)type->tp_alloc(type, 0);
    if (en == NULL)
        return NULL;
    if (start != NULL) {
        start = PyNumber_Index(start);
        if (start == NULL) { Py_DECREF(en); return NULL; }
        assert(PyLong_Check(start));
        en->en_index = PyLong_AsSsize_t(start);
        if (en->en_index == -1 && PyErr_Occurred()) {
            PyErr_Clear();
            en->en_index = PY_SSIZE_T_MAX;
            en->en_longindex = start;   // keep the Python int
        } else {
            en->en_longindex = NULL;
            Py_DECREF(start);
        }
    } else {
        en->en_index = 0;
        en->en_longindex = NULL;
    }
    en->en_sit = PyObject_GetIter(iterable);
    if (en->en_sit == NULL) { Py_DECREF(en); return NULL; }
    en->en_result = _PyTuple_FromPairSteal(Py_None, Py_None);
    if (en->en_result == NULL) { Py_DECREF(en); return NULL; }
    en->one = _PyLong_GetOne();    /* borrowed reference */
    return (PyObject *)en;
}

Key points:

start is converted with PyNumber_Index, so enumerate(x, start=1.0) is rejected and bool/int subclasses work. The start value is then stored either as a C integer (en_index) or, if it does not fit in Py_ssize_t, as a Python int in en_longindex with en_index set to PY_SSIZE_T_MAX as a sentinel meaning “we are in long mode”.
The underlying iterable is immediately turned into an iterator with PyObject_GetIter, so enumerate never re-iterates the original.
en_result is pre-allocated as a pair of Nones. This tuple will be mutated in place on every next() call.
one is the process-wide singleton 1 (borrowed, never freed by this object).

enumerate also has a fast tp_vectorcall (enumerate_vectorcall) that parses positional/keyword arguments by hand, including the case where the user writes enumerate(start=..., iterable=...) in either order. It delegates to enum_new_impl.

`next()`: the fast path

c
// Objects/enumobject.c
static PyObject *
enum_next(PyObject *op)
{
    enumobject *en = _enumobject_CAST(op);
    PyObject *next_index;
    PyObject *next_item;
    PyObject *result = en->en_result;
    PyObject *it = en->en_sit;
    PyObject *old_index;
    PyObject *old_item;

    next_item = (*Py_TYPE(it)->tp_iternext)(it);
    if (next_item == NULL)
        return NULL;                 // StopIteration propagates

    Py_ssize_t en_index = FT_ATOMIC_LOAD_SSIZE_RELAXED(en->en_index);
    if (en_index == PY_SSIZE_T_MAX)
        return enum_next_long(en, next_item);

    next_index = PyLong_FromSsize_t(en_index);
    if (next_index == NULL) { Py_DECREF(next_item); return NULL; }
    FT_ATOMIC_STORE_SSIZE_RELAXED(en->en_index, en_index + 1);

    if (_PyObject_IsUniquelyReferenced(result)) {
        Py_INCREF(result);
        old_index = PyTuple_GET_ITEM(result, 0);
        old_item  = PyTuple_GET_ITEM(result, 1);
        PyTuple_SET_ITEM(result, 0, next_index);
        PyTuple_SET_ITEM(result, 1, next_item);
        Py_DECREF(old_index);
        Py_DECREF(old_item);
        _PyTuple_Recycle(result);
        return result;
    }
    return _PyTuple_FromPairSteal(next_index, next_item);
}

This is the heart of the implementation. Two optimisations matter:

One allocation per step only for the index. The item comes from the underlying iterator (which may allocate). The result tuple is not allocated fresh each time; it is mutated in place when it is uniquely referenced.
Tuple recycling. _PyObject_IsUniquelyReferenced(result) checks that no other object holds a reference to en_result. In the normal for i, x in enumerate(...) loop the previous yielded tuple has been consumed and dropped, so this is true, and the same tuple storage is reused via PyTuple_SET_ITEM. _PyTuple_Recycle re-tracks it for the GC (a recycled tuple may have been untracked) and resets its cached hash.

If the result tuple is shared (for example someone kept a reference to an earlier pair), enumerate falls back to _PyTuple_FromPairSteal, which allocates a fresh length-2 tuple. Either way ownership of next_index and next_item is transferred into the returned tuple.

The counter is stepped with a relaxed atomic store. In the normal single- threaded case this compiles to a plain store; under free threading it avoids data races on the shared struct.

Huge indices: `enum_next_long`

Once en_index reaches PY_SSIZE_T_MAX the counter switches to Python int arithmetic:

c
// Objects/enumobject.c
static inline PyObject *
increment_longindex_lock_held(enumobject *en)
{
    if (en->en_longindex == NULL) {
        en->en_longindex = PyLong_FromSsize_t(PY_SSIZE_T_MAX);
        if (en->en_longindex == NULL) return NULL;
    }
    PyObject *next_index = en->en_longindex;     // old value, returned
    PyObject *stepped_up = PyNumber_Add(next_index, en->one);
    if (stepped_up == NULL) return NULL;
    en->en_longindex = stepped_up;             // new current
    return next_index;                          // caller owns this ref
}

enum_next_long calls this under a critical section (Py_BEGIN_CRITICAL_SECTION), because the long index is a Python object and the mutation must be atomic with respect to other threads. It then performs the same in-place result-tuple recycling as the fast path. one is the borrowed 1, so PyNumber_Add does not allocate a new small int for the step.

enum_reduce reflects this split: it pickles (type, sit, en_longindex) when in long mode and (type, sit, en_index) otherwise.

GC and deallocation

c
// Objects/enumobject.c
static void enum_dealloc(PyObject *op) {
    enumobject *en = _enumobject_CAST(op);
    PyObject_GC_UnTrack(en);
    Py_XDECREF(en->en_sit);
    Py_XDECREF(en->en_result);
    Py_XDECREF(en->en_longindex);
    Py_TYPE(en)->tp_free(en);
}

tp_clear is NULL because enumobject holds no weak references and the traverse function is enough for the collector; the GC frees the object through PyObject_GC_Del. en->one is borrowed and is not decremented.

`reversed`

reversed is in the same file and is simpler: it does not wrap an iterator, it walks a sequence by index.

c
// Objects/enumobject.c
typedef struct {
    PyObject_HEAD
    Py_ssize_t      index;
    PyObject* seq;
} reversedobject;

Construction (reversed_new_impl) first looks up __reversed__ on the argument; if present it calls that and returns its result (so user-defined reversal wins). Otherwise it requires PySequence_Check, reads PySequence_Size, and stores index = n - 1. The object keeps a strong reference to the sequence.

reversed_next reads the current index atomically; if it is >= 0 it calls PySequence_GetItem(seq, index), decrements the stored index on success, and returns the item. On IndexError/StopIteration it clears the error. When exhausted it sets index = -1 and, in the GIL build, clears seq to drop the reference early. __length_hint__ recomputes the remaining count from the current index and the (possibly changed) sequence size.

`zip`

zip lives in Python/bltinmodule.c and stores its iterators in a tuple:

c
// Python/bltinmodule.c
typedef struct {
    PyObject_HEAD
    Py_ssize_t tuplesize;
    PyObject *ittuple;     /* tuple of iterators */
    PyObject *result;
    int strict;
} zipobject;

Construction (zip_new) turns each argument into an iterator with PyObject_GetIter and stores them in ittuple; it also pre-allocates result as a tuple of None of length tuplesize. strict comes from the keyword argument.

zip_next is the same recycling idea scaled to N:

c
// Python/bltinmodule.c (simplified)
if (_PyObject_IsUniquelyReferenced(result)) {
    Py_INCREF(result);
    for (i = 0; i < tuplesize; i++) {
        it = PyTuple_GET_ITEM(lz->ittuple, i);
        item = (*Py_TYPE(it)->tp_iternext)(it);
        if (item == NULL) { ... handle strict/exhaustion ... }
        olditem = PyTuple_GET_ITEM(result, i);
        PyTuple_SET_ITEM(result, i, item);
        Py_DECREF(olditem);
    }
    _PyTuple_Recycle(result);
} else {
    result = PyTuple_New(tuplesize);
    ...
}

When an iterator is exhausted, zip returns NULL (StopIteration). In strict=True mode it instead raises ValueError if the iterables have different lengths, by draining the remaining iterators to see whether any produces another item. zip_reduce/zip_setstate round-trip the iterator tuple and the strict flag.

Shared design notes

All three are GC objects with tp_traverse over their held references; none implement tp_clear, relying on traversal plus PyObject_GC_Del.
All three reuse a single result tuple (en_result / result) and mutate it with PyTuple_SET_ITEM when uniquely referenced, avoiding an allocation per yielded value. _PyTuple_Recycle keeps the GC tracking correct.
Counter/index state is touched with relaxed atomics so the same object can be driven from multiple threads in the free-threaded build.
enumerate and zip do not materialise sequences; they only advance the iterators they hold. reversed is the exception, because indexing requires the whole sequence.

The enumerate object

Construction: enum_new_impl

next(): the fast path

Huge indices: enum_next_long