Objects/listobject.c (sort and resize)

Objects/listobject.c is the largest file in Objects/ after unicodeobject.c. It covers the mutable sequence type: dynamic resizing with overallocation, the timsort implementation used by list.sort() and the sorted() built-in, in-place reversal, slicing, and the mutation-detecting iterator. The sort alone accounts for roughly 1400 of the 2700 lines.

Map

Lines	Symbol	Role
1–80	PyListObject struct, ob_item, allocated	Header plus pointer to heap-allocated item array; allocated >= ob_size
81–200	list_resize	Dynamic resize: realloc with overallocation when growing, shrink when ob_size < allocated/2
201–350	app1, listappend, listinsert	append and insert paths; both call list_resize
351–500	list_slice, list_ass_slice	Slice read (returns new list) and slice assignment (in-place mutation)
501–650	list_reverse	In-place pointer swap from both ends toward the middle
651–800	listiter, listiter_next	Iterator with it_seq/it_index and ob_size mutation guard
801–2700	listsort subsystem	Full timsort: merge_lo/hi, merge_at, gallop_left/right, run detection, pending-run stack

Reading

list_resize: the overallocation formula

When the requested new size is larger than allocated, list_resize calls PyMem_Realloc with a larger buffer. The target size is chosen so that repeated single-element appends amortize to O(1): the formula grows by roughly 12.5% plus a small constant.

// CPython: Objects/listobject.c:97 list_resize
static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
    Py_ssize_t allocated = self->allocated;

    if (allocated >= newsize && newsize >= (allocated >> 1)) {
        /* within the current buffer; just update ob_size */
        Py_SET_SIZE(self, newsize);
        return 0;
    }

    /* new_allocated = newsize + newsize/8 + (newsize < 9 ? 3 : 6) */
    Py_ssize_t new_allocated = (size_t)newsize + (newsize >> 3) +
                               (newsize < 9 ? 3 : 6);
    ...
    PyObject **items = self->ob_item;
    if (new_allocated <= (PY_SSIZE_T_MAX / sizeof(PyObject *)))
        PyMem_Realloc(items, new_allocated * sizeof(PyObject *));
    ...
}

The shrink guard (newsize >= allocated >> 1) prevents oscillation: if the list is between 50% and 100% full it keeps the existing buffer rather than reallocating immediately.

list_reverse: in-place pointer swap

list.reverse() runs in O(n) time with O(1) extra space by swapping pairs of pointers from both ends inward. No new list object is allocated.

// CPython: Objects/listobject.c:520 listreverse
static int
list_reverse_impl(PyListObject *self)
{
    PyObject **lo = self->ob_item;
    PyObject **hi = self->ob_item + Py_SIZE(self) - 1;
    while (lo < hi) {
        PyObject *t = *lo;
        *lo = *hi;
        *hi = t;
        lo++;
        hi--;
    }
    return 0;
}

Because list_reverse operates directly on ob_item pointers it does not alter reference counts; each pointer is moved but the pointed-to object is unchanged.

listiter: mutation guard via ob_size snapshot

The list iterator records the list's ob_size at creation time inside it_seq. Each call to listiter_next checks whether the list length matches the recorded snapshot; a mismatch raises RuntimeError: list changed size during iteration.

// CPython: Objects/listobject.c:680 listiter_next
static PyObject *
listiter_next(listiterobject *it)
{
    PyListObject *seq = it->it_seq;
    if (seq == NULL)
        return NULL;

    Py_ssize_t index = it->it_index;
    if (index < PyList_GET_SIZE(seq)) {
        PyObject *item = PyList_GET_ITEM(seq, index);
        ++it->it_index;
        Py_INCREF(item);
        return item;
    }
    it->it_seq = NULL;
    Py_DECREF(seq);
    return NULL;
}

The full mutation check is in the ITERNEXT wrapper generated by the Argument Clinic machinery; the inner function shown here focuses on the hot path.

listsort timsort: run detection and galloping

The sort subsystem occupies lines 801 to 2700. Timsort finds existing sorted runs in the input (ascending or descending, the latter reversed in place), then merges them using a pending-run stack. When one side of a merge wins many consecutive comparisons the code switches to gallop mode, which uses binary search to find the changeover point and copies a bulk prefix before resuming element-by-element comparison.

// CPython: Objects/listobject.c:1120 merge_at
static int
merge_at(MergeState *ms, Py_ssize_t i)
{
    sortslice ssa = ms->pending[i].base;
    Py_ssize_t na  = ms->pending[i].len;
    sortslice ssb = ms->pending[i+1].base;
    Py_ssize_t nb  = ms->pending[i+1].len;

    ms->pending[i].len = na + nb;
    if (i == ms->n - 3)
        ms->pending[i+1] = ms->pending[i+2];
    --ms->n;

    /* find where b[0] sits in a; a[k] < b[0] elements can be ignored */
    k = gallop_right(*ssb.keys, ssa.keys, na, 0);
    ...
    /* merge remaining [k:na] of a with all of b */
    if (na - k <= nb)
        return merge_lo(ms, ssa, na - k, ssb, nb);
    else
        return merge_hi(ms, ssa, na - k, ssb, nb);
}

merge_lo copies the shorter run into a temporary buffer and merges forward; merge_hi copies the shorter run and merges backward. Choosing the direction keeps the temporary allocation small.

// CPython: Objects/listobject.c:980 gallop_right
static Py_ssize_t
gallop_right(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint)
{
    /* exponential search from hint outward, then binary search */
    Py_ssize_t ofs = 1, lastofs = 0;
    ...
    while (ofs < n) {
        int k = ISLT(key, a[hint + ofs], compare);
        if (k < 0) return -1;
        if (k)     break;
        lastofs = ofs;
        ofs     = (ofs << 1) + 1;
        if (ofs <= 0) ofs = n;   /* overflow guard */
    }
    /* binary search in (hint+lastofs, hint+ofs] */
    ...
}

The ISLT macro abstracts the comparison function pointer so that timsort works for both the default key-less case and the key= argument case without branching in the inner loop.

gopy notes

Status: not yet ported.

Planned package path: objects/list.go for the list type, resize, append, and slicing; objects/list_sort.go for the full timsort subsystem; objects/list_iter.go for the iterator.

Key porting decisions to resolve:

• list_resize's overallocation formula must be replicated exactly (including the newsize < 9 ? 3 : 6 branch) so that capacity growth matches CPython's behavior for tests that inspect sys.getsizeof trends.
• The timsort in objects/list_sort.go will be a direct port of merge_lo, merge_hi, merge_at, and gallop_left/right rather than delegating to Go's slices.SortFunc. Using Go's sort would not replicate CPython's stable-sort guarantee on already-sorted inputs or the gallop thresholds that affect performance-sensitive benchmarks.
• The mutation guard in listiter_next maps to a version counter on the Go list struct. Each mutating method increments the counter; the iterator saves the counter at creation and checks it on each __next__ call.
• PyList_GET_ITEM is an unchecked index; the gopy equivalent will be an inline method that performs no bounds check in release builds, matching the C macro semantics.