CPython Formal Derivations & Operational Identities

Behind Python's dynamic ergonomics lies a foundation of rigorous mathematical equations, recurrence relations, and formal structural invariants.

This revision matrix consolidates every mathematical equation governing CPython runtime execution, memory footprints, and algorithmic complexities into a single, authoritative reference.

Formal Mathematical ModelsReference

KaTeX

Complete mathematical formulations governing CPython memory, algorithms, and execution.

1. Unified Object Memory Footprints#

Fixed-Size vs Variable-Length Headers (64-bit Platform)#

\text{Fixed Object Header}: \text{PyObject} = (\text{ob\_refcnt}, \text{ob\_type}) \implies 16 \text{ bytes}

\text{Variable Object Header}: \text{PyVarObject} = (\text{ob\_refcnt}, \text{ob\_type}, \text{ob\_size}) \implies 24 \text{ bytes}

\text{GC Tracked Header}: \text{PyGC\_Head} = (\text{gc\_next}, \text{gc\_prev}, \text{gc\_refs}) \implies 16 \text{ bytes (prepended)}

Architecture Diagram

Rendering diagram...

2. Scalar Representation Formulations#

Arbitrary-Precision Integers (`PyLongObject`)#

Large integers $N \in \mathbb{Z}$ are expressed using a sign-magnitude base- $2^{30}$ positional numeral system:

N = \text{sgn}(\text{ob\_size}) \cdot \sum_{i=0}^{|s|-1} d_i \cdot 2^{30 \cdot i}

Where:

$d_i \in \{0, 1, \dots, 2^{30} - 1\}$ is an unsigned 32-bit digit word (uint32_t).
$|s| = |\text{ob\_size}|$ indicates the count of active digits.
$\text{sgn}(\text{ob\_size}) \in \{-1, 0, 1\}$ stores integer sign.

Flexible Unicode Strings (PEP 393)#

1 \text{ byte} & \text{if } V_{\max} < 2^8 \quad (\text{ASCII / Latin-1}) \\ 2 \text{ bytes} & \text{if } 2^8 \le V_{\max} < 2^{16} \quad (\text{UCS-2}) \\ 4 \text{ bytes} & \text{if } 2^{16} \le V_{\max} < 2^{32} \quad (\text{UCS-4})

M_{\text{str}}(L, k) = \text{sizeof}(\text{PyASCIIObject}) + (L \cdot k) + 1

3. Container Capacity & Hash Recurrence Relations#

Dynamic Array Capacity Growth (`PyListObject`)#

When an append operation exceeds capacity, CPython reallocates the pointer buffer according to the non-linear growth formula:

C_{\text{new}} = N_{\text{new}} + \left\lfloor \frac{N_{\text{new}}}{8} \right\rfloor + \begin{cases} 3 & \text{if } N_{\text{new}} < 9 \\ 6 & \text{if } N_{\text{new}} \ge 9 \end{cases}

This guarantees amortized insertion complexity $O(1)$ while bounding memory waste to roughly $12.5\%$ .

Open Addressing Hash Collision Probing (`PyDictObject`)#

Given key hash $h = \text{hash}(K)$ , probing index $i$ inside a table of size $2^k$ follows the pseudo-random recurrence relation:

i_0 = h \pmod{2^k}

i_{j+1} = (5 \cdot i_j + 1 + \text{perturb}_j) \pmod{2^k}, \quad \text{perturb}_{j+1} = \text{perturb}_j \gg 5

Where $\text{perturb}_0 = h$ .

4. Hierarchy & Resolution Invariants#

C3 Linearization MRO Recursion Identity#

The Method Resolution Order $L(C)$ for class $C$ with parents $B_1, B_2, \dots, B_n$ is:

L(C) = C + \text{merge}\left( L(B_1), L(B_2), \dots, L(B_n), (B_1, B_2, \dots, B_n) \right)

L(\text{object}) = (\text{object})

Subject to the head-not-in-tail selection rule:

\text{head}(L_i) \notin \text{tail}(L_j), \quad \forall j \neq i

Attribute Resolution Precedence Sequence#

\mathcal{R}(obj, attr) = \text{DataDescriptor} \succ \text{InstanceDict} \succ \text{NonDataDescriptor} \succ \text{ClassDict} \succ \text{GetAttr}

Amdahl's Law Speedup Boundary#

\text{Speedup}(P) = \frac{1}{S + \frac{1 - S}{P}} - O(P)

5. Concept Verification#

Test your understanding of formal CPython mathematical models:

Concept check

In the PyListObject capacity formula, why does CPython add (N >> 3) plus 3 or 6 instead of simply doubling the capacity (2 * N) like standard textbooks?