Memory hierarchy — registers, cache, RAM, disk и реальная latency

Многие думают, что «память» в компьютере — это RAM. Один большой объект, к которому CPU может обратиться за константное время. Это упрощение, и оно мешает понимать производительность. На самом деле память — это иерархия, и разница между «быстрой» и «медленной» памятью — 6 порядков (миллион раз).

Когда вы пишете for i in range(1_000_000): data[i] и недоумеваете, почему это медленно работает на большом массиве — ответ в memory hierarchy. Когда Spark говорит «out of memory», когда Postgres медленный после ребута, когда numpy в 100 раз быстрее list Python — все эти ситуации напрямую связаны с тем, как уровни памяти работают.

В этом уроке разберём иерархию, реальную latency каждого уровня, и почему cache-friendly код может быть в 10-100x быстрее эквивалентного cache-unfriendly.

Все уровни иерархии

Современный компьютер имеет 5-6 уровней памяти. Каждый уровень в 10-100 раз медленнее предыдущего, но в 10-100 раз больше.

Запомните таблицу: L1 = 1 ns, RAM = 100 ns, SSD = 100 мкс (100,000 ns), HDD = 10 мс (10,000,000 ns).

Видно: RAM медленнее L1 в 100 раз. SSD медленнее RAM в 1000 раз. HDD медленнее SSD в 100 раз. Каждый шаг — 2-3 порядка.

Зачем нужна иерархия

Почему не сделать «всю память L1»? Технически нельзя:

Решение — иерархия. Часто используемые данные — в L1 (быстрое + маленькое). Редкие — в RAM (большое + не очень быстрое). Архивные — на диске. Hardware прозрачно кэширует данные между уровнями.

Cache line — единица обмена

CPU не работает с памятью по байту. Он работает с cache lines — блоками обычно 64 байта.

Ключевое следствие: последовательный доступ к памяти на порядки быстрее случайного. Если вы итерируете массив подряд, после первого доступа следующие 63 байта уже в L1. Если вы прыгаете по случайным адресам — каждый доступ это cache miss.

# Размер cache line:
getconf LEVEL1_DCACHE_LINESIZE
# 64    -- стандарт на x86, ARM

# Размер L1 data cache:
getconf LEVEL1_DCACHE_SIZE
# 32768  -- 32 KB на ядро

# L2:
getconf LEVEL2_CACHE_SIZE
# 524288 -- 512 KB на ядро

# L3:
getconf LEVEL3_CACHE_SIZE
# 33554432 -- 32 MB на сокет

Sequential vs random access — драматическая разница

Простой эксперимент. Создадим массив 1 миллион int (4 MB — не помещается в L1 32KB, но помещается в L3). Сравним время суммирования при последовательном и случайном доступе.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 1000000

int main() {
    int* arr = malloc(N * sizeof(int));
    for (int i = 0; i < N; i++) arr[i] = i;

    // Sequential access:
    struct timespec t1, t2;
    long sum = 0;
    clock_gettime(CLOCK_MONOTONIC, &t1);
    for (int i = 0; i < N; i++) sum += arr[i];
    clock_gettime(CLOCK_MONOTONIC, &t2);
    printf("Sequential: %.2f ms\n", (t2.tv_nsec - t1.tv_nsec) / 1e6);

    // Shuffle indexes
    int* idx = malloc(N * sizeof(int));
    for (int i = 0; i < N; i++) idx[i] = i;
    for (int i = N-1; i > 0; i--) {
        int j = rand() % (i+1);
        int t = idx[i]; idx[i] = idx[j]; idx[j] = t;
    }

    // Random access:
    sum = 0;
    clock_gettime(CLOCK_MONOTONIC, &t1);
    for (int i = 0; i < N; i++) sum += arr[idx[i]];
    clock_gettime(CLOCK_MONOTONIC, &t2);
    printf("Random: %.2f ms\n", (t2.tv_nsec - t1.tv_nsec) / 1e6);
}

Типичные результаты:

• Sequential: 1-2 мс (1M доступов за 1 мс — 1 ns per access)
• Random: 30-100 мс (1M доступов за 50 мс — 50 ns per access)

50x разница на одном и том же массиве! При последовательном чтении hardware prefetcher предсказывает следующий доступ и подтягивает данные заранее. При случайном — каждый доступ это cache miss.

# Запустить вышеупомянутый код:
gcc -O0 access.c -o access  # без оптимизаций для чистоты эксперимента
./access

# Замерить cache misses через perf:
perf stat -e cache-references,cache-misses ./access
# Покажет, сколько cache misses из всех доступов
# Random будет иметь много misses, sequential -- мало

Что значит для data engineering

Knowledge о cache hierarchy фундаментально меняет, как вы пишете код. Несколько правил:

1. Arrays of structs vs struct of arrays

# Array of Structs (AoS) -- классический OOP подход:
class Point:
    def __init__(self, x, y, z, name):
        self.x = x; self.y = y; self.z = z; self.name = name
points = [Point(...) for _ in range(1_000_000)]

# Если нужно посчитать сумму всех X:
sum_x = sum(p.x for p in points)
# Каждый доступ к p.x = cache miss, потому что между x'ами лежат y, z, name

# Struct of Arrays (SoA) -- numpy-стиль:
xs = np.array([...])  # подряд
ys = np.array([...])
zs = np.array([...])
sum_x = xs.sum()
# Все xs подряд -- идеально для cache

