Mutability vs immutability на уровне памяти и cache

В большинстве учебников mutability vs immutability подаётся как философское или функциональное понятие. Это правильно, но не полно. На уровне CPython это cache strategy: immutable structures можно safely share, интернировать (один объект — много references), reorder в памяти для locality. Это link между Python data model и NumPy/Arrow performance — те же principles работают на data engineer-стеке.

После этого урока вы должны видеть mutability/immutability как memory layout decision, а не just type-system feature, и понимать, почему NumPy ndarray быстрее Python list для numeric workloads (spoiler: cache locality + packed primitives, не «C быстрее»).

Что значит mutable / immutable

Concrete example mutable vs immutable behavior:

# mutable: один объект, несколько имён
a = [1, 2, 3]
b = a                # b ссылается на тот же list
b.append(4)
print(a)             # [1, 2, 3, 4] - 'a' тоже изменился!

# immutable: каждое присваивание создаёт новое имя на тот же объект
s = "hello"
t = s                # t - то же самое имя на ту же string
t = t + "!"          # rebinding: t теперь указывает на новый объект "hello!"
print(s)             # "hello" - не изменился
print(t)             # "hello!"

Различие критично: mutable объект может быть изменён через любой alias; immutable — никогда (rebinding имени != mutation объекта).

Hashable требует stable identity

Hashable объект должен иметь stable hash на всём времени жизни (контракт hash(x) == hash(y) если x == y). Это нужно для использования в hash table (dict key, set element). Mutable объекты не hashable потому что их state может меняться → hash сместится → объект исчезнет из контейнера, где он был ключом.

# tuple hashable - immutable
t = (1, 2, 3)
hash(t)              # OK
d = {t: "value"}     # OK как dict key

# list не hashable - mutable
l = [1, 2, 3]
hash(l)              # TypeError: unhashable type: 'list'

# frozenset hashable, set нет
fs = frozenset({1, 2, 3})
s = {1, 2, 3}
hash(fs)             # OK
hash(s)              # TypeError

Это hard constraint Python data model: вы не можете «обойти» это, объявив class MyList(list): __hash__ = id. Если объект mutable по своей природе, hash через id() (object identity) допустимо, но семантически странно — два списка с одинаковым содержимым не равны как hash-keys.

Sharing immutable safely

Множество references на immutable object — safe: никто не сможет изменить state. Это даёт enable для interning — одного физического объекта на много references:

# CPython интернирует short strings и identifiers:
a = "hello"
b = "hello"
print(a is b)        # True (interned by compiler как const)

# Маленькие int [-5, 256] - small-int cache:
x = 100
y = 100
print(x is y)        # True (cached)

# Tuple literal interning - implementation detail:
a = (1, 2, 3)
b = (1, 2, 3)
print(a is b)        # часто True в 3.10+ (bytecode constant interning), но не гарантировано

Cite: Objects/codeobject.c — co_consts могут быть shared между function calls; Objects/longobject.c — _PyLong_SMALL_INTS array; Objects/unicodeobject.c — string interning.

Mutable объекты нельзя интернировать. Если бы CPython кэшировал [1, 2, 3], то a = [1, 2, 3]; a.append(4) изменил бы кэшированный объект для всех. Поэтому каждый list literal — новый объект.

Cache locality — где immutable выигрывает

Immutable structures могут layout-optimized. Конкретные примеры:

1. NumPy ndarray — fixed-type contiguous: shape immutable, dtype immutable, values mutable но layout фиксирован. Это даёт:

• Sequential cache loads: arr[0], arr[1], ..., arr[N] — все в смежных байтах. CPU prefetcher загружает следующую cache line автоматически.
• SIMD-friendly: один vmovapd ymm0, [rdi] загружает 4 × float64 = 256 бит за инструкцию. Compiler может векторизовать arr.sum(), arr * 2, (arr1 + arr2).
• Zero per-element overhead: ровно 8 байт (для int64/float64), без PyObject header (28+ байт).

2. Apache Arrow Buffer — fully immutable: создаётся через builder, freezes для use. Это даёт:

• Zero-copy между процессами: shared memory, mmap’нутый файл — несколько процессов читают тот же buffer без синхронизации (immutable безопасен в shared memory).
• Columnar layout: каждый столбец — отдельный contiguous buffer. Predicate pushdown, vectorized execution.
• Padded для cache lines: buffer’ы выровнены к 64-byte границам — CPU читает целиком cache line за один load.

3. Python tuple — immutable, ob_item встроен в struct (см. M02-02): single allocation, header + payload в одной cache line для маленьких tuple’ов.

Когда mutable выигрывает

1. In-place updates без allocation. lst.append(x) обычно не аллоцирует (capacity headroom, см. M02-01). Mutable accumulator (build pattern):

result = []
for item in stream:
    if condition(item):
        result.append(transform(item))      # in-place, no new allocation per step

# vs immutable equivalent (медленно для больших streams):
result = ()
for item in stream:
    if condition(item):
        result = result + (transform(item),)  # каждая итерация создаёт новый tuple
                                              # суммарная работа O(n²)

Для immutable accumulator без оптимизаций work — O(n²); для mutable — O(n) amortized.

2. Modifying graph structures, caches, accumulators. dict/set операции — естественно mutable (insert, delete). Иммутабельность здесь была бы overhead’ом без бенефита.

3. Performance-critical hot loops. Если каждая «модификация» требует копирования всего контейнера — это N² work для N mutations. Mutable выигрывает.

Trade-off table

Никакого «лучшего» выбора нет — зависит от workload’а. Эмпирическое правило: input/parameters — immutable, intermediate accumulators — mutable, final output — immutable (если будет shared или сериализован).

Параллель к NumPy / Arrow / Spark / Polars

Все современные analytical-engines строят на immutability:

• NumPy ndarray — data block immutable layout (shape, dtype, strides — immutable; raw values технически mutable, но obычно treated as immutable view).
• Apache Arrow Buffer — fully immutable. Builders создают, потом freeze для use. Used by Pandas 2+, Polars, DuckDB, ClickHouse.
• Spark DataFrame — immutable. df.filter(...) возвращает новый logical plan (lazy); execution плана может cache’ить intermediate.
• Polars DataFrame — immutable lazy. Операции создают expressions, evaluation в .collect().

Все эти системы получают cache locality + safe sharing + zero-copy между threads/processes именно из-за immutability. Python tuple — simplest example принципа: single record analog того, что Arrow scaling до миллиардов записей.

import numpy as np

# Каноничный demo speedup от cache locality:
data = list(range(10**6))                   # Python list of PyLong (28+ MB)
result = sum(x**2 for x in data)            # ~100 ms на M1

arr = np.arange(10**6, dtype=np.int64)      # NumPy ndarray (8 MB)
result = (arr ** 2).sum()                   # ~1 ms на M1

# Speedup ~100x объясняется:
# 1. Memory: 8 MB vs 28+ MB (cache fits лучше)
# 2. Layout: packed int64 vs scattered PyLong*
# 3. SIMD: vectorized power и sum
# 4. No PyObject overhead на каждый int

Cross-course context

Ключевые выводы

1. Mutability vs immutability — не философия, а memory layout strategy. Immutable → hashable + safely shareable + cache-friendly + interning возможен.
2. Hashable требует stable identity: mutable не может быть hashable (hash сместился бы при mutation). list unhashable, tuple hashable; set unhashable, frozenset hashable.
3. Cache locality: immutable structures позволяют packed layout (NumPy ndarray, Arrow buffer, Python tuple flex array). NumPy/Arrow speedup 10-100x vs Python list — это memory layout, не магия компиляции.
4. Mutable выигрывает в build/accumulator paths: lst.append O(1) amort, immutable equivalent O(n²). Эмпирическое правило: input/output — immutable, intermediate — mutable.
5. NumPy/Arrow/Spark/Polars все built on immutability principle. Python tuple — simplest example принципа; Arrow Buffer — production-scale extension.

В уроке M02-07 — финальная сводка модуля: comparative big-O matrix list/tuple/dict/set + memory snapshot + decision matrix.