Every object CPython creates is a C struct allocated on the heap. Whatever else it holds, it begins with the same two fields, defined as PyObject in Include/object.h:

• ob_refcnt: how many references point at the object. When it drops to zero the object is freed immediately (Chapter 4).
• ob_type: a pointer to the object's type object, which is itself a Python object. The type decides what the object can do: how to add it, hash it, print it, get an attribute from it.

Objects whose size varies, such as int, tuple, bytes and list, use PyVarObject, which adds an ob_size field (the number of items or digits). After the header comes the type-specific payload: the digits of an int, the item pointers of a tuple, the bytes of a string.

A variable is not a box that holds a value. A name is an entry in a namespace (a dict, or a slot in a frame) that holds a pointer to an object. x = 5 makes the name x point at an int object. The object does not know which names point at it, only how many references exist.

Because types are objects too, you can ask any type for its type. The chain stops at type, which is its own type, and every class including type inherits from object:

print(type(5), type(int), type(type))
print(int.__mro__)
print(isinstance(type, object), isinstance(object, type))
print(issubclass(type, object), issubclass(object, type))

<class 'int'> <class 'type'> <class 'type'>
(<class 'int'>, <class 'object'>)
True True
True False

How big an object is

sys.getsizeof returns the size of the object's own struct in bytes, not counting objects it points to. On a 64-bit build the two header fields already take 16 bytes, so even an empty object is not small:

import sys
for label, v in [("object()", object()), ("None", None), ("1.0", 1.0), ("0", 0), ("1", 1),
                 ("2**30", 2**30), ("2**60", 2**60), ('""', ""), ('"abc"', "abc"),
                 ("()", ()), ("[]", []), ("{}", {}), ("set()", set())]:
    print(f"{label:>9} {sys.getsizeof(v):4}")

 object()   16
     None   16
      1.0   24
        0   28
        1   28
    2**30   32
    2**60   36
       ""   41
    "abc"   44
       ()   40
       []   56
       {}   64
    set()  216

An int stores its magnitude in 30-bit "digits". 0 and 1 both need one digit, so they are 28 bytes, and every 30 bits of magnitude adds 4 bytes. A list's 56 bytes hold only the header and a pointer to a separate array of item pointers, which is why getsizeof of a list never includes its items.

Immortal objects (3.12)

Before 3.12, None, True, small ints and interned strings had ordinary reference counts that every use incremented and decremented. That meant constant writes to shared memory, which hurts multi-core performance. PEP 683 made these objects immortal: their refcount is set to a huge sentinel value and Py_INCREF and Py_DECREF leave it alone.

import sys
print(sys.getrefcount(None))
print(sys.getrefcount(7))
x = object()
print(sys.getrefcount(x))

4294967295
4294967295
2

getrefcount reports one more than you might expect for x because passing x as an argument creates a temporary reference.

Python has two different questions about two objects:

• a is b asks whether they are the same object. In CPython this compares two pointers and cannot be overridden.
• a == b asks whether they are equal. It calls a.__eq__(b) (and may fall back to b.__eq__(a)), so a class decides what equality means.

id(obj) returns an integer that is unique among objects that exist at the same time. In CPython it is the object's memory address. Two objects with non-overlapping lifetimes may get the same id, because the memory of the first was reused:

print(id([]) == id([]))
a = []
b = []
print(id(a) == id(b))

True
False

In the first line, the first list is freed as soon as id() returns, and the second list is allocated at the same address. In the second pair both lists are alive at once, so their ids differ.

When equality is not reflexive

float("nan") is not equal to itself, as IEEE 754 requires. Container comparisons, however, check identity before equality as an optimisation (PyObject_RichCompare with Py_EQ inside list comparison uses is first). So the same NaN object is "found" in a list even though it is not equal to itself:

x = float("nan")
print(x == x, x is x)
print([x] == [x], x in [x])
print(float("nan") in [float("nan")])

False True
True True
False

Some objects are shared because CPython creates them once and hands out the same object every time. This is an implementation detail, but interviewers love it because it makes is look inconsistent.

The small-int cache

CPython pre-creates the ints from −5 to 256 when the interpreter starts. Any operation that produces one of these values returns the cached object. Values outside the range get a fresh object each time they are computed at run time:

a = int("256"); b = int("256")
c = int("257"); d = int("257")
print(a is b, c is d)
e = 250 + 6; f = 251 + 6
print(e is int("256"), f)

True False
True 257

Constants in the same code object

The compiler collects the literals of a function or module into a tuple of constants, co_consts, and merges equal ones. Two literals 257 written in the same compilation unit therefore end up as the same object, even though 257 is outside the small-int cache. Compiled separately, they are different objects:

a = 257
b = 257
print(a is b)

ns = {}
exec("x = 257", ns)
exec("y = 257", ns)
print(ns["x"] is ns["y"])

def f():
    return 1000, 1000
p, q = f()
print(p is q, f.__code__.co_consts)

True
False
True (None, (1000, 1000))

This is why a is b gives a different answer in a script, in the interactive prompt (where each line is compiled separately) and inside a function. None of these answers is a language guarantee.

String interning

Strings that look like identifiers (letters, digits and underscores) and that appear as constants in code are interned: CPython keeps one copy in a global table so that attribute and variable lookups can compare pointers before comparing characters. Strings built at run time are not interned unless you call sys.intern:

import sys
a = "hello_world"
b = "hello_" + "world"          # folded at compile time, then interned
c = "".join(["hello_", "world"])  # built at run time
print(a is b, a is c, a == c)
print(sys.intern(c) is a)
s = "hello world!"
t = "hello world!"
print(s is t)

True False True
True
True

s is t is True here only because both literals live in the same code object, not because the string was interned (it contains a space and !).

b = a copies a pointer. After it, both names refer to the same object, and a change made through one name is visible through the other. This only matters for mutable objects (list, dict, set, most user classes). For immutable ones (int, str, tuple, frozenset) every "change" creates a new object, so sharing is invisible.

a = [1, 2, 3]
b = a
b.append(4)
print(a, a is b)

s = "abc"
t = s
t += "d"
print(s, t, s is t)

[1, 2, 3, 4] True
abc abcd False

+= is two different operations

x += y first tries x.__iadd__(y), which mutable types implement by changing x in place and returning it. If there is no __iadd__, it falls back to x = x + y, which builds a new object and rebinds the name. Either way the name is assigned at the end, and that last step explains one of the strangest results in Python:

t = ([1, 2], 3)
try:
    t[0] += [99]
except TypeError as e:
    print("error:", e)
print(t)

error: 'tuple' object does not support item assignment
([1, 2, 99], 3)

t[0] += [99] runs as: load t[0] (the list), call list.__iadd__, which appends 99 in place and succeeds, then store the result back with t[0] = …, which fails because tuples do not support item assignment. The exception is raised after the mutation has already happened.

Copies: shallow and deep

list(a), a[:], a.copy() and copy.copy(a) make a shallow copy: a new outer container whose slots point at the same inner objects. copy.deepcopy recursively copies the inner objects too, and keeps a memo dict so that shared and cyclic references are copied once:

import copy
grid = [[0, 0], [0, 0]]
shallow = grid[:]
deep = copy.deepcopy(grid)
grid[0][0] = 1
print(shallow, deep)

row = [0] * 2
bad = [row] * 2
bad[0][0] = 7
good = [[0] * 2 for _ in range(2)]
good[0][0] = 7
print(bad, good)

[[1, 0], [0, 0]] [[0, 0], [0, 0]]
[[7, 0], [7, 0]] [[7, 0], [0, 0]]

[row] * 2 repeats the pointer to one list, so both rows are the same object. The comprehension evaluates [0] * 2 again on every iteration and builds independent rows.

A Python int never overflows. CPython stores the sign and magnitude as an array of 30-bit digits, so the cost of arithmetic grows with the number of digits: addition is linear, and multiplication uses Karatsuba above a threshold. Converting very large ints to and from decimal strings is quadratic, so since 3.11 CPython refuses conversions above 4300 digits by default to block denial-of-service inputs:

import sys
n = 2**100
print(n, n.bit_length(), sys.getsizeof(n))
print(sys.int_info.bits_per_digit, sys.get_int_max_str_digits())
big = 10**5000
try:
    str(big)
except ValueError as e:
    print("ValueError:", str(e)[:60])
print(len(hex(big)))

1267650600228229401496703205376 101 40
30 4300
ValueError: Exceeds the limit (4300 digits) for integer string conversio
4155

Hexadecimal conversion is linear, so it is not limited. You can raise the limit with sys.set_int_max_str_digits or the PYTHONINTMAXSTRDIGITS environment variable.

Booleans are ints: bool is a subclass of int, True == 1 and True + True == 2. That is why {1: "a", True: "b"} has a single key.

