Что такое cache line

Когда CPU обращается к памяти, он не читает один байт. Он читает целый блок памяти, выровненный по 64-байтной границе. Этот блок называется cache line. На современных x86 и ARM это всегда 64 байта, точка.

Почему именно так? Чтение из RAM имеет огромный фиксированный overhead (~60 ns latency). Прочитать 1 байт занимает столько же времени, что прочитать 64. Поэтому архитектура CPU всегда читает 64 байта за один раз, в надежде, что соседние данные тоже скоро понадобятся.

64 байта — это:

• 16 штук 32-битных int (по 4 байта).
• 8 штук 64-битных int / float / pointer.
• 64 штуки char.
• Около 4 штук Python int-объектов (28 байт каждый — не помещается ровно).

Так что когда вы делаете arr[i] (numpy int32), вы получаете не только arr[i], но и бесплатно в L1 оседают arr[i+1]..arr[i+15]. Следующее чтение arr[i+1] — ~1 ns вместо ~60 ns.

Spatial locality — пространственная локальность

Spatial locality — это свойство кода: если он обращается к адресу X, скорее всего скоро понадобится X+1, X+2, … Это золотое правило памяти: оно превращает дорогие RAM-чтения в почти бесплатные cache hits.

Хорошие примеры spatial locality:

• Проход по массиву for x in lst или for i, x in enumerate(arr).
• Сравнение двух соседних строк в файле.
• Чтение полей одного объекта подряд.

Плохие примеры:

• Random access — arr[random.randint(0, n)] каждый раз.
• Hash-таблицы (по природе своей разбрасывают данные).
• Linked list — каждый следующий узел может быть где угодно в памяти.

Temporal locality — временная локальность

Второе свойство — temporal locality: если код обратился к X, скорее всего скоро обратится к X снова. Cache держит недавно использованные данные — на это и расчёт.

Хорошие примеры:

• Аккумулятор в цикле — переменная s в for x: s += x всё время в регистре.
• Hot config / lookup table, к которой обращаются тысячи раз.
• Активный buffer в streaming-обработке.

Плохие примеры:

• Однократный проход по гигантскому датасету — каждый элемент посещается ровно раз, кэш не помогает (но cache line всё равно помогает!).

Демонстрация на простом примере

Сделаем эксперимент: пройдёмся по массиву последовательно vs в случайном порядке. Один и тот же big-O O(n), но разница из-за cache line будет заметна.

import timeit
import random
import array

def sequential_sum(arr, indices):
    s = 0
    for i in indices:
        s += arr[i]
    return s

n = 1_000_000
# array.array — компактный массив int32, как numpy без зависимости
arr = array.array('i', range(n))

# Случайный порядок
seq_indices = list(range(n))
random_indices = list(range(n))
random.shuffle(random_indices)

t_seq = min(timeit.repeat(
    lambda: sequential_sum(arr, seq_indices),
    number=3, repeat=3
)) / 3

t_rand = min(timeit.repeat(
    lambda: sequential_sum(arr, random_indices),
    number=3, repeat=3
)) / 3

print(f"Sequential access: {t_seq*1000:.0f} ms")
print(f"Random access:    {t_rand*1000:.0f} ms")
print(f"Slowdown:         {t_rand/t_seq:.1f}x")

Типичный вывод:

Sequential access:  85 ms
Random access:     320 ms
Slowdown:          3.8x

Big-O одинаковый — O(n) сложений. Размер данных одинаковый. Различается только порядок доступа. Sequential получает бесплатные cache hits на соседних элементах. Random — каждый раз туда-сюда по памяти.

На Python разница ~4x — её смягчает огромный overhead интерпретатора. На numpy/C эффект может быть 20-50x на тех же данных.

for x in lst vs for i in range(len(lst)): lst[i]

Классический вопрос: в каких случаях быстрее одно, в каких другое?

import timeit

lst = list(range(1_000_000))

t1 = min(timeit.repeat(
    """
total = 0
for x in lst:
    total += x
""",
    setup='lst = list(range(1_000_000))',
    number=10, repeat=3
)) / 10

t2 = min(timeit.repeat(
    """
total = 0
for i in range(len(lst)):
    total += lst[i]
""",
    setup='lst = list(range(1_000_000))',
    number=10, repeat=3
)) / 10

print(f"for x in lst:        {t1*1000:.1f} ms")
print(f"for i in range(len): {t2*1000:.1f} ms")

Типичный вывод:

for x in lst:        45.0 ms
for i in range(len): 62.0 ms

for x in lst быстрее на ~30%. Причина — он использует итератор list-а, который ходит по ob_item по порядку, идеально cache-friendly. range(len) создаёт лишний int-объект на каждой итерации и делает lst[i] через вычисление адреса.

Но: если вам нужно одновременно обращаться к lst[i] и lst[i+1] (например, для проверки соседних элементов) — выбора нет, нужны индексы. И тогда for i in range(...) правильное решение.

Cache lines и структуры данных

Это объясняет фундаментальную разницу между list (массив указателей в Python) и array.array / numpy.array (компактные массивы значений):

Итог: проход по list из 1M int-ов означает 1M random RAM accesses к разным int-объектам. Проход по array.array — 250K cache line reads (по 16 int32 в каждой), всё sequentially. Разница может быть 10-50x в реальной производительности.

В Python это критично: для числовых данных всегда лучше array.array, numpy.array или встроенные функции (sum(range(n)) оптимизирован), а не list.

Попробуй сам: матрица row-major vs column-major

Самый известный пример cache effects — порядок обхода 2D-массива. В большинстве языков (C, Python, numpy с default) матрицы хранятся по строкам (row-major). То есть m[0][0], m[0][1], m[0][2], ..., m[1][0], m[1][1], ... лежат в памяти подряд.

Если обходить по строкам (внутренний цикл по столбцам) — sequential access, cache-friendly. Если обходить по столбцам (внутренний цикл по строкам) — random access, cache-unfriendly.

import timeit

N = 1000  # матрица NxN
setup = f"""
matrix = [[i*j for j in range({N})] for i in range({N})]
"""

# Обход по строкам — sequential
row_major = """
total = 0
for i in range(N):
    for j in range(N):
        total += matrix[i][j]
""".replace("N", str(N))

# Обход по столбцам — random для row-major layout
col_major = """
total = 0
for j in range(N):
    for i in range(N):
        total += matrix[i][j]
""".replace("N", str(N))

t_row = min(timeit.repeat(row_major, setup=setup, number=3, repeat=3)) / 3
t_col = min(timeit.repeat(col_major, setup=setup, number=3, repeat=3)) / 3

print(f"Row-major (cache-friendly):     {t_row*1000:.1f} ms")
print(f"Col-major (cache-unfriendly):   {t_col*1000:.1f} ms")
print(f"Slowdown:                        {t_col/t_row:.1f}x")

Row-major (cache-friendly):     35.0 ms
Col-major (cache-unfriendly):   58.0 ms
Slowdown:                        1.7x

Шпаргалка по cache lines

В следующем уроке — pointer chasing: что происходит, когда CPU не может предугадать следующий адрес. Linked list, prefetcher и почему deque на самом деле хорош.