Control flow, range и cache line behavior

for x in lst и for i in range(len(lst)): x = lst[i] дают одинаковый результат, но первый обычно на 30–50% быстрее. Это не магия и не оптимизация компилятора — это следствие двух аппаратных и языковых факторов: cache locality + меньше bytecode-инструкций на каждой итерации.

Понимание cache line (64 байта) и contiguous-memory layout — это ровно тот мост от Python к C, на котором стоят NumPy/pandas/Polars/Arrow. Без него «pandas быстрее» — магия; с ним — следствие.

Cache lines — что это

CPU читает память не по 1 байту, а блоками — cache lines. На x86_64 и aarch64 это 64 байта. Когда CPU обращается к адресу X, он подгружает в L1 cache адреса X..X+63. Следующий доступ к X+8 (8 байт дальше) — cache hit, бесплатно (~1 нс). Доступ к X+1024 — cache miss, ~100 нс (на два порядка медленнее).

Sequential prefetcher CPU агрессивно предсказывает: если вы читаете X, X+8, X+16, ..., hardware заранее загружает следующие cache lines в L1 ещё до того, как ваш код их попросит. Это делает linear scan по contiguous-memory структурам near-free.

Почему list contiguous → cache friendly

Python list — это массив PyObject* (8 байт на 64-bit). 64-байтовая cache line вмещает 8 указателей за один cache load. Iteration через for x in lst идёт по contiguous memory: при чтении ob_item[i] все 7 следующих указателей уже подгружены в L1 prefetcher’ом.

import time

lst = list(range(10**6))

# Sequential через iter (использует FOR_ITER opcode)
s = time.perf_counter()
for x in lst:
    pass
print('iter:', time.perf_counter() - s)

# Index-based (использует FOR_ITER на range + BINARY_SUBSCR на lst)
s = time.perf_counter()
for i in range(len(lst)):
    x = lst[i]
print('index:', time.perf_counter() - s)

На моём ноутбуке (CPython 3.12, aarch64): iter ~10ms, index ~20ms. Разница в ~2× стабильна. Причины:

1. Меньше bytecode-инструкций. for x in lst это GET_ITER + FOR_ITER (2 опкода/итерацию). for i in range(len): x = lst[i] — FOR_ITER (на range) + STORE_FAST i + LOAD_FAST lst + LOAD_FAST i + BINARY_SUBSCR + STORE_FAST x (~6 опкодов).
2. Те же cache patterns. Оба варианта sequential — но index-loop делает больше работы между cache loads.

Контраст: linked list. Каждый node в random heap location. Доступ к node.next — практически гарантированный cache miss. Поэтому linked list в Python нет в stdlib для performance-критичных кейсов — collections.deque использует block-allocated linked-array, чтобы получить cache locality на блоках.

range — не list

range(N) — это lazy iterable (тип range), а не list. Объект range хранит только три integer’а: start, stop, step. Не аллоцирует N integer’ов. Итератор по нему генерирует значения «на лету».

import sys
print(sys.getsizeof(range(10**9)))   # 48 байт (constant!)
print(type(range(10)))                # <class 'range'>
# print(sys.getsizeof(list(range(10**9))))  # ~8 GB — НЕ ЗАПУСКАЙТЕ

Это огромная экономия: в Python 2 был range() (eager — материализует list) и xrange() (lazy). В Python 3 объединили под именем range с lazy-семантикой, и xrange убрали.

Implications:

• for i in range(10**9) — нормально, ~48 байт памяти.
• list(range(10**9)) — катастрофа, ~8 GB.
• range поддерживает __contains__ за O(1) (через арифметику бордюров): 5 in range(10) мгновенно.
• range поддерживает slicing: range(10)[5:8] возвращает range(5, 8, 1), не материализованный list.

while vs for — bytecode level

for x in iter: компилируется в GET_ITER (один раз) + FOR_ITER (одна инструкция на iteration; завершается когда iter raises StopIteration). while True: ... break — JUMP_BACKWARD + manual condition check на каждой итерации.

Для-цикл обычно быстрее на чистом bytecode count и более идиоматичен. Используйте dis.dis(...) чтобы увидеть bytecode (см. docs.python.org/3/library/dis.html):

import dis

def f_for():
    total = 0
    for x in [1, 2, 3]:
        total += x
    return total

def f_while():
    items = [1, 2, 3]
    total = 0
    i = 0
    while i < len(items):
        total += items[i]
        i += 1
    return total

dis.dis(f_for)    # ~6-7 инструкций в loop body
dis.dis(f_while)  # ~10+ инструкций (LOAD len, COMPARE_OP, BINARY_SUBSCR, ...)

f_for побеждает по bytecode count и по cache pattern.

Cross-course context

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

1. Cache line ≈ 64 bytes на x86_64/aarch64. Sequential access → cache hits, prefetcher работает; random access → cache miss каждый шаг.
2. for x in lst обычно быстрее for i in range(len(lst)) не из-за магии, а из-за fewer bytecodes (2 vs ~6 на итерацию) и отсутствия BINARY_SUBSCR.
3. range(N) lazy, занимает ~48 байт независимо от N. list(range(N)) материализует — следите за этим различием.