• Every object starts with ob_refcnt and ob_type; variable-size ones add ob_size. A 64-bit object() is 16 bytes, an int 28.
• Names hold references. Assignment, argument passing and return copy references, never objects.
• is is identity (address in CPython), == calls __eq__. Use is only for None, True, False and your own sentinels.
• Cached: ints −5..256, None, True, False, the empty tuple, and interned identifier-like string constants. In 3.12 these are immortal.
• Equal constants in one code object are merged, so a = 257; b = 257 in one file gives a is b == True. Not a guarantee.
• Containers check identity before equality, so nan in [nan] is True for the same NaN object.
• x += y calls __iadd__ (in place for mutable types), then assigns. t[0] += [1] mutates the list and then raises.
• Shallow copy: a[:], list(a), a.copy(). Deep copy: copy.deepcopy. [[0]*n]*m shares rows.
• Ints are arbitrary precision in 30-bit digits; decimal conversion is limited to 4300 digits since 3.11.
• bool subclasses int: True == 1, and 1, 1.0 and True are the same dict key.

A namespace maps names to objects. Python has four kinds that matter for name lookup, searched in this order:

1. Local: the names assigned in the current function call.
2. Enclosing: the locals of any function that lexically contains this one.
3. Global: the module's namespace, a plain dict you can see as globals() or module.__dict__.
4. Built-in: the builtins module, which holds len, print, ValueError and the rest.

Scopes are lexical: what matters is where the function was written, not where it is called from. A function defined inside another one can see the outer function's names even after the outer call has returned.

x = "global"

def outer():
    x = "enclosing"
    def inner():
        return x
    return inner

def caller():
    x = "caller's local"
    return outer()()

print(caller())
print(len.__module__, "len" in dir(__builtins__))

enclosing
builtins True

inner returns "enclosing" even though it is called from caller, because lookup follows the nesting in the source code.

Shadowing a built-in

Any assignment to a name such as list, id or sum at module level creates a global that hides the built-in for the rest of the module. Nothing warns you:

list = [1, 2, 3]
try:
    print(list("abc"))
except TypeError as e:
    print("TypeError:", e)
del list
print(list("abc"))

TypeError: 'list' object is not callable
['a', 'b', 'c']

del list removes the global, and lookup falls through to builtins again.

Python does not look a name up dynamically through all four scopes on every access. When it compiles a function, it reads the whole body and classifies every name once:

• A name that is assigned anywhere in the function (by =, +=, for, import, def, class, with … as, except … as or a walrus :=) is local to the whole function, unless declared global or nonlocal.
• A name that is only read, and is local in an enclosing function, is free: it is reached through a cell (below).
• Any other name that is only read is global-or-built-in.

The classification picks the bytecode: LOAD_FAST for locals (an index into an array in the frame), LOAD_DEREF for free variables and LOAD_GLOBAL for the rest. LOAD_FAST is just an array index, which is why local variables are faster than globals.

import symtable

src = """
total = 0
def f(a):
    b = a + total
    def g():
        return b + len(a)
    return g
"""
mod = symtable.symtable(src, "<demo>", "exec")
f = mod.get_children()[0]
g = f.get_children()[0]
for table in (f, g):
    for s in sorted(table.get_symbols(), key=lambda s: s.get_name()):
        kind = ("local" if s.is_local() else "") + (" free" if s.is_free() else "") + (" global" if s.is_global() else "")
        print(table.get_name(), s.get_name(), kind.strip())

f a local
f b local
f g local
f total global
g a free
g b free
g len global

b is local in f and free in g. total and len are globals as far as the compiler knows; whether len is found in the module or in builtins is decided at run time.

UnboundLocalError

Because an assignment anywhere makes a name local everywhere in the function, reading it before the assignment fails, even if a global of the same name exists:

count = 0

def bump():
    try:
        count += 1
    except UnboundLocalError as e:
        print("UnboundLocalError:", e)

def show_then_set():
    try:
        print(count)
    except UnboundLocalError as e:
        print("UnboundLocalError:", e)
    count = 5

bump()
show_then_set()

UnboundLocalError: cannot access local variable 'count' where it is not associated with a value
UnboundLocalError: cannot access local variable 'count' where it is not associated with a value

In show_then_set, the print is on the line before the assignment, and it still fails. The compiler saw count = 5 and made count local for the whole body. UnboundLocalError is a subclass of NameError.

What bytecode the compiler chose

import dis

g_value = 10

def f(a):
    b = a * 2
    return b + g_value + len("x")

dis.dis(f)

  5           0 RESUME                   0

  6           2 LOAD_FAST                0 (a)
              4 LOAD_CONST               1 (2)
              6 BINARY_OP                5 (*)
             10 STORE_FAST               1 (b)

  7          12 LOAD_FAST                1 (b)
             14 LOAD_GLOBAL              0 (g_value)
             24 BINARY_OP                0 (+)
             28 LOAD_GLOBAL              3 (NULL + len)
             38 LOAD_CONST               2 ('x')
             40 CALL                     1
             48 BINARY_OP                0 (+)
             52 RETURN_VALUE

a and b are LOAD_FAST, while g_value and len use LOAD_GLOBAL, which checks the module dict and then the builtins dict. CPython caches global lookups per instruction and invalidates the cache when either dict changes, so in a hot loop LOAD_GLOBAL is cheap but still slower than LOAD_FAST.

When an inner function uses a variable of the outer function, the outer local cannot live in the outer frame's array any more, because the inner function may outlive that frame. The compiler instead stores it in a cell object: a tiny heap object that holds one reference. The outer function and every inner function that uses the variable share the same cell, so they all see the latest value.

def make_counter():
    count = 0
    def inc():
        nonlocal count
        count += 1
        return count
    def peek():
        return count
    return inc, peek

inc, peek = make_counter()
inc(); inc()
print(peek())
print(inc.__code__.co_freevars, inc.__closure__[0] is peek.__closure__[0])
print(inc.__closure__[0].cell_contents)
print(make_counter.__code__.co_cellvars)

2
('count',) True
2
('count',)

co_cellvars lists the outer function's variables that live in cells, and co_freevars lists the inner function's references to them. __closure__ is the tuple of cells a function object carries.

Late binding: the loop-closure bug

A closure captures the variable (the cell), not the value the variable had when the function was created. Functions created in a loop therefore all see the variable's final value:

fns = [lambda: i for i in range(3)]
print([f() for f in fns])

fixed = [lambda i=i: i for i in range(3)]
print([f() for f in fixed])

from functools import partial
def show(i):
    return i
parts = [partial(show, i) for i in range(3)]
print([p() for p in parts])

[2, 2, 2]
[0, 1, 2]
[0, 1, 2]

The default argument i=i is evaluated when each lambda is created, so it freezes the current value. functools.partial does the same by storing the argument. The same bug appears with callbacks registered in a loop (GUI handlers, threading.Thread(target=lambda: work(i))).

global x says "the name x in this function refers to the module's x". Assignments then write to the module dict. nonlocal x says "x refers to the nearest enclosing function's variable", and it must already exist there; it never reaches the module level.

total = 0

def add_global(n):
    global total
    total += n

def outer():
    level = "outer"
    def inner():
        nonlocal level
        level = "changed by inner"
    inner()
    return level

add_global(5)
print(total, outer())

try:
    exec("def f():\n    nonlocal missing\n")
except SyntaxError as e:
    print("SyntaxError:", e.msg)

5 changed by inner
SyntaxError: no binding for nonlocal 'missing' found

Neither statement is needed to mutate an object: items.append(x) inside a function works on a global list without global items, because it reads the name and calls a method; it never assigns the name. You need global or nonlocal only to rebind the name.

def f(x, items=[]) evaluates [] once, when the def statement runs, and stores the object in f.__defaults__. Every call that does not pass items gets that same list, so changes accumulate between calls:

def append_to(x, items=[]):
    items.append(x)
    return items

print(append_to(1), append_to(2))
print(append_to.__defaults__)

def append_safe(x, items=None):
    if items is None:
        items = []
    items.append(x)
    return items

print(append_safe(1), append_safe(2))

[1, 2] [1, 2]
([1, 2],)
[1] [2]

Both calls return the same list object, which is why the first line prints [1, 2] twice: by the time print runs, the shared list holds both items. The None sentinel pattern creates a fresh list on each call. The same rule makes def f(when=datetime.now()) freeze the time at import, and it is also why the i=i trick above works.

Comprehensions and class bodies

A list comprehension has its own scope for its loop variable, so the variable does not leak. Since 3.12 (PEP 709), CPython inlines comprehensions into the enclosing function for speed, but it keeps the same visible semantics.

A class body is a namespace but not an enclosing scope for anything nested in it: methods cannot see class attributes as bare names, and neither can a comprehension in the class body (except in its first iterable, which is evaluated in the class scope):

class Config:
    base = 10
    try:
        scaled = [base * i for i in range(3)]
    except NameError as e:
        error = str(e)
    ok = [i for i in range(base, base + 2)]

print(Config.error)
print(Config.ok)

x = "module"
squares = [x for x in range(3)]
print(x, squares)

name 'base' is not defined
[10, 11]
module [0, 1, 2]

range(base, base + 2) is the first iterable, so it can see base. Inside the comprehension body, base is looked up as a global and not found. Use self.base, cls.base or Config.base inside methods.

• Lookup order: Local, Enclosing, Global, Built-in. Scoping is lexical (where the function is written).
• Any assignment in a function (=, augmented assignment, for, import, def, class, as, :=) makes the name local to the whole function.
• Reading a local before assigning it raises UnboundLocalError, even if a global exists.
• Bytecode: LOAD_FAST (locals, array index), LOAD_DEREF (cells), LOAD_GLOBAL (module dict, then builtins).
• Closures capture variables through shared cell objects (__closure__, co_freevars, co_cellvars), so they see the latest value.
• Loop closures: bind per iteration with lambda i=i: …, functools.partial or a factory function.
• global x rebinds the module variable. nonlocal x rebinds an enclosing function's variable and must find one. Neither is needed to mutate.
• Defaults are evaluated once at def time and stored in __defaults__; use None for mutable or time-based defaults.
• Comprehension variables do not leak; := inside a comprehension binds in the enclosing scope.
• Class bodies are not enclosing scopes: methods and comprehensions in the class body cannot see class attributes by bare name.

When you import a module or run a script, CPython goes through these stages:

1. Tokenise: split the text into tokens (NAME, OP, NUMBER, INDENT …).
2. Parse: build an abstract syntax tree (AST) with the PEG parser introduced in 3.9.
3. Symbol table: classify every name as local, free, cell or global (Chapter 2).
4. Compile: turn the AST into a control-flow graph of instructions, optimise it, and assemble it into bytecode.
5. Execute: the interpreter loop in Python/ceval.c runs the bytecode.

The result of step 4 is a code object: an immutable bundle of the bytecode plus everything needed to run it: constants, names, local variable names, the stack size it needs, line-number and exception tables. Every function, class body, module and comprehension has its own code object.

import ast, tokenize, io

src = "total = price * 3"
toks = [tokenize.tok_name[t.type] for t in tokenize.generate_tokens(io.StringIO(src).readline)]
print(toks[:5])
print(ast.dump(ast.parse(src).body[0]))
code = compile(src, "<demo>", "exec")
print(type(code).__name__, code.co_names, code.co_consts)

['NAME', 'OP', 'NAME', 'OP', 'NUMBER']
Assign(targets=[Name(id='total', ctx=Store())], value=BinOp(left=Name(id='price', ctx=Load()), op=Mult(), right=Constant(value=3)))
code ('price', 'total') (3, None)

compile() exposes steps 1–4 directly. Its mode argument is "exec" for a module or statements, "eval" for a single expression and "single" for one interactive statement (which prints expression results, as the REPL does).

What a code object holds

def area(w, h=2, *, unit="m"):
    scale = 1.0
    return f"{w * h * scale}{unit}"

c = area.__code__
print(c.co_name, c.co_argcount, c.co_kwonlyargcount, c.co_nlocals)
print(c.co_varnames)
print(c.co_consts, c.co_names, c.co_stacksize)
print(len(c.co_code), "bytes of bytecode")

area 2 1 4
('w', 'h', 'unit', 'scale')
(None, 1.0) () 2
30 bytes of bytecode

co_varnames lists the parameters first, then other locals, which is the order of the frame's local slots. A function object wraps a code object together with the things that vary per def execution: its globals dict, defaults, closure cells and __dict__. Many function objects can share one code object, for example the closures created by repeated calls of a factory.

CPython bytecode is a sequence of 2-byte units: one byte of opcode and one byte of argument (larger arguments use EXTENDED_ARG prefixes). Many instructions are followed by cache entries that the specialising interpreter uses, which is why offsets in dis output sometimes jump by more than 2.

The machine is a stack machine: instructions push values onto a per-frame value stack and pop them off. a + b * c becomes "push a, push b, push c, multiply the top two, add the top two":

import dis

def calc(a, b, c):
    return a + b * c

dis.dis(calc)

  3           0 RESUME                   0

  4           2 LOAD_FAST                0 (a)
              4 LOAD_FAST                1 (b)
              6 LOAD_FAST                2 (c)
              8 BINARY_OP                5 (*)
             12 BINARY_OP                0 (+)
             16 RETURN_VALUE

Each line shows the source line number (only when it changes), the byte offset, the instruction name, the numeric argument and a human-readable meaning in brackets. BINARY_OP 5 (*) and BINARY_OP 0 (+) are one generic instruction for all binary operators, selected by the argument.

Control flow

if, while and for become conditional and unconditional jumps. A for loop calls iter() once (GET_ITER) and then FOR_ITER repeatedly, which calls next() and jumps out of the loop when the iterator is exhausted:

import dis

def count_pos(xs):
    n = 0
    for x in xs:
        if x > 0:
            n += 1
    return n

dis.dis(count_pos)

  3           0 RESUME                   0

  4           2 LOAD_CONST               1 (0)
              4 STORE_FAST               1 (n)

  5           6 LOAD_FAST                0 (xs)
              8 GET_ITER
        >>   10 FOR_ITER                13 (to 40)
             14 STORE_FAST               2 (x)

  6          16 LOAD_FAST                2 (x)
             18 LOAD_CONST               1 (0)
             20 COMPARE_OP              68 (>)
             24 POP_JUMP_IF_TRUE         1 (to 28)
             26 JUMP_BACKWARD            9 (to 10)

  7     >>   28 LOAD_FAST                1 (n)
             30 LOAD_CONST               2 (1)
             32 BINARY_OP               13 (+=)
             36 STORE_FAST               1 (n)
             38 JUMP_BACKWARD           15 (to 10)

  5     >>   40 END_FOR

  8          42 LOAD_FAST                1 (n)
             44 RETURN_VALUE

COMPARE_OP pushes the result of x > 0. In 3.12 the compiler lays the loop out so that POP_JUMP_IF_TRUE jumps forward to the increment, while the fall-through JUMP_BACKWARD goes straight back to FOR_ITER. The augmented assignment is BINARY_OP 13 (+=), the in-place variant of addition. END_FOR is where FOR_ITER jumps when the iterator raises StopIteration; the exception itself is never created for built-in iterators.

Each call to a Python function needs a frame: the state of one running code object. It holds the instruction pointer, the local variable slots (including cells), the value stack, and references to the function's globals and builtins. Since 3.11 CPython allocates these frames in a contiguous per-thread "data stack" rather than as separate heap objects, and only creates a full frame object when something asks for it (a traceback, sys._getframe, a debugger). That change is a large part of why 3.11 calls are faster.

import sys

def inner():
    f = sys._getframe()
    chain = []
    while f is not None:
        chain.append(f"{f.f_code.co_name}:{f.f_lineno}")
        f = f.f_back
    return chain

def middle():
    return inner()

def outer():
    return middle()

print(outer())
print(sys.getrecursionlimit())

['inner:7', 'middle:12', 'outer:15', '<module>:17']
1000

f_back links each frame to its caller, which is exactly the chain a traceback prints. The recursion limit (1000 by default) caps how deep this chain can grow so that a runaway recursion raises RecursionError instead of overflowing the C stack.

The loop itself

The core of ceval.c is conceptually:

for (;;) {
    opcode, oparg = next instruction
    switch (opcode) {
        case LOAD_FAST:  push(locals[oparg]); break;
        case BINARY_OP:  right = pop(); left = pop(); push(binary_op(left, right, oparg)); break;
        case RETURN_VALUE: return pop();
        ...
    }
    every so often: check for signals, pending calls and a GIL drop request
}

In reality it uses computed gotos where the compiler supports them (each instruction jumps straight to the next handler, which branch predictors handle better than a single switch), and the handlers are generated from a domain-specific language in Python/bytecodes.c. The "every so often" check is how a long-running loop still responds to Ctrl-C and lets other threads take the GIL (Chapter 11).

PEP 659 made CPython's interpreter adaptive. Generic instructions such as LOAD_ATTR, BINARY_OP, LOAD_GLOBAL and CALL start in a counting mode. After an instruction has run a few times (the warm-up), the interpreter looks at the types it actually saw and replaces the instruction in place with a specialised version, using the inline cache entries after it to store what it learned (a type version, a dict key index, a slot offset):

import dis

class Point:
    def __init__(self, x):
        self.x = x

def get_x(p):
    return p.x

def add(a, b):
    return a + b

for _ in range(100):
    get_x(Point(1))
    add(1, 2)

dis.dis(get_x, adaptive=True)
dis.dis(add, adaptive=True)

  7           0 RESUME                   0

  8           2 LOAD_FAST                0 (p)
              4 LOAD_ATTR_INSTANCE_VALUE     0 (x)
             24 RETURN_VALUE
 10           0 RESUME                   0

 11           2 LOAD_FAST__LOAD_FAST     0 (a)
              4 LOAD_FAST                1 (b)
              6 BINARY_OP_ADD_INT        0 (+)
             10 RETURN_VALUE

LOAD_ATTR_INSTANCE_VALUE reads the attribute straight from the instance's value array after checking that the type has not changed, skipping the general attribute-lookup machinery. BINARY_OP_ADD_INT adds two ints without the generic dispatch, and LOAD_FAST__LOAD_FAST is a "superinstruction" that does two loads in one step.

If the guess later turns out wrong (say add is suddenly called with strings), the specialised instruction fails its guard, falls back to the generic path, and after enough misses it is de-specialised and can re-specialise for the new types:

import dis

def add(a, b):
    return a + b

for _ in range(100):
    add(1, 2)
for _ in range(100):
    add("a", "b")

for ins in dis.get_instructions(add, adaptive=True):
    if ins.opname.startswith("BINARY_OP"):
        print(ins.opname)

BINARY_OP_ADD_UNICODE

The compiler does some optimisation before any code runs:

• Constant folding: expressions made only of constants are computed at compile time, as long as the result is small (to avoid building a 10 MB string at compile time).
• Tuple constants: a literal list or set used only for membership (x in [1, 2, 3]) or iteration becomes a constant tuple or frozenset.
• Dead code: code after return or inside if 0: is removed.
• Jump threading and removal of redundant NOPs.

import dis

def consts(x):
    a = 24 * 60 * 60
    b = "ab" * 3
    c = x in [1, 2, 3]
    d = x in {1, 2, 3}
    if 0:
        print("never compiled")
    return a, b, c, d

print(consts.__code__.co_consts)
print([i.opname for i in dis.get_instructions(consts) if "CALL" in i.opname or "PRINT" in i.opname])

(None, 86400, 'ababab', (1, 2, 3), frozenset({1, 2, 3}))
[]

The constants already hold 86400, 'ababab', the tuple (1, 2, 3) and the frozenset, and no call to print survives.

Zero-cost exceptions

Before 3.11, entering a try block executed a SETUP_FINALLY instruction that pushed a block onto a stack, so even a try that never raised cost something. Since 3.11 the compiler instead records an exception table in the code object: ranges of instruction offsets and the handler to jump to. Entering a try block costs nothing; the table is consulted only when an exception is actually raised.

import dis

def safe_div(a, b):
    try:
        return a / b
    except ZeroDivisionError:
        return None

dis.dis(safe_div)

  3           0 RESUME                   0

  4           2 NOP

  5           4 LOAD_FAST                0 (a)
              6 LOAD_FAST                1 (b)
              8 BINARY_OP               11 (/)
             12 RETURN_VALUE
        >>   14 PUSH_EXC_INFO

  6          16 LOAD_GLOBAL              0 (ZeroDivisionError)
             26 CHECK_EXC_MATCH
             28 POP_JUMP_IF_FALSE        3 (to 36)
             30 POP_TOP

  7          32 POP_EXCEPT
             34 RETURN_CONST             0 (None)

  6     >>   36 RERAISE                  0
        >>   38 COPY                     3
             40 POP_EXCEPT
             42 RERAISE                  1
ExceptionTable:
  4 to 10 -> 14 [0]
  14 to 30 -> 38 [1] lasti
  36 to 36 -> 38 [1] lasti

The ExceptionTable at the bottom says "if anything between offsets 4 and 10 raises, jump to 14". There is no setup instruction at the start of the try (only a NOP that keeps the line number for tracing).

• Pipeline: tokens → AST (PEG parser) → symbol table → CFG → bytecode in a code object → eval loop in ceval.c.
• Code objects are immutable (co_code, co_consts, co_names, co_varnames, co_stacksize, co_exceptiontable); use code.replace() for a modified copy.
• Function object = code object + globals + defaults + closure + __dict__.
• CPython is a stack machine; dis.dis(fn) shows instructions, dis.dis(fn, adaptive=True) shows specialised ones.
• 3.11+: frames live on a per-thread data stack; frame objects are created lazily for tracebacks and debuggers.
• PEP 659 specialisation: LOAD_ATTR_INSTANCE_VALUE, BINARY_OP_ADD_INT, LOAD_GLOBAL_MODULE… guarded by type versions, de-specialised on repeated misses. Keep hot code type-stable.
• Compile-time: constant folding (small results only), list/set literals in in become tuple/frozenset constants, dead code removed. No reordering of a * 24 * 60.
• 3.11+ zero-cost try: an exception table replaces SETUP_FINALLY; raising is still expensive.
• Bytecode and .pyc magic numbers change every minor version; never rely on them across versions.

Every object's ob_refcnt counts the references to it. The interpreter increments it (Py_INCREF) whenever a new reference is created, by binding a name, storing into a container or pushing onto the value stack, and decrements it (Py_DECREF) when a reference goes away. When the count reaches zero, Py_DECREF immediately calls the type's deallocator, which decrements everything the object refers to (possibly freeing those too) and returns the memory.

import sys

data = []
print(sys.getrefcount(data))      # +1 for the argument
alias = data
holder = [data, data]
print(sys.getrefcount(data))
del alias
holder.clear()
print(sys.getrefcount(data))

2
5
2

The consequences are what make CPython's memory behaviour predictable:

• Deterministic destruction: an object without cycles is freed at the exact moment its last reference goes, so files closed in __del__ or by going out of scope are closed promptly (on CPython; other implementations do not promise this).
• Cost on every operation: each reference change is a memory write, which is why immortal objects (Chapter 1) and the free-threaded build's biased refcounting matter.
• Cycles leak: objects that refer to each other keep each other's counts above zero forever.

class Resource:
    def __init__(self, name):
        self.name = name
    def __del__(self):
        print("freed", self.name)

def work():
    r = Resource("local")
    print("returning")

work()
print("after call")
x = Resource("global")
x = None
print("after rebinding")

returning
freed local
after call
freed global
after rebinding

"freed local" is printed before "after call" because the frame's reference was the last one. Rebinding x frees the second object on the spot.

To reclaim cycles, CPython has a tracing garbage collector in the gc module. It only looks at container objects (lists, dicts, sets, instances, functions …) because only containers can form cycles. An int or a string can never be part of a cycle, so they are not tracked at all, and CPython even untracks containers that hold only atomic values:

import gc
print(gc.is_tracked(42), gc.is_tracked("text"))
print(gc.is_tracked([]), gc.is_tracked({}), gc.is_tracked({"a": 1}), gc.is_tracked({"a": []}))
t = tuple(range(3))
print(gc.is_tracked(t), end=" ")
gc.collect()
print(gc.is_tracked(t), gc.is_tracked(([],)))

False False
True False False True
True False True

An empty dict and a dict of ints are not tracked; a dict that holds a list is. Tuples are handled lazily: a new tuple starts tracked, and the collector untracks it the first time a collection finds that it holds only atomic values.

How it finds garbage

A collection works on a set of tracked containers:

1. Copy each object's refcount into a scratch field gc_refs.
2. For every object in the set, visit each object it references (tp_traverse) and subtract 1 from that target's gc_refs. After this, gc_refs counts only references coming from outside the set.
3. Objects with gc_refs > 0 are definitely reachable from outside. Everything reachable from them is reachable too.
4. Whatever is left is only referenced from inside the set: unreachable cycles. Run their finalizers, then break the cycles with tp_clear, and normal refcounting frees them.

import gc, weakref

class Node:
    def __init__(self, name):
        self.name = name
        self.other = None

a, b = Node("a"), Node("b")
a.other, b.other = b, a
probe = weakref.ref(a)
del a, b
print("alive after del:", probe() is not None)
print("collected:", gc.collect() >= 2)
print("alive after collect:", probe() is not None)

alive after del: True
collected: True
alive after collect: False

Generations

Most objects die young, so the collector is generational. New containers start in generation 0. Each collection that an object survives moves it to the next generation (0 → 1 → 2), and older generations are scanned less often:

• Generation 0 is collected when (allocations − deallocations) of tracked containers exceeds threshold0 (700).
• Generation 1 is collected after threshold1 (10) generation-0 collections, and generation 2 after threshold2 (10) generation-1 collections, with an extra rule: a full collection only runs if the number of objects waiting in the young generations is at least 25% of the long-lived ones, which keeps it from going quadratic in programs with millions of objects.

import gc
print(gc.get_threshold())
gc.collect()
print(gc.get_count())
junk = [[] for _ in range(500)]
print(gc.get_count()[0] >= 500)
gc.collect()
print(gc.get_stats()[2]["collections"] >= 1)

(700, 10, 10)
(0, 0, 0)
True
True

gc.get_count() shows how many allocations each generation has accumulated since its last collection. gc.freeze() (3.7+) moves everything into a permanent generation that is never scanned, which pre-fork servers use so that the collector does not touch, and therefore copy, pages shared with child processes.

__del__ is a finalizer: it runs when the object is about to be destroyed, either because its refcount hit zero or because the collector is freeing its cycle. Since 3.4 (PEP 442) objects with __del__ inside cycles are collected normally; before that they were left in gc.garbage. A finalizer still has sharp edges:

