Sequence & Mapping Internal Layouts

Python containers provide clean, expressive interfaces for lists, tuples, dictionaries, and sets. However, beneath their friendly surface lie sophisticated C memory layouts designed to optimize CPU cache locality, amortize allocation costs, and preserve insertion order.

Understanding these structures is essential for diagnosing memory bottlenecks and writing high-performance Python applications.

1. Dynamic Arrays: PyListObject#

A Python list is not a linked list; it is a contiguous dynamic array of object pointers (PyObject**).

The Over-Allocation Formula#

When appending an element to a list whose capacity is full (ob_size == allocated), CPython reallocates the pointer array according to a non-linear growth formula:

This formula guarantees that appending $N$ items requires only $O(\log N)$ distinct heap reallocations, delivering amortized $O(1)$ append time.

1
2
3
4
5
6
7
8
9
10
11
12
13
import sys

items = []
previous_capacity = 0

print("Count | Size (bytes) | Allocated Capacity Jump")
print("---------------------------------------------")
for i in range(25):
    items.append(i)
    current_size = sys.getsizeof(items)
    if current_size != previous_capacity:
        print(f"{len(items):5d} | {current_size:12d} | Capacity expanded")
        previous_capacity = current_size

2. Fixed Immutable Sequences: PyTupleObject#

Unlike lists, tuples cannot be mutated after creation. This architectural invariant unlocks several critical optimizations:

1. Inline Element Storage: Tuples store their element pointers directly in the same contiguous memory block following the PyVarObject header, eliminating an extra pointer indirection.
2. Zero Over-Allocation: A tuple of length 5 allocates exactly 5 pointer slots ($C = N$), with zero wasted capacity.
3. Small Tuple Free Lists: CPython maintains dedicated free lists for empty tuples and small tuples (up to length 20). When a small tuple is deallocated, its memory is not returned to the OS; instead, it is cached for instant re-use.

3. Compact Hash Tables: PyDictObject#

In Python 3.6, CPython adopted the compact dictionary architecture pioneered by Raymond Hettinger. Earlier versions used a sparse table containing hash, key, and value entries in each bucket, wasting up to 60% of table memory on empty buckets.

The modern compact dictionary separates indexing from entry storage:

Collision Resolution via Pseudo-Random Probing#

When two keys produce identical index slots, CPython resolves collisions using open addressing with a recurrence relation:

Where $h = \text{hash}(K)$ and the table size is always a power of two ($2^k$).

4. SipHash-2-4 & Collision Attack Defense#

If an attacker knows the hash algorithm, they can craft thousands of string keys that all collide into the same hash bucket, degrading dictionary lookups from $O(1)$ to $O(N)$ and causing denial-of-service (hash flooding).

To prevent this vulnerability, CPython uses the cryptographically secure SipHash-2-4 algorithm with a random seed initialized per interpreter process (PYTHONHASHSEED). Even with identical string data, hash values differ across different Python process runs.

5. Concept Verification#

Test your understanding of CPython container internals: