Opensource internals

CPython's Iterator Implementation in C

8 min read Jay Hubbert

The whole iterator protocol is two function pointers: tp_iter and tp_iternext. Here's how CPython wires them, and why built-in iterators skip Python dispatch entirely.

TL;DR: The entire iterator protocol is two slots in the type object: tp_iter and tp_iternext. Built-in iterators fill them with plain C functions, so for x in my_list never touches Python-level __next__ dispatch.

Python’s iterator protocol is tiny: an iterable has __iter__, an iterator has __next__. In CPython those two ideas are encoded directly in the type object as function pointers, tp_iter and tp_iternext, and every concrete iterator type fills them in. This article traces the protocol and the main iterator implementations through the 3.15 source.

The C-level protocol

A type is iterable when its tp_iter slot is non-NULL (or it is a sequence, see below). A type is an iterator when its tp_iternext slot is non-NULL and not _PyObject_NextNotImplemented:

c 
// Objects/abstract.c
int PyIter_Check(PyObject *obj) {
    PyTypeObject *tp = Py_TYPE(obj);
    return (tp->tp_iternext != NULL &&
            tp->tp_iternext != &_PyObject_NextNotImplemented);
}

PyObject_GetIter is the C entry point behind iter(obj):

c 
// Objects/abstract.c
PyObject *PyObject_GetIter(PyObject *o) {
    PyTypeObject *t = Py_TYPE(o);
    getiterfunc f = t->tp_iter;
    if (f == NULL) {
        if (PySequence_Check(o))
            return PySeqIter_New(o);   // fallback for old-style sequences
        return type_error("'%.200s' object is not iterable", o);
    }
    PyObject *res = (*f)(o);
    if (res != NULL && !PyIter_Check(res)) {
        PyErr_Format(PyExc_TypeError,
                     "%T.__iter__() must return an iterator, not %T",
                     o, res);
        Py_SETREF(res, NULL);
    }
    return res;
}

Two consequences matter: a sequence without tp_iter still gets a generic sequence iterator, and __iter__’s return value is validated to actually be an iterator.

Consumption goes through tp_iternext directly:

c 
// Objects/abstract.c
static int iternext(PyObject *iter, PyObject **item) {
    iternextfunc tp_iternext = Py_TYPE(iter)->tp_iternext;
    if ((*item = tp_iternext(iter))) {
        return 1;            // got an item
    }
    PyThreadState *tstate = _PyThreadState_GET();
    if (!_PyErr_Occurred(tstate)) {
        return 0;            // exhausted, no exception
    }
    if (_PyErr_ExceptionMatches(tstate, PyExc_StopIteration)) {
        _PyErr_Clear(tstate);
        return 0;            // exhausted, StopIteration cleared
    }
    return -1;               // real error
}

PyObject *PyIter_Next(PyObject *iter) {
    PyObject *item;
    (void)iternext(iter, &item);
    return item;
}

So tp_iternext returning NULL means “exhausted or error”; a raised StopIteration is swallowed and turned into a clean end. This is why for loops terminate without leaking StopIteration.

Here’s the thing: StopIteration is an implementation detail of the protocol, not something your loop should ever see. The C layer eats it.

The trivial “I am my own iterator” slot is PyObject_SelfIter, used by every iterator type for tp_iter:

c 
// Objects/object.c
PyObject *PyObject_SelfIter(PyObject *obj) {
    return Py_NewRef(obj);
}

__iter__ / __next__ slot wrappers

For Python classes, __iter__ and __next__ are not function pointers in the type struct by default; they are wired in by the slot machinery in Objects/typeobject.c:

