CPython's range Implementation in C: Lazy Sequences That Never Materialize

TL;DR: range isn’t a list of integers. It’s four PyObject * fields — start, stop, step, and a cached length — and every value is computed on demand. len() is O(1), indexing is arithmetic, and x in range(...) is O(1) when x is an int.

Python’s range is not a list of integers. It’s a tiny immutable object that remembers only its start, stop, and step, then computes everything else on demand. range(0, 10**18) takes exactly the same memory as range(3).

In CPython that’s rangeobject in Objects/rangeobject.c, with a cached length and two iterator types. Let’s walk the representation and the hot paths through the 3.15 source.

The object struct

c
// Objects/rangeobject.c
typedef struct {
    PyObject_HEAD
    PyObject *start;
    PyObject *stop;
    PyObject *step;
    PyObject *length;
} rangeobject;

Four PyObject * fields, all owned references. start, stop, and step are the user-supplied bounds, normalized to PyLong objects via PyNumber_Index in range_from_array. length is the precomputed number of items, also a PyLong.

There’s no array of integers anywhere. The sequence is fully lazy.

rangeobject is a fixed-size PyObject (sizeof(rangeobject)), so its allocation cost is constant no matter how many values the range would yield. Deallocation just decrements the four fields and returns the object to a small freelist (Py_ranges_MAXFREELIST == 6):

c
// Objects/rangeobject.c
static void range_dealloc(PyObject *op) {
    rangeobject *r = (rangeobject*)op;
    Py_DECREF(r->start);
    Py_DECREF(r->stop);
    Py_DECREF(r->step);
    Py_DECREF(r->length);
    _Py_FREELIST_FREE(ranges, r, PyObject_Free);
}

Construction and the cached length

range_new / range_vectorcall funnel into range_from_array, which converts arguments and calls make_range_object:

c
// Objects/rangeobject.c
static rangeobject *make_range_object(PyTypeObject *type, PyObject *start,
                                      PyObject *stop, PyObject *step) {
    PyObject *length = compute_range_length(start, stop, step);
    if (length == NULL) return NULL;
    rangeobject *obj = _Py_FREELIST_POP(rangeobject, ranges);
    if (obj == NULL) {
        obj = PyObject_New(rangeobject, type);
        ...
    }
    obj->start = start;
    obj->stop = stop;
    obj->step = step;
    obj->length = length;
    return obj;
}

compute_range_length first tries a fast path where all three values fit in a C long (compute_range_length_long), using the same formula as get_len_of_range:

c
// Objects/rangeobject.c
static unsigned long get_len_of_range(long lo, long hi, long step) {
    assert(step != 0);
    if (step > 0 && lo < hi)
        return 1UL + (hi - 1UL - lo) / step;
    else if (step < 0 && lo > hi)
        return 1UL + (lo - 1UL - hi) / (0UL - step);
    else
        return 0UL;
}

If any value overflows long (or the result doesn’t fit), it falls back to PyObject arithmetic: take the positive-step case, compute (hi - lo - 1) // step + 1, clamping to zero when lo >= hi.

The result is stored once in r->length, so len(r) is just:

c
// Objects/rangeobject.c
static Py_ssize_t range_length(PyObject *op) {
    rangeobject *r = (rangeobject*)op;
    return PyLong_AsSsize_t(r->length);
}

That’s why len(range(...)) is O(1) — and why a range whose length exceeds PY_SSIZE_T_MAX (possible on Win64 with huge ints) still works through the length field even though sq_length can’t represent it.

Indexing: computing, not looking up

range_item / range_subscript never touch a buffer. For an integer index, compute_range_item normalizes negative indices against length, bounds-checks, then computes the value:

c
// Objects/rangeobject.c
static PyObject *compute_item(rangeobject *r, PyObject *i) {
    /* PyLong equivalent to: return r->start + (i * r->step) */
    if (r->step == _PyLong_GetOne()) {
        return PyNumber_Add(r->start, i);
    } else {
        PyObject *incr = PyNumber_Multiply(i, r->step);
        if (!incr) return NULL;
        PyObject *result = PyNumber_Add(r->start, incr);
        Py_DECREF(incr);
        return result;
    }
}

Notice the fast path when step == 1: it skips the multiply entirely. Negative indices are handled by adding length to the index first, exactly like standard sequence semantics. Out-of-range indices raise IndexError.

Slicing returns a new range, not a list. compute_slice uses _PySlice_GetLongIndices against r->length, then builds substart = compute_item(r, start), substop = compute_item(r, stop) and substep = r->step * step, and constructs a new range via make_range_object. So range(10)[2:8:2] is range(2, 8, 4) and costs O(1).

`contains` is O(1)

For an exact int (or bool), range_contains dispatches to range_contains_long, which avoids iteration entirely:

c
// Objects/rangeobject.c
static int range_contains_long(rangeobject *r, PyObject *ob) {
    /* Check if the value can possibly be in the range. */
    cmp1 = PyObject_RichCompareBool(r->step, zero, Py_GT);
    if (cmp1 == 1) { /* positive steps: start <= ob < stop */
        cmp2 = PyObject_RichCompareBool(r->start, ob, Py_LE);
        cmp3 = PyObject_RichCompareBool(ob, r->stop, Py_LT);
    } else {          /* negative steps: stop < ob <= start */
        cmp2 = PyObject_RichCompareBool(ob, r->start, Py_LE);
        cmp3 = PyObject_RichCompareBool(r->stop, ob, Py_LT);
    }
    if (cmp2 == 0 || cmp3 == 0) { /* ob outside of range */
        result = 0; goto end;
    }
    /* Check that the stride does not invalidate membership. */
    tmp1 = PyNumber_Subtract(ob, r->start);
    tmp2 = PyNumber_Remainder(tmp1, r->step);
    result = PyObject_RichCompareBool(tmp2, zero, Py_EQ);
end:
    ...
}

The algorithm is two steps: bound check (start <= ob < stop for a positive step, reversed for a negative one), then a divisibility check (ob - start) % step == 0. Both are O(1) big-int operations.

Gotcha: for any other object type, range_contains falls back to _PySequence_IterSearch — a linear scan. So x in range(...) is only guaranteed O(1) when x is an int.

range_index reuses the same membership test and then computes the index as (ob - start) // step (or just ob - start when step is 1).

Iteration: two tiers

range_iter picks between a fast C-long iterator and a generic PyObject-based one, depending on whether everything fits in a long:

c
// Objects/rangeobject.c
static PyObject *range_iter(PyObject *seq) {
    rangeobject *r = (rangeobject *)seq;
    long lstart = PyLong_AsLong(r->start);
    if (lstart == -1 && PyErr_Occurred()) { PyErr_Clear(); goto long_range; }
    ... /* lstop, lstep similarly */
    ulen = get_len_of_range(lstart, lstop, lstep);
    if (ulen > (unsigned long)LONG_MAX) goto long_range;
    /* overflow check for lstart + ulen * lstep */
    ...
    return fast_range_iter(lstart, lstop, lstep, (long)ulen);
long_range:
    it = PyObject_New(longrangeiterobject, &PyLongRangeIter_Type);
    it->start = Py_NewRef(r->start);
    it->step = Py_NewRef(r->step);
    it->len = Py_NewRef(r->length);
    return (PyObject *)it;
}

The fast tier uses _PyRangeIterObject, whose entire state is three C longs:

c
// Include/internal/pycore_range.h
typedef struct {
    PyObject_HEAD
    long start;
    long step;
    long len;
} _PyRangeIterObject;

Its tp_iternext is trivial, and allocation-free beyond the first PyLong_FromLong:

c
// Objects/rangeobject.c
static PyObject *rangeiter_next(PyObject *op) {
    _PyRangeIterObject *r = (_PyRangeIterObject*)op;
    if (r->len > 0) {
        long result = r->start;
        r->start = result + r->step;
        r->len--;
        return PyLong_FromLong(result);
    }
    return NULL;
}

The generic tier (longrangeiterobject) stores PyObject *start/step/len and does PyNumber_Add / PyNumber_Subtract per step, so it handles arbitrary-precision bounds at the cost of per-iteration allocation. Both iterators are recycled through freelists of size 6.

__reversed__ (range_reverse) re-expresses the reversed sequence as a new range range(start+(n-1)*step, start-step, -step) and again prefers the fast C-long iterator when all values fit.

Memory efficiency summary

A range is sizeof(rangeobject) (≈ 40 bytes on 64-bit) plus the four referenced PyLong objects — independent of its length.
The length is computed once at construction (O(1) for small ints, big-int arithmetic otherwise) and cached.
Indexing, slicing, containment, and len() are all O(1) for ints. Only non-int containment and iteration over huge values degrade.
Iteration has a zero-allocation-per-step fast path for the common case where bounds fit in a C long.

Key takeaways

range stores only start, stop, step, and a cached length. The sequence is never materialized.
Membership of an int is O(1) via a bounds check plus a modulo divisibility test; non-ints fall back to a linear search.
Indexing computes start + i * step; slicing produces another range.
There are two iterator tiers: a C-long fast path (_PyRangeIterObject) and a generic PyObject path for arbitrary precision.
Both range and its iterators are recycled through 6-deep freelists.