• It can run at any point where a reference is dropped, including in the middle of another operation or during interpreter shutdown, when module globals may already be None.
• Exceptions raised in it are not propagated; they are printed to stderr as "Exception ignored in …".
• It can resurrect the object by storing self somewhere. PEP 442 guarantees __del__ runs at most once per object.

class Bad:
    def __del__(self):
        raise RuntimeError("boom in __del__")

b = Bad()
del b
print("program continues")

Exception ignored in: <function Bad.__del__ at 0x…>
Traceback (most recent call last):
  File "main.py", line 3, in __del__
    raise RuntimeError("boom in __del__")
RuntimeError: boom in __del__
program continues

weakref.finalize is the safer tool: it registers a callback that runs when the object dies or at exit, does not keep the object alive, and runs at most once.

Weak references

A weak reference points at an object without increasing its refcount. Calling it returns the object while it is alive and None afterwards. Weak references are how caches and observer lists avoid keeping things alive just because they are cached:

import weakref, gc

class Image:
    def __init__(self, name):
        self.name = name

cache = weakref.WeakValueDictionary()
img = Image("logo.png")
cache["logo"] = img
print(list(cache.keys()))
del img
print(list(cache.keys()))

events = []
obj = Image("tmp")
weakref.finalize(obj, events.append, "finalized tmp")
del obj
print(events)
try:
    weakref.ref(42)
except TypeError as e:
    print("TypeError:", e)

['logo']
[]
['finalized tmp']
TypeError: cannot create weak reference to 'int' object

Not every type supports weak references: int, str, tuple and list do not, and a class with __slots__ needs "__weakref__" in its slots to support them.

Python programs allocate huge numbers of small, short-lived objects, which general-purpose malloc handles poorly. CPython therefore sends every request of 512 bytes or less to its own allocator, pymalloc, and passes larger ones to the system malloc:

• An arena is a 1 MiB chunk obtained from the OS with mmap (256 KiB before 3.10).
• An arena is divided into pools of 16 KiB (4 KiB before 3.10). Each pool serves exactly one size class.
• A pool is divided into blocks of its size class. Size classes are multiples of 16 bytes (16, 32, … 512), so there are 32 of them.

A request for 40 bytes is rounded up to the 48-byte class and served from a pool of 48-byte blocks. Freed blocks go onto that pool's free list and are reused for the next request of that class, which is very fast and explains the id reuse from Chapter 1.

import tracemalloc