c 
// Objects/typeobject.c
static PyObject *slot_tp_iter(PyObject *self) {
    int attr_is_none = 0;
    PyObject *res = maybe_call_special_no_args(self, &_Py_ID(__iter__),
                                               &attr_is_none);
    if (res != NULL) return res;
    else if (PyErr_Occurred()) return NULL;
    else if (attr_is_none || !has_dunder_getitem(self)) {
        PyErr_Format(PyExc_TypeError,
            "'%.200s' object is not iterable", Py_TYPE(self)->tp_name);
        return NULL;
    }
    return PySeqIter_New(self);   // fallback: sequence protocol
}

static PyObject *slot_tp_iternext(PyObject *self) {
    PyObject *stack[1] = {self};
    return vectorcall_method(&_Py_ID(__next__), stack, 1);
}

So a class that defines __getitem__ but not __iter__ still becomes iterable, via PySeqIter_New. A class that defines __iter__ returning self becomes an iterator. The slot is only installed when the dunder exists, which is why PyIter_Check also rejects _PyObject_NextNotImplemented (a sentinel used when __next__ is removed at runtime).

Objects/iterobject.c

This file holds two generic iterator types.

Sequence iterator (iterator)

PySeqIter_New wraps any sequence:

c 
// Objects/iterobject.c
typedef struct {
    PyObject_HEAD
    Py_ssize_t it_index;
    PyObject *it_seq;   /* NULL when exhausted */
} seqiterobject;

PyObject *PySeqIter_New(PyObject *seq) {
    if (!PySequence_Check(seq)) {
        PyErr_BadInternalCall();
        return NULL;
    }
    seqiterobject *it = PyObject_GC_New(seqiterobject, &PySeqIter_Type);
    it->it_index = 0;
    it->it_seq = Py_NewRef(seq);
    _PyObject_GC_TRACK(it);
    return (PyObject *)it;
}

Its tp_iternext fetches by index and converts IndexError into exhaustion:

c 
// Objects/iterobject.c
static PyObject *iter_iternext(PyObject *iterator) {
    seqiterobject *it = (seqiterobject *)iterator;
    PyObject *seq = it->it_seq;
    if (seq == NULL) return NULL;
    if (it->it_index == PY_SSIZE_T_MAX) { ... OverflowError ... }

    PyObject *result = PySequence_GetItem(seq, it->it_index);
    if (result != NULL) {
        it->it_index++;
        return result;
    }
    if (PyErr_ExceptionMatches(PyExc_IndexError) ||
        PyErr_ExceptionMatches(PyExc_StopIteration)) {
        PyErr_Clear();
        it->it_seq = NULL;
        Py_DECREF(seq);
    }
    return NULL;
}

It also implements __length_hint__, __reduce__ and __setstate__, so generic iterators support len() estimates and pickling.

Callable iterator (callable_iterator)

iter(callable, sentinel) builds a calliterobject:

c 
// Objects/iterobject.c
typedef struct {
    PyObject_HEAD
    PyObject *it_callable;  /* NULL when exhausted */
    PyObject *it_sentinel;  /* NULL when exhausted */
} calliterobject;

static PyObject *calliter_iternext(PyObject *op) {
    calliterobject *it = (calliterobject *)op;
    if (it->it_callable == NULL) return NULL;

    PyObject *result = _PyObject_CallNoArgs(it->it_callable);
    if (result != NULL && it->it_sentinel != NULL) {
        int ok = PyObject_RichCompareBool(it->it_sentinel, result, Py_EQ);
        if (ok == 0) return result;          // not equal: yield
        if (ok > 0) {                        // equal: stop
            Py_CLEAR(it->it_callable);
            Py_CLEAR(it->it_sentinel);
        }
    }
    else if (PyErr_ExceptionMatches(PyExc_StopIteration)) {
        PyErr_Clear();
        Py_CLEAR(it->it_callable);
        Py_CLEAR(it->it_sentinel);
    }
    Py_XDECREF(result);
    return NULL;
}

The callable is invoked with no arguments each step; equality with the sentinel (or a StopIteration from the callable) ends iteration.

Specialized sequence iterators

Lists and tuples do not use the generic iterator; they have their own types (list_iterator, tuple_iterator) that avoid per-step PySequence_GetItem overhead and support freelists.

list_iterator

c 
// Include/internal/pycore_list.h
typedef struct {
    PyObject_HEAD
    Py_ssize_t it_index;
    PyListObject *it_seq;   /* Set to NULL when iterator is exhausted */
} _PyListIterObject;

Construction pops from a per-type freelist:

c 
// Objects/listobject.c
static PyObject *list_iter(PyObject *seq) {
    _PyListIterObject *it = _Py_FREELIST_POP(_PyListIterObject, list_iters);
    if (it == NULL) {
        it = PyObject_GC_New(_PyListIterObject, &PyListIter_Type);
    }
    it->it_index = 0;
    it->it_seq = (PyListObject *)Py_NewRef(seq);
    _PyObject_GC_TRACK(it);
    return (PyObject *)it;
}

The hot path reads the index atomically and fetches a borrowed+newref item directly from the list’s array:

c 
// Objects/listobject.c
static PyObject *listiter_next(PyObject *self) {
    _PyListIterObject *it = (_PyListIterObject *)self;
    Py_ssize_t index = FT_ATOMIC_LOAD_SSIZE_RELAXED(it->it_index);
    if (index < 0) return NULL;

    PyObject *item = list_get_item_ref(it->it_seq, index);
    if (item == NULL) {                  // out of bounds
        FT_ATOMIC_STORE_SSIZE_RELAXED(it->it_index, -1);
#ifndef Py_GIL_DISABLED
        PyListObject *seq = it->it_seq;
        it->it_seq = NULL;
        Py_DECREF(seq);
#endif
        return NULL;
    }
    FT_ATOMIC_STORE_SSIZE_RELAXED(it->it_index, index + 1);
    return item;
}

On the free-threaded build the index and array access use relaxed atomic loads/stores so iteration can race with list mutation without tearing; exhaustion stores -1 as a sticky “done” marker.

tuple_iterator

c 
// Include/internal/pycore_tuple.h
typedef struct {
    PyObject_HEAD
    Py_ssize_t it_index;
    PyTupleObject *it_seq;   /* Set to NULL when iterator is exhausted */
} _PyTupleIterObject;

Tuples are immutable, so the next function can be simpler and does not need to detach the sequence on exhaustion in the GIL build:

c 
// Objects/tupleobject.c
static PyObject *tupleiter_next(PyObject *self) {
    _PyTupleIterObject *it = _PyTupleIterObject_CAST(self);
    PyTupleObject *seq = it->it_seq;
    Py_ssize_t index = FT_ATOMIC_LOAD_SSIZE_RELAXED(it->it_index);
    if (index < PyTuple_GET_SIZE(seq)) {
        FT_ATOMIC_STORE_SSIZE_RELAXED(it->it_index, index + 1);
        PyObject *item = PyTuple_GET_ITEM(seq, index);
        return Py_NewRef(item);
    }
    // exhausted
#ifndef Py_GIL_DISABLED
    it->it_seq = NULL;
    Py_DECREF(seq);
#endif
    return NULL;
}

Both types expose __length_hint__, __reduce__, __setstate__, and are recycled through freelists (list_iters, tuple_iters).

Dict iterators

dict.__iter__ returns a key iterator, and .values()/.items() return value/item iterators. They all share one struct:

c 
// Objects/dictobject.c
typedef struct {
    PyObject_HEAD
    PyDictObject *di_dict;   /* NULL when exhausted */
    Py_ssize_t di_used;
    Py_ssize_t di_pos;
    PyObject *di_result;     /* reusable (key, value) tuple for items */
    Py_ssize_t len;
} dictiterobject;

Construction records the dict’s ma_used at creation time so a size change during iteration can be detected:

