CPU не работает напрямую с RAM

Процессор не читает RAM напрямую — это слишком медленно. Между регистрами и RAM есть иерархия кэшей: L1, L2, L3, и только потом DRAM. Каждый уровень больше и медленнее предыдущего:

Чтение из L1 — ~4 такта. Чтение из RAM — ~200-400 тактов. В 100 раз медленнее. Если ваша программа всё время бьёт мимо кэша — она бьёт по производительности, и это не фикситcя более быстрым алгоритмом.

Как работает spatial locality

Когда CPU читает байт из RAM, он не загружает один байт. Он загружает cache line — обычно 64 байта. Это значит: если вы прочитали xs[0], то xs[1], xs[2], …, xs[15] (при 4 байтах на int) уже в L1, бесплатно. Это и есть spatial locality: рядом лежащие в памяти данные читаются вместе.

Массив (array.array, numpy.ndarray) идеально использует этот эффект: 1M int32 = 4 MB, плотно, ровно. При последовательном проходе кэш-линии загружаются по очереди, prefetcher CPU их предугадывает заранее.

Python list теряет эту локальность: в буфере лежат указатели, а сами объекты разбросаны по куче. Каждое чтение xs[i] + 1 означает: прочесть указатель (один cache miss), потом по указателю прочесть PyObject (другой cache miss, другая cache line), потом сам ob_digit. Каждое значение — отдельный «прыжок» в произвольное место памяти, никакого spatial locality.

Бенчмарк: суммирование 1M int

Сравним три структуры на одной задаче: посчитать сумму.

import time
import array
import numpy as np

N = 1_000_000

# три варианта одних и тех же данных
lst = list(range(N))
arr = array.array('i', range(N))
ndarr = np.arange(N, dtype='int32')

def measure(fn, repeats=10):
    t0 = time.perf_counter()
    for _ in range(repeats):
        fn()
    t1 = time.perf_counter()
    return (t1 - t0) / repeats

print(f"sum(list):           {measure(lambda: sum(lst))*1000:>7.2f} ms")
print(f"sum(array.array):    {measure(lambda: sum(arr))*1000:>7.2f} ms")
print(f"sum(numpy iter):     {measure(lambda: sum(ndarr))*1000:>7.2f} ms")
print(f"numpy.ndarray.sum:   {measure(lambda: ndarr.sum())*1000:>7.2f} ms")

Типовой результат (CPython 3.13, Apple M-серии):

sum(list):              5.20 ms
sum(array.array):      13.50 ms     # медленнее list?!
sum(numpy iter):       45.00 ms     # ещё медленнее?!
numpy.ndarray.sum:      0.17 ms     # быстрее в 30 раз

Сюрприз: sum() на array.array и numpy через python-итерацию медленнее, чем на list. Почему?

Где локальность реально работает

Python sum() — это python-loop. Для каждого элемента:

• __next__ итератора возвращает PyObject.
• + вызывает nb_add (или __add__).

Когда мы итерируем array.array или numpy.ndarray, CPython создаёт PyLongObject из int32 на каждом шаге — это аллокация и refcounting. Получается, что spatial locality буфера полезна только до момента, как мы начали обернуть значения в PyObject. Дальше — обычный overhead интерпретатора.

А вот ndarr.sum() — это native C-функция (np.add.reduce). Она читает буфер напрямую, использует SIMD, не создаёт никаких PyObject в цикле. Поэтому в 30 раз быстрее.

Главный вывод: locality сама по себе не магия. Она помогает только когда CPU делает много работы на cache line. В Python loop’е, где каждый элемент уходит в PyObject, выгода теряется. Поэтому в numpy все полезные операции — vectorized (+, *, .sum(), .mean(), np.where) — делают batch-обработку в нативном коде.

Точные числа: сколько в RAM, сколько в L3, сколько в L1

Размер 1M int32 = 4 MB. На современном x86 типичный L3 = 8-32 MB, L2 = 256 KB - 1 MB, L1 = 32 KB. То есть весь массив влезает в L3, но не в L1/L2.

Когда вы делаете первый проход — данные подтягиваются из RAM в L3, в L2, в L1 (по cache line). Второй проход (если массив не вырос) — данные уже в L3, чтения дешёвые. Третий проход — может быть в L2. Это temporal locality: повторное чтение тех же данных дешевле первого.

В вашем коде это проявляется так:

import time
import numpy as np

ndarr = np.arange(10_000_000, dtype='int32')  # 40 MB — больше L3

t0 = time.perf_counter()
_ = ndarr.sum()  # первый проход — холодный кэш
t1 = time.perf_counter()
_ = ndarr.sum()  # второй — горячий
t2 = time.perf_counter()

print(f"cold: {(t1-t0)*1000:.2f} ms")
print(f"hot:  {(t2-t1)*1000:.2f} ms")

Получите что-то вроде cold: 8.20 ms, hot: 3.10 ms — разница в 2-3 раза. Это и есть «горячий vs холодный» кэш.

Сводная таблица: 1M int32

«Spatial locality экономит время» — да, но видна эта экономия только в нативном коде. В Python loop’е её съедает overhead интерпретатора. Поэтому правило: много чисел плюс простая арифметика — переходите на numpy или pandas, и используйте vectorized операции.

Попробуй сам

Запустите этот бенч с разными N (1k, 10k, 100k, 1M, 10M) и постройте таблицу:

import time
import numpy as np

def bench(N, repeats=20):
    lst = list(range(N))
    ndarr = np.arange(N, dtype='int32')

    t0 = time.perf_counter()
    for _ in range(repeats):
        _ = sum(lst)
    t1 = time.perf_counter()
    list_ms = (t1 - t0) / repeats * 1000

    t0 = time.perf_counter()
    for _ in range(repeats):
        _ = ndarr.sum()
    t1 = time.perf_counter()
    numpy_ms = (t1 - t0) / repeats * 1000

    speedup = list_ms / numpy_ms if numpy_ms > 0 else float('inf')
    print(f"N={N:>10,}  list={list_ms:>8.3f} ms  numpy={numpy_ms:>8.3f} ms  speedup={speedup:>6.1f}x")

for N in [1_000, 10_000, 100_000, 1_000_000, 10_000_000]:
    bench(N)

Посмотрите, как растёт разница: на 1k она невелика, на 1M — десятки раз, на 10M — сотни.