tracemalloc.start()
before = tracemalloc.get_traced_memory()[0]
items = [str(i) * 3 for i in range(10_000)]
after = tracemalloc.get_traced_memory()[0]
print("about", (after - before) // 10_000, "bytes per item")
snapshot = tracemalloc.take_snapshot()
top = snapshot.statistics("lineno")[0]
print(top.traceback[0].lineno, top.count >= 10_000)
tracemalloc.stop()

about 61 bytes per item
5 True

tracemalloc hooks the allocator and records where each block was allocated, which makes it the first tool to reach for when memory grows: take two snapshots and compare them with snapshot.compare_to.

Why memory is not returned to the OS

pymalloc can give an arena back to the OS only when every pool in it is empty. A program that allocates a million small objects and frees 99% of them may still hold most of its arenas, because a few surviving objects are scattered across them. The process's resident memory then stays high even though Python considers the memory free and will reuse it for new objects. Large allocations (over 512 bytes) go to the system malloc, which has its own rules about returning memory.

• Refcounting frees an object the moment its count hits zero; deallocation cascades to what it referenced.
• Only containers are tracked by gc; containers of atomic values may be untracked (gc.is_tracked).
• Cycle detection: subtract internal references from refcount copies; whatever has zero external references is garbage.
• Generations 0/1/2 with thresholds (700, 10, 10); full collections also need 25% growth of long-lived objects. gc.freeze() for pre-fork servers.
• gc.disable() stops only cycle collection; refcounting still runs.
• __del__: runs at most once (PEP 442), may resurrect, exceptions are only printed, timing not guaranteed outside CPython. Prefer with plus weakref.finalize.
• Weak references: weakref.ref, WeakValueDictionary, WeakKeyDictionary, WeakSet. int, str, tuple, list cannot be weakly referenced; __slots__ classes need __weakref__.
• pymalloc: requests ≤ 512 bytes, 32 size classes of 16 bytes, 16 KiB pools, 1 MiB arenas (3.10+). Arenas go back to the OS only when completely empty.
• Find growth with tracemalloc snapshots and compare_to; RSS staying high after frees is usually fragmentation.

A list object is a header plus a pointer, ob_item, to a separate C array of PyObject*. ob_size is the number of items in use and allocated is the capacity of the array. Items are never stored inline; a list of a million ints is a million pointers to int objects.

When an append finds the array full, CPython grows it to roughly 1.125 times the new size plus a small constant, rounded to a multiple of 4. In 3.12 the formula in list_resize is (newsize + (newsize >> 3) + 6) & ~3. Growing by a fixed factor is what makes append amortised O(1): the total copying done over n appends is proportional to n.

import sys

items = []
caps = []
last = None
for i in range(80):
    cap = (sys.getsizeof(items) - sys.getsizeof([])) // 8
    if cap != last:
        caps.append(cap)
        last = cap
    items.append(i)
print(caps)

[0, 4, 8, 16, 24, 32, 40, 52, 64, 76, 92]

Each capacity is the size reached when the previous one filled up. The small 1.125 factor wastes little memory, at the cost of more frequent reallocations than, say, the factor of 2 many C++ standard libraries use for std::vector.

What each operation costs

import timeit
from collections import deque

n = 50_000
t_list = timeit.timeit("while a: a.pop(0)", setup=f"a = list(range({n}))", number=1)
t_deque = timeit.timeit("while a: a.popleft()", setup=f"from collections import deque; a = deque(range({n}))", number=1)
print("list.pop(0) at least 5x slower:", t_list > 5 * t_deque)

list.pop(0) at least 5x slower: True

Using a list as a FIFO queue turns a linear algorithm quadratic. collections.deque is the fix (below).

Timsort

list.sort and sorted use Timsort (since 2.3; the merge policy was improved to "powersort" in 3.11). It scans for runs that are already ascending (or strictly descending, which it reverses), extends short runs to a minimum length with binary insertion sort, and merges runs using a stack with rules that keep merges balanced. Merging uses galloping: when one run keeps winning, it switches to exponential search to copy whole chunks. The result is stable, O(n) on sorted or reverse-sorted input, and very fast on partially ordered real-world data.

records = [("bob", 2), ("amy", 1), ("cat", 2), ("dan", 1)]
by_score = sorted(records, key=lambda r: r[1])
print(by_score)
print(sorted(sorted(records), key=lambda r: r[1]) == sorted(records, key=lambda r: (r[1], r[0])))

[('amy', 1), ('dan', 1), ('bob', 2), ('cat', 2)]
True

Stability means equal keys keep their input order, so sorting by a secondary key first and then by the primary key gives a correct multi-key sort.

A tuple stores its item pointers inside the object, right after the header, because its size never changes. That saves the separate allocation a list needs and makes a tuple smaller:

import sys
print(sys.getsizeof((1, 2, 3)), sys.getsizeof([1, 2, 3]))
print(sys.getsizeof(()), sys.getsizeof((1,)))
empty_a, empty_b = (), tuple()
print(empty_a is empty_b, tuple([]) is empty_a)

64 88
40 48
True True

The empty tuple is a singleton. CPython also keeps free lists of recently freed tuples for each length below 20, so creating and destroying small tuples (as function arguments and multiple returns do) rarely touches the allocator.

"Immutable" means the tuple's slots cannot be rebound. The objects in them can still be mutable, and a tuple is only hashable if all its items are:

t = (1, [2, 3])
t[1].append(4)
print(t)
try:
    hash(t)
except TypeError as e:
    print("TypeError:", e)
print(hash((1, (2, 3))) == hash((1, (2, 3))))

(1, [2, 3, 4])
TypeError: unhashable type: 'list'
True

Since 3.6 (and guaranteed by the language since 3.7), a dict keeps keys in insertion order. CPython does it with a layout called the compact dict, which uses two arrays:

• An index table of size 2^k, where each slot holds a small integer (1, 2, 4 or 8 bytes depending on the table size) pointing into the entries array, or a marker for "empty" or "deleted".
• A dense entries array of (hash, key, value) triples, appended to in insertion order.

A lookup hashes the key, uses the low bits to pick an index slot, follows it to an entry, and compares the stored hash and then the key with is and ==. On a collision it probes another slot. Iteration just walks the entries array, which is why it is ordered and fast.

The compact layout uses less memory than the old one (which kept a full 24-byte entry in every slot, mostly empty), and it keeps ordering for free.

Probing, load factor and resizing

CPython uses open addressing: all entries live in the one table, and a collision is resolved by probing other slots. The probe sequence is i = (5*i + 1 + perturb) mod size, with perturb starting as the full hash and shifted right by 5 bits each step, so every bit of the hash eventually influences the probe, not just the low bits.

The table is kept at most two-thirds full. When an insert would pass that, the dict is resized to the next power of two that leaves room (roughly 3× the number of items) and every entry is re-inserted:

import sys

d = {}
last = sys.getsizeof(d)
print(0, last)
for i in range(50):
    d[i] = i
    size = sys.getsizeof(d)
    if size != last:
        print(len(d), size)
        last = size

0 64
1 224
6 352
11 632
22 1168
43 2264

A dict never shrinks when you delete keys. Deleted entries become "dummy" markers so that probe chains stay intact, and the space is reclaimed only on the next resize, by clear(), or by building a new dict:

import sys
d = {i: i for i in range(1000)}
full = sys.getsizeof(d)
for i in range(990):
    del d[i]
print(sys.getsizeof(d) == full, len(d))
print(sys.getsizeof(dict(d)) < full)

True 10
True

Hashing

hash(x) must satisfy one rule: if a == b then hash(a) == hash(b). The reverse is not required; different objects may share a hash (a collision) and only cost extra probes. A few details show up in interviews:

print(hash(1), hash(1.0), hash(True))
print(hash(-1), hash(-2))
print(hash(2**61 - 1), hash(2**61))
print(hash(float("inf")), hash(0.5))

1 1 1
-2 -2
0 1
314159 1152921504606846976

• Numbers that are equal hash equally across types, so 1, 1.0 and True are one dict key.
• Integer hashes are computed modulo the Mersenne prime 2⁶¹ − 1, so huge ints wrap around.
• -1 is reserved as the error return value of the C-level hash function, so hash(-1) is replaced with -2.
• str and bytes hashes are randomised per process (SipHash with a random key) to stop attackers from crafting keys that all collide. Set PYTHONHASHSEED to make them repeatable.

A type with a constant __hash__ turns every insertion into a long probe chain, and the dict degrades to O(n) per operation:

import timeit

class Key:
    def __init__(self, v):
        self.v = v
    def __eq__(self, other):
        return self.v == other.v

class BadKey(Key):
    def __hash__(self):
        return 42

class GoodKey(Key):
    def __hash__(self):
        return hash(self.v)

for cls in (GoodKey, BadKey):
    t = timeit.timeit(lambda: {cls(i): i for i in range(400)}, number=5)
    print(cls.__name__, "slow" if t > 0.05 else "fast")

GoodKey fast
BadKey fast

Key-sharing dicts and instance attributes

Instances of the same class usually have the same attribute names. PEP 412 (3.3) let their __dict__s share one table of keys and store only the values per instance. In 3.11 and 3.12 CPython goes further: an instance's attributes are stored in an inline values array laid out according to the class's shared keys, and a real __dict__ object is created only if someone asks for it. This is what makes LOAD_ATTR_INSTANCE_VALUE (Chapter 3) possible. Adding attributes in a different order in different instances, or adding many attributes outside __init__, can defeat the sharing.

A set is a hash table of keys only, using the same equal-means-equal-hash rule. It does not use the compact layout: it keeps a single sparse table and probes linearly for a few slots before jumping, which is good for the cache when testing membership. Because there is no entries array, iteration follows table order, which is why sets are unordered:

print({3, 1, 2})
print({100, 33, 1, 64})
print(list({"b": 1, "a": 2}), list(dict.fromkeys([3, 1, 3, 2])))

{1, 2, 3}
{64, 33, 100, 1}
['b', 'a'] [3, 1, 2]

Small ints hash to themselves, so a set of small ints often looks sorted. That is a coincidence of the table layout, not a guarantee; strings appear in a different order on every run because of hash randomisation.

Set operations cost what you would expect from hashing: x in s is O(1) on average, a | b is O(len(a) + len(b)), and a & b iterates over the smaller set and probes the larger one, so it is O(min(len(a), len(b))).

collections.deque is a doubly linked list of blocks, each holding 64 item pointers. Appending or popping at either end only touches the end block, so both ends are O(1). Indexing near the middle has to walk blocks from the nearer end, so d[i] is O(n) in the worst case, and there is no slicing.

from collections import deque

d = deque(range(5), maxlen=5)
d.append(5)
d.appendleft(-1)
print(d)
d.rotate(2)
print(d, d[0], d[-1])

deque([-1, 1, 2, 3, 4], maxlen=5)
deque([3, 4, -1, 1, 2], maxlen=5) 3 2

With maxlen set, adding at one end silently drops an item from the other, which makes a bounded deque a ready-made sliding window or "last N items" buffer.

Other tools worth knowing:

• heapq: a binary min-heap stored in a plain list (heap[k] <= heap[2k+1], heap[2k+2]). heappush/heappop are O(log n); heapify is O(n).
• bisect: binary search on a sorted list. Finding the position is O(log n), but insort is O(n) because inserting into the list shifts items.
• Counter, defaultdict and OrderedDict are dict subclasses. OrderedDict still matters for move_to_end and order-sensitive equality.

import heapq, bisect

tasks = [(3, "write"), (1, "plan"), (2, "test")]
heapq.heapify(tasks)
print([heapq.heappop(tasks)[1] for _ in range(3)])
print(heapq.nlargest(2, [5, 1, 9, 3]))
scores = [10, 20, 30, 40]
print(bisect.bisect_left(scores, 25), bisect.bisect_right(scores, 30))

['plan', 'test', 'write']
[9, 5]
2 3

• list: header + separate array of pointers; growth (n + (n >> 3) + 6) & ~3 → capacities 0, 4, 8, 16, 24, 32, 40, 52, 64, 76…; append amortised O(1); front insert/pop O(n).
• Timsort: stable, finds runs, galloping merges; O(n) on sorted input. Multi-key sort = sort by secondary, then by primary.
• tuple: items inline, empty tuple singleton, free lists for lengths below 20; hashable only if all items are.
• dict: compact layout (sparse index table + dense entries), insertion-ordered, load ≤ 2/3, resize to a power of two, never shrinks on delete, tombstones for deleted keys.
• Probing: i = (5*i + 1 + perturb) mod 2^k, perturb >>= 5.
• Hash rules: equal ⇒ same hash; hash(1) == hash(1.0) == hash(True); hash(-1) == -2; ints mod 2^61 − 1; str/bytes randomised per process.
• Defining __eq__ without __hash__ makes instances unhashable. Never mutate a key's hashed fields.
• set: keys-only sparse table, unordered; & iterates the smaller set. Use dict.fromkeys for ordered de-duplication.
• deque: blocks of 64 pointers, O(1) at both ends, O(n) in the middle, maxlen for windows.
• heapq (min-heap in a list), bisect (O(log n) search, O(n) insert), Counter, defaultdict, OrderedDict.move_to_end.

Since 3.3 (PEP 393), CPython stores each string's characters in a fixed-width array whose width is picked from the largest code point in the string:

Every character occupies the same number of bytes, so s[i] is a direct array access and len(s) is stored in the header. Both are O(1). An ASCII string has a 40-byte header; any other kind uses a 56-byte header, which has room for a cached UTF-8 copy. A terminating NUL character is always included.

import sys
samples = {
    "ascii": "a" * 100,
    "latin-1": "é" * 100,
    "ucs-2": "ā" * 100,
    "ucs-4": "😀" * 100,
    "one emoji": "a" * 99 + "😀",
}
for name, s in samples.items():
    print(f"{name:>9}: len {len(s)}, {sys.getsizeof(s)} bytes")

    ascii: len 100, 141 bytes
  latin-1: len 100, 157 bytes
    ucs-2: len 100, 258 bytes
    ucs-4: len 100, 460 bytes
one emoji: len 100, 460 bytes

The last line is the surprise: a single emoji forces the whole string to 4 bytes per character, so 99 ASCII letters plus one emoji take as much memory as 100 emoji.

Strings are immutable

Every string method returns a new string. Immutability is what allows strings to be hashed (and the hash to be cached in the object after the first computation), interned and shared safely between threads.

s = "hello"
try:
    s[0] = "H"
except TypeError as e:
    print("TypeError:", e)
t = s.replace("h", "H")
print(s, t, s is t)
u = s.replace("z", "Z")
print(u is s)

TypeError: 'str' object does not support item assignment
hello Hello False
True

When a method has nothing to change, CPython often returns the original object (replace with no match returns s itself). That is an optimisation you can see with is, not a guarantee.

Because strings are immutable, s = s + t must allocate a new string and copy both parts. Doing that n times in a loop copies 1 + 2 + … + n characters, which is O(n²).

CPython has an optimisation for the common case: when the left operand of += is a local variable and this is the only reference to the string, it resizes the string in place with realloc, which is usually amortised O(1). The moment any other reference exists, the optimisation is off and the loop becomes quadratic:

import timeit

def build_plus(n):
    s = ""
    for _ in range(n):
        s += "x"
    return s

def build_plus_shared(n):
    s = ""
    snapshots = []
    for _ in range(n):
        snapshots.append(s)    # a second reference to s
        s += "x"
    return s

def build_join(n):
    return "".join("x" for _ in range(n))

n = 20_000
t_plus = timeit.timeit(lambda: build_plus(n), number=3)
t_shared = timeit.timeit(lambda: build_plus_shared(n), number=3)
t_join = timeit.timeit(lambda: build_join(n), number=3)
print("shared += is 10x slower:", t_shared > 10 * t_plus)
print("join within 3x of fast +=:", t_join < 3 * t_plus)

shared += is 10x slower: True
join within 3x of fast +=: True

str.join computes the total length first, allocates once and copies each piece once, so it is O(total length) on every implementation. That is why the standard advice is to collect pieces in a list and join at the end, or to use io.StringIO.

Formatting

f-strings compile to dedicated bytecode (FORMAT_VALUE and BUILD_STRING), so they are usually the fastest way to format. Since 3.12 (PEP 701) they are parsed by the real grammar, so you can reuse the same quote character and write comments and backslashes inside the braces:

user = {"name": "Ada", "score": 0.91234}
print(f"{user["name"]} scored {user["score"]:.1%}")
width = 8
print(f"[{'left':<{width}}] [{'right':>{width}}] [{42:08b}]")
x = 3
print(f"{x = }, {x * 2 = }")

Ada scored 91.2%
[left    ] [   right] [00101010]
x = 3, x * 2 = 6

The = specifier (3.8+) prints the expression text and its value, which is handy for debugging.

Text and binary data are separate types in Python 3:

• str is text: code points. It has no byte length until you encode it.
• bytes is an immutable sequence of integers 0–255. b[0] is an int, not a one-byte bytes.
• bytearray is the mutable version, with the same over-allocation strategy as list, so appending is amortised O(1).
• memoryview is a window onto any object that supports the buffer protocol (bytes, bytearray, array.array, NumPy arrays). Slicing a memoryview does not copy.

data = "naïve café".encode("utf-8")
print(len("naïve café"), len(data), data[:6], data[2])
print(data.decode("utf-8"), data.decode("latin-1"))

buf = bytearray(b"hello world")
buf[0] = ord("H")
buf.extend(b"!")
print(buf, buf.upper())

view = memoryview(buf)[6:11]
view[:] = b"WORLD"
print(buf, view.nbytes, view.obj is buf)

10 12 b'na\xc3\xafve' 195
naïve café naïve café
bytearray(b'Hello world!') bytearray(b'HELLO WORLD!')
bytearray(b'Hello WORLD!') 5 True

Decoding UTF-8 bytes as Latin-1 never fails (every byte is a valid Latin-1 character) but produces "mojibake" such as naïve. Writing through the memoryview changed the underlying bytearray in place, with no copy.

Why memoryview matters

Slicing bytes or bytearray creates a copy. A parser that slices a large buffer repeatedly therefore copies over and over. A memoryview slice is O(1) and shares memory:

import timeit

payload = bytes(10_000_000)
t_copy = timeit.timeit(lambda: payload[1:], number=20)
mv = memoryview(payload)
t_view = timeit.timeit(lambda: mv[1:], number=20)
print("view slicing 100x faster:", t_view * 100 < t_copy)
print(mv[1:].nbytes, mv.readonly)

view slicing 100x faster: True
9999999 True

Sockets (sock.recv_into), files (readinto) and struct.unpack_from all accept buffers, so a network server can fill one pre-allocated bytearray and parse it through memoryviews without ever copying.

Encodings

UTF-8 encodes each code point in 1 to 4 bytes: ASCII stays 1 byte, most European and Middle Eastern letters take 2, most other BMP characters 3, and emoji 4. It is the default for encode() and decode(). open() without encoding= still uses the locale's encoding in 3.12 (PEP 686 makes UTF-8 the default from 3.15), so always pass encoding="utf-8" for files that must work on every machine.

for ch in ["A", "é", "€", "😀"]:
    print(ch, hex(ord(ch)), len(ch.encode("utf-8")), ch.encode("utf-8"))
print("€".encode("utf-16-le"), len("😀".encode("utf-16-le")))
try:
    "€".encode("ascii")
except UnicodeEncodeError as e:
    print("UnicodeEncodeError:", e.reason)
print("€".encode("ascii", errors="replace"), "€".encode("ascii", errors="xmlcharrefreplace"))
print(b"\xff\xfe".decode("utf-8", errors="replace"))

A 0x41 1 b'A'
é 0xe9 2 b'\xc3\xa9'
€ 0x20ac 3 b'\xe2\x82\xac'
😀 0x1f600 4 b'\xf0\x9f\x98\x80'
b'\xac ' 4
UnicodeEncodeError: ordinal not in range(128)
b'?' b'€'
��

One visible character is not one code point

What a user sees as one character (a grapheme cluster) can be several code points: a base letter plus combining accents, an emoji with a skin-tone modifier, or a family emoji joined with zero-width joiners. len() counts code points:

family = "👨‍👩‍👧"
print(family, len(family), len(family.encode()))
print([f"U+{ord(c):04X}" for c in family])
print(family[::-1] == family, len(family[:2]))

👨‍👩‍👧 5 18
['U+1F468', 'U+200D', 'U+1F469', 'U+200D', 'U+1F467']
False 2

Reversing or slicing such a string by code points breaks the cluster apart. Correct grapheme handling needs a library such as regex (with \X) or grapheme.

The same text, two encodings in code points

é can be the single code point U+00E9 or e followed by the combining acute accent U+0301. They look identical, but they are not equal until you normalise them:

import unicodedata

composed = "café"
decomposed = "café"
print(composed == decomposed, len(composed), len(decomposed))
nfc = unicodedata.normalize("NFC", decomposed)
print(nfc == composed, len(nfc))
print(unicodedata.name("́"))

False 4 5
True 4
COMBINING ACUTE ACCENT

Normalise user input (usually to NFC) before comparing, hashing or using it as a dict key. macOS file names, for example, have historically been stored decomposed.

Case and digits

lower() is not the right tool for case-insensitive comparison. casefold() applies the full Unicode folding rules, and some mappings change the length of the string:

print("Straße".lower(), "Straße".casefold(), "Straße".upper())
print("STRASSE".casefold() == "Straße".casefold())
print(len("İ".lower()), "fi".upper())
print("²".isdigit(), "²".isdecimal(), "٣".isdecimal(), int("٣") + 1)

straße strasse STRASSE
True
2 FI
True False True 4

isdigit() accepts superscripts that int() cannot parse; isdecimal() is the check that matches what int() accepts, and int() happily parses Arabic-Indic digits. Validating input with isdigit() and then calling int() is a classic crash.

• str = immutable code points. PEP 393 width per string: ASCII/Latin-1 1 byte, UCS-2 2, UCS-4 4. ASCII header 40 bytes, others 56. One emoji widens the whole string.
• len(s) and s[i] are O(1). UTF-8 is a separate encoding (s.encode()).
• Methods return new strings; unchanged results may return the same object.
• s += t in a loop is fast only for an unshared local in CPython; use "".join(parts) or io.StringIO.
• f-strings are the fastest formatting; 3.12 allows nested same quotes. f"{x = }" for debugging.
• bytes immutable (b[0] is an int), bytearray mutable and over-allocated, memoryview zero-copy slices over the buffer protocol.
• UTF-8: 1–4 bytes per code point; continuation bytes are 10xxxxxx. Latin-1 decodes any bytes. Pass encoding="utf-8" to open().
• Graphemes ≠ code points (combining marks, ZWJ emoji). Normalise (NFC/NFKC) before comparing; use casefold() for caseless matching.
• isdecimal() matches int(); isdigit() accepts superscripts that int() rejects.

Every operator and many built-in functions translate into a special method:

The important detail is in the first column of every row: CPython looks special methods up on the type, skipping the instance's own __dict__. At the C level each type has slots (tp_as_number->nb_add, tp_as_sequence->sq_length …) that are filled from the class's dunder methods when the class is created or modified, and the interpreter calls the slot directly.

class Box:
    def __len__(self):
        return 3

b = Box()
b.__len__ = lambda: 99          # an instance attribute
print(len(b), b.__len__())

Box.__len__ = lambda self: 7    # changing the class updates the slot
print(len(b))

3 99
7

len(b) ignores the instance attribute, while the explicit b.__len__() is an ordinary attribute lookup and finds it. Assigning to the class works because type.__setattr__ notices dunder names and refreshes the C slot.

class Proxy:
    def __init__(self, target):
        self._target = target
    def __getattr__(self, name):
        return getattr(self._target, name)

p = Proxy([1, 2, 3])
print(p.count(2), p.__len__())
try:
    len(p)
except TypeError as e:
    print("TypeError:", e)

1 3
TypeError: object of type 'Proxy' has no len()

A transparent proxy has to define every special method it wants to forward explicitly, which is why libraries such as wrapt exist.

For a + b, Python follows these rules:

1. If type(b) is a subclass of type(a) and overrides __radd__, try b.__radd__(a) first. This lets a subclass control mixed operations with its base.
2. Otherwise try a.__add__(b).
3. If that method is missing or returns the special singleton NotImplemented, try b.__radd__(a) (only if the types differ).
4. If both give NotImplemented, raise TypeError.

Returning NotImplemented (not raising NotImplementedError) is how a method says "I do not know how to handle this type, ask the other operand".

class Money:
    def __init__(self, cents):
        self.cents = cents
    def __add__(self, other):
        if isinstance(other, Money):
            return Money(self.cents + other.cents)
        if isinstance(other, int):
            return Money(self.cents + other)
        return NotImplemented
    def __radd__(self, other):
        return self.__add__(other)
    def __repr__(self):
        return f"Money({self.cents})"

print(Money(5) + Money(7), Money(5) + 3, 3 + Money(5))
print(sum([Money(1), Money(2)]))
try:
    Money(1) + "x"
except TypeError as e:
    print("TypeError:", e)

Money(12) Money(8) Money(8)
Money(3)
TypeError: unsupported operand type(s) for +: 'Money' and 'str'

3 + Money(5) works because int.__add__ returns NotImplemented for a Money, so Python calls Money.__radd__. sum starts from 0, so it also relies on __radd__.

Augmented assignment

a += b tries a.__iadd__(b) first. If it is missing or returns NotImplemented, Python falls back to a = a + b (with the full __add__/__radd__ dance). Mutable types implement __iadd__ to modify themselves and return self; immutable types do not define it, so += creates a new object (Chapter 1).

The subclass rule

class Base:
    def __add__(self, other):
        return "Base.__add__"
    def __radd__(self, other):
        return "Base.__radd__"

class Derived(Base):
    def __radd__(self, other):
        return "Derived.__radd__"

print(Base() + Derived())
print(Derived() + Base())

Derived.__radd__
Base.__add__

Even though Base is on the left, Derived.__radd__ wins, because the right operand's type is a subclass that overrides the reflected method.

Rich comparisons

==, !=, <, <=, >, >= call __eq__, __ne__, __lt__, __le__, __gt__, __ge__. Their reflections are swapped: if a < b gets NotImplemented, Python tries b > a. For ==, the final fallback when both sides return NotImplemented is an identity comparison, so == never raises TypeError. __ne__ by default inverts __eq__.

from functools import total_ordering

@total_ordering
class Version:
    def __init__(self, text):
        self.parts = tuple(int(p) for p in text.split("."))
    def __eq__(self, other):
        if not isinstance(other, Version):
            return NotImplemented
        return self.parts == other.parts
    def __lt__(self, other):
        if not isinstance(other, Version):
            return NotImplemented
        return self.parts < other.parts
    def __hash__(self):
        return hash(self.parts)
    def __repr__(self):
        return ".".join(map(str, self.parts))

vs = [Version("1.10"), Version("1.2"), Version("1.9.1")]
print(sorted(vs), max(vs), Version("1.2") >= Version("1.2.0"))
print(Version("1.0") == "1.0", Version("1.0") != Version("1.0"))

[1.2, 1.9.1, 1.10] 1.10 False
False False

total_ordering derives <=, > and >= from __eq__ and __lt__. Comparing tuples of ints gives the natural version order (1.2 < 1.9.1 < 1.10), which string comparison gets wrong. Note the False for 1.2 >= 1.2.0: the tuples (1, 2) and (1, 2, 0) differ, and a shorter tuple that is a prefix of a longer one sorts first. A real version class would strip or pad trailing zeros before comparing.

Truthiness

if x: calls type(x).__bool__. If the class has no __bool__, Python uses __len__ and treats zero as false. If it has neither, the object is always true.

class Empty:
    def __len__(self):
        return 0

class Plain:
    pass

class Strict:
    def __bool__(self):
        return 1

print(bool(Empty()), bool(Plain()), bool([]), bool([0]), bool(0.0), bool("0"))
try:
    bool(Strict())
except TypeError as e:
    print("TypeError:", e)

False True False True False True
TypeError: __bool__ should return bool, returned int

__bool__ must return a real bool; returning 1 raises TypeError.

Containment and iteration fallbacks

x in obj uses __contains__ if defined. Otherwise Python iterates over obj with __iter__, and if there is no __iter__ either, it uses the old sequence protocol: call __getitem__(0), __getitem__(1) … until IndexError. So defining only __getitem__ is enough to make an object iterable and searchable:

class Squares:
    def __getitem__(self, i):
        if i >= 5:
            raise IndexError(i)
        return i * i

s = Squares()
print(list(s), 9 in s, 10 in s)
print(iter(s))

[0, 1, 4, 9, 16] True False
<iterator object at 0x…>

• __repr__ should be unambiguous, for developers. Containers use the repr of their items, and the REPL and debuggers show it. If possible it looks like an expression that rebuilds the object.
• __str__ is the readable form used by print and str(). It defaults to __repr__.
• __format__(spec) handles format specs in f-strings and format().

from datetime import date

class Temp:
    def __init__(self, c):
        self.c = c
    def __repr__(self):
        return f"Temp({self.c!r})"
    def __str__(self):
        return f"{self.c}°C"
    def __format__(self, spec):
        if spec == "f":
            return f"{self.c * 9 / 5 + 32:.1f}°F"
        return format(str(self), spec)

t = Temp(21.5)
print(t, repr(t), [t])
print(f"{t:f} | {t:>8} | {date(2026, 1, 2):%d %b}")

21.5°C Temp(21.5) [Temp(21.5)]
70.7°F |   21.5°C | 02 Jan

By default each instance has a __dict__ for its attributes (stored as inline values with shared keys in 3.11+, Chapter 5, but still with room for a dict). Declaring __slots__ replaces the per-instance dict with fixed fields at known offsets in the object, accessed through member descriptors on the class:

import sys, tracemalloc

class Plain:
    def __init__(self, x, y):
        self.x, self.y = x, y

class Slotted:
    __slots__ = ("x", "y")
    def __init__(self, x, y):
        self.x, self.y = x, y

def measure(cls, n=10_000):
    tracemalloc.start()
    objs = [cls(i, i) for i in range(n)]
    size = tracemalloc.get_traced_memory()[0]
    tracemalloc.stop()
    return size // n

print("bytes per object:", measure(Plain), measure(Slotted))
s = Slotted(1, 2)
print(type(Slotted.__dict__["x"]).__name__, hasattr(s, "__dict__"))
try:
    s.z = 3
except AttributeError as e:
    print("AttributeError:", e)

bytes per object: 120 87
member_descriptor False
AttributeError: 'Slotted' object has no attribute 'z'

The rules that trip people up:

• Slots save memory per instance and make attribute access slightly faster, but you can no longer add arbitrary attributes.
• A subclass without its own __slots__ gets a __dict__ again, so every class in the hierarchy must declare slots to keep the saving.
• Slotted instances cannot be weakly referenced unless "__weakref__" is in the slots.
• A slot name cannot also be a class attribute (the descriptor would be overwritten), so defaults go in __init__. @dataclass(slots=True) (3.10+) handles this for you.

• Implicit special method calls look on the type, not the instance, and bypass __getattr__. Changing the class's dunder updates the C slot.
• a + b: subclass's __radd__ first if it overrides; else a.__add__(b), then b.__radd__(a) on NotImplemented; else TypeError.
• Return NotImplemented for unsupported operand types; never raise NotImplementedError from an operator.
• a += b: __iadd__ (must return self), else a = a + b.
• == falls back to identity and never raises; < raises TypeError when both sides decline. __ne__ inverts __eq__. functools.total_ordering fills in the rest.
• Truthiness: __bool__ (must return bool), else __len__ != 0, else true.
• in: __contains__, else __iter__, else __getitem__(0, 1, …) until IndexError.
• __repr__ for developers, __str__ for users (defaults to repr), __format__ for f-string specs.
• __slots__: fixed fields via member descriptors, no __dict__, less memory; subclasses must redeclare, add __weakref__ for weak refs, no class-level defaults for slot names.

obj.name calls type(obj).__getattribute__(obj, "name"). For ordinary objects that is object.__getattribute__, which does this:

1. Look name up in the class and its bases, following the MRO (below). Call the result cls_attr.
2. If cls_attr is a data descriptor (its type defines __set__ or __delete__), return cls_attr.__get__(obj, type(obj)). Data descriptors win over the instance.
3. Otherwise, if name is in the instance's __dict__, return that value.
4. Otherwise, if cls_attr is a non-data descriptor (defines only __get__), return cls_attr.__get__(obj, type(obj)).
5. Otherwise, if cls_attr was found, return it as is.
6. Otherwise raise AttributeError, and if the class defines __getattr__, call __getattr__(obj, name) instead of failing.