c 
// Objects/dictobject.c
static PyObject *dictiter_new(PyDictObject *dict, PyTypeObject *itertype) {
    dictiterobject *di = PyObject_GC_New(dictiterobject, itertype);
    di->di_dict = (PyDictObject *)Py_NewRef(dict);
    Py_ssize_t used = GET_USED(dict);
    di->di_used = used;
    di->di_len = used;
    // reverse iterators start at the last entry
    if (rev) di->di_pos = ... last index ...;
    else     di->di_pos = 0;
    if (items) di->di_result = _PyTuple_FromPairSteal(Py_None, Py_None);
    _PyObject_GC_TRACK(di);
    return (PyObject *)di;
}

The key iterator walks the underlying key table, skipping deleted slots (me_value == NULL), and marks exhaustion by nulling di_dict:

c 
// Objects/dictobject.c (GIL build)
static PyObject *dictiter_iternextkey_lock_held(PyDictObject *d, PyObject *self) {
    dictiterobject *di = (dictiterobject *)self;
    if (di->di_used != d->ma_used) {
        PyErr_SetString(PyExc_RuntimeError,
                        "dictionary changed size during iteration");
        di->di_used = -1;   // sticky
        return NULL;
    }
    Py_ssize_t i = di->di_pos;
    // walk DK_UNICODE_ENTRIES / DK_ENTRIES skipping empty slots
    ...
    if (i >= n) goto fail;   // exhausted
    di->di_pos = i + 1;
    di->di_len--;
    return Py_NewRef(key);
fail:
    di->di_dict = NULL;
    Py_DECREF(d);
    return NULL;
}

Value and item iterators mirror this, reusing a single tuple for items to avoid per-step allocation. On the free-threaded build the same logic is provided by dictiter_iternext_threadsafe.

Gotcha: mutating a dict while iterating it raises RuntimeError. The di_used snapshot is exactly how CPython catches that, and it’s a sticky error — once tripped, the iterator stays broken.

tp_iternext as the unifying slot

Every iterator type above fills in the same two slots:

c 
PyTypeObject PyListIter_Type = {
    ...
    PyObject_SelfIter,   /* tp_iter  */
    listiter_next,       /* tp_iternext */
    ...
};

That is the whole trick: for x in obj compiles to PyObject_GetIter followed by repeated tp_iternext calls. There is no Python-level __next__ dispatch on the hot path for built-in iterators; the C function pointer is called directly. User-defined iterators pay the slot_tp_iternext -> __next__ lookup cost, while built-ins like list_iterator, tuple_iterator, dict_keyiterator, iterator and callable_iterator run straight C.

Key takeaways

  • Iterability is decided by tp_iter (or sequence fallback); being an iterator is decided by tp_iternext.
  • PyObject_GetIter validates that __iter__ returns a real iterator; PyIter_Next turns StopIteration into a clean end.
  • iterobject.c provides generic iterator (by index) and callable_iterator (call-until-sentinel).
  • Lists and tuples use specialized iterators with freelists and atomic index updates; tuples can skip detachment because they are immutable.
  • Dict iterators share one struct, snapshot ma_used to detect concurrent size changes, and reuse a tuple for items.
  • __iter__/__next__ on Python classes are connected to tp_iter/ tp_iternext by slot wrappers in typeobject.c.

Further reading

  • Objects/iterobject.c – seqiterobject, calliterobject, anextawaitableobject.
  • Objects/listobject.c – list_iter, listiter_next, _PyListIterObject.
  • Objects/tupleobject.c – tuple_iter, tupleiter_next, _PyTupleIterObject.
  • Objects/dictobject.c – dictiter_new, dictiter_iternextkey*.
  • Objects/abstract.c – PyObject_GetIter, PyIter_Next, PyIter_Check.
  • Objects/typeobject.c – slot_tp_iter, slot_tp_iternext.
  • Objects/object.c – PyObject_SelfIter, _PyObject_NextNotImplemented.

PythonCpythonInternalsIterator