Lists, Tuples, Slicing & Sequence Operations

Lists and tuples are CPython’s core ordered sequence containers. While lists are mutable dynamic pointer arrays, tuples are immutable fixed sequences. Understanding CPython’s dynamic array over-allocation formula, tuple freelist caching, slice memory copies, and zero-copy memoryview buffers is essential for performance engineering.

This chapter details PyListObject array resizing mechanics, tuple freelist allocation, slicing overhead, and memoryview buffers.

1. CPython List Architecture (PyListObject)

A Python list is not a linked list. It is an array of pointers to PyObject structs stored in contiguous C memory (PyObject** ob_item).

// CPython Internal Representation
typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;  // Array of pointers to heap objects
    Py_ssize_t allocated; // Total allocated slot capacity
} PyListObject;

Growth Pattern & Over-Allocation Formula:

When you call list.append(), CPython doesn’t resize the underlying array by 1 slot. It over-allocates extra capacity to ensure $O(1)$ amortized append performance:

Over-allocation Formula:
new_allocated = N + (N >> 3) + (N < 9 ? 3 : 6)

PyListObject Growth Pattern:

[ PyListObject Struct ]
├── ob_size: 4      (Current item count)
├── allocated: 8    (Total pointer array capacity)
└── ob_item (ptr) -> [ ptr0 | ptr1 | ptr2 | ptr3 | UNUSED | UNUSED | UNUSED | UNUSED ]

When ob_size == allocated, CPython allocates a new, larger pointer array, copies the pointers over, and frees the old array.

2. Tuple Architecture & Freelist Caching (PyTupleObject)

Tuples (tuple) are immutable sequence containers. Because their size is fixed at creation, CPython stores tuple element pointers inline directly following the PyTupleObject header.

Freelist Caching:

To minimize malloc/free system calls for small tuples, CPython maintains an array of freelists for tuples of size 1 to 20:

• When a small tuple is garbage collected, CPython doesn’t return its C memory to the system allocator (pymalloc). It puts the pre-allocated struct memory onto a freelist.
• Creating a new small tuple grabs a pre-allocated block from the freelist, eliminating C heap allocation overhead.

3. Slicing Mechanics vs. Zero-Copy memoryview

Standard Slicing (a[start:stop]):

Slicing a list or tuple (my_list[2:5]) creates a completely new container object and copies the element pointers into the new array.

• Time Complexity: O(K) where K = stop - start.
• Memory Overhead: Allocates a new PyListObject and copies $K$ pointer references.

Zero-Copy Buffers (memoryview):

When working with large binary buffers (e.g. video frames, socket streams), slicing bytes creates unnecessary memory copies. A memoryview exposes CPython’s internal Buffer Protocol (Py_buffer), allowing you to slice bytes without copying memory payload:

data = bytearray(b"X" * 10_000_000)  # 10MB byte buffer

# Standard slice: Allocates a NEW 5MB byte object in memory!
chunk_copy = data[0:5_000_000]

# Memoryview slice: Zero-copy view! Shares original memory buffer.
view = memoryview(data)[0:5_000_000]
view[0] = ord('Y')  # Modifies underlying data[0] in place!

4. Production Trade-offs & Queue Selection

• Pop from Front: Calling list.pop(0) or list.insert(0, item) forces CPython to call memmove, shifting all $N-1$ element pointers right or left. This takes $O(N)$ linear time.
• High-Throughput Queues: Never use a list as a FIFO queue. Use collections.deque ($O(1)$ head/tail operations via 64-element block arrays).