SoA в numpy/pandas в 10-100x быстрее AoS в Python lists для аналитики. Это и есть column-oriented storage в данных (parquet, arrow). Cache locality.

2. Loop order matters

// Двумерный массив 1000x1000:
int matrix[1000][1000];

// БЫСТРО -- row by row (как лежит в памяти):
for (int i = 0; i < 1000; i++)
    for (int j = 0; j < 1000; j++)
        sum += matrix[i][j];

// МЕДЛЕННО -- column by column:
for (int j = 0; j < 1000; j++)
    for (int i = 0; i < 1000; i++)
        sum += matrix[i][j];
// Каждый доступ к matrix[i][j] = другая строка = cache miss
// На 1000x1000 разница может быть 5-10x

В data engineering это работает для табличных данных. Чтение row-by-row из row-oriented хранилища (PostgreSQL) — быстро. Чтение колонок — медленно. Обратное для column-oriented (Parquet, ClickHouse) — агрегации по колонке быстрые, чтение всей строки медленнее.

3. Working set size

Если ваш горячий набор данных (working set) помещается в L3 cache — всё будет fast. Не помещается — каждый доступ может уйти в RAM.

L1 = 32-64 KB -- небольшая активная часть алгоритма
L2 = 256-1024 KB -- разумный working set
L3 = 8-128 MB -- большой working set
RAM = ваш весь dataset

При проектировании high-performance pipeline думайте: что у меня в working set? Если 100 MB — хорошо, если 100 GB — скорее всего хитов в L3 будет мало.

NVMe — быстрая нижняя память

NVMe SSD сильно изменили картину. SATA SSD имеют latency 100-200 мкс, NVMe — 10-50 мкс. Это:

NVMe gen4-5 настолько быстры, что для random reads они становятся сравнимы с network latency. Это меняет архитектуру: можно использовать диск как очень большую RAM (с paging, mmap, etc).

# Информация о ваших дисках:
lsblk -d -o NAME,SIZE,TYPE,TRAN
# nvme0n1   500G disk nvme
# sda      4000G disk sata

# Бенчмарк latency:
sudo fio --name=randread --rw=randread --bs=4k --size=1G --filename=/tmp/test --runtime=10
# read: IOPS=200k, lat (usec): avg=20 -- 20 мкс average latency

rm /tmp/test

Network — ещё один уровень иерархии

Для распределённых систем сеть — ещё один уровень в memory hierarchy.

В data engineering это важно: distributed query на 5 серверов в том же DC — RTT 200 мкс. Distributed query через регионы — 100 мс. Один HTTP-запрос cross-region может занять больше времени, чем 100 GB sequential reads с локального NVMe.

Попробуй сам

# 1. Узнать параметры памяти своей машины:
getconf LEVEL1_DCACHE_SIZE
getconf LEVEL2_CACHE_SIZE
getconf LEVEL3_CACHE_SIZE
getconf LEVEL1_DCACHE_LINESIZE

# 2. Бенчмарк sequential vs random:
cat > /tmp/access.c << 'EOF'
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 10000000
int main() {
    int* a = malloc(N*sizeof(int));
    int* idx = malloc(N*sizeof(int));
    for (int i=0; i<N; i++) { a[i]=i; idx[i]=i; }
    for (int i=N-1; i>0; i--) { int j=rand()%(i+1); int t=idx[i]; idx[i]=idx[j]; idx[j]=t; }
    long sum;
    struct timespec t1, t2;
    sum=0;
    clock_gettime(CLOCK_MONOTONIC, &t1);
    for (int i=0; i<N; i++) sum += a[i];
    clock_gettime(CLOCK_MONOTONIC, &t2);
    printf("Sequential: %.1f ms (sum=%ld)\n", (t2.tv_sec-t1.tv_sec)*1e3 + (t2.tv_nsec-t1.tv_nsec)/1e6, sum);
    sum=0;
    clock_gettime(CLOCK_MONOTONIC, &t1);
    for (int i=0; i<N; i++) sum += a[idx[i]];
    clock_gettime(CLOCK_MONOTONIC, &t2);
    printf("Random:     %.1f ms (sum=%ld)\n", (t2.tv_sec-t1.tv_sec)*1e3 + (t2.tv_nsec-t1.tv_nsec)/1e6, sum);
}
EOF
gcc -O2 /tmp/access.c -o /tmp/access
/tmp/access
# Sequential будет 5-30 мс, Random 200-1000 мс -- 30-50x разница

# 3. perf stat покажет cache misses:
perf stat -e cache-misses,cache-references,L1-dcache-load-misses /tmp/access
# Будет видно: sequential ~1% miss rate, random 30-50% miss rate

# 4. Сравнить numpy vs Python list:
python3 -c "
import time, numpy as np
n = 10_000_000
lst = list(range(n))
t1 = time.time(); s = sum(lst); print(f'Python list sum: {time.time()-t1:.3f}s')

arr = np.arange(n)
t1 = time.time(); s = arr.sum(); print(f'NumPy sum: {time.time()-t1:.3f}s')
"
# NumPy в 50-100x быстрее -- cache friendly

# 5. Замерить NVMe latency:
sudo fio --name=test --rw=randread --bs=4k --size=100M \
    --filename=/tmp/fio.test --runtime=5 --direct=1
rm /tmp/fio.test