Структуры данных на практике. Глава 2: Иерархия памяти

«Память — это современный диск, диск — это современная лента», — Джим Грей

Проблема ста тактов

В Главе 1 мы говорили о том, что промахи кэша стоят 100-200 тактов, а попадания в кэш — всего 1-4 такта. И это не какая-то мелкая деталь, а самый важный фактор современной производительности.

Ниже я расскажу, почему это так.

Однажды я оптимизировал драйвер устройства для встраиваемой системы на RISC-V. Драйвер должен был обрабатывать пакеты от сетевого интерфейса, но при большой нагрузке мы теряли пакеты. CPU работал с частотой 1 ГГц, а для обработки каждого пакета требовалось около 500 команд. Простая математика:

500 команд ÷ 1 ГГц = 500 наносекунд на пакет

При скорости 500 нс на пакет мы могли бы обрабатывать 2 миллиона пакетов в секунду. Однако мы справлялись всего с 200 тысячами пакетов в секунду, то есть в десять раз меньше, чем ожидалось.

Профилировщик показал следующее:

$ perf stat -e cycles,instructions,cache-misses ./driver_test
  Performance counter stats:
    5,000,000 cycles
      500,000 instructions
       45,000 cache-misses

Постойте-ка: 500000 команд должны занимать 500000 тактов (при 1 IPC). Но мы видим 5 миллионов тактов. Куда подевались лишние 4,5 миллиона тактов?

Потрачены на промахи кэша: 45000 промахов × 100 тактов = 4500000 тактов

Во время исполнения преобладали промахи кэша. Реальные вычисления (500000 тактов) занимали всего 10% от общего времени. Остальные 90% тратились на ожидание памяти.

Такова реальность современных вычислений: память медленная и становится всё медленнее относительно скорости CPU.

Иерархия памяти

У современных компьютеров нет «памяти»: у них есть иерархия разных видов памяти, каждый из которых имеет свою скорость и размер:

Уровень	Тип	Задержка	Размер
Регистры	32 регистра	1 такт	Около 128 Б
Кэш L1	Разделение на команды и данные	3-4 такта	32-64 КБ
Кэш L2	Единый	12-15 тактов	256-512 КБ
Кэш L3 (при наличии)	Общий	40-50 тактов	2-32 МБ
DRAM	Основная память	100-200 тактов	ГБ-ТБ

Важные выводы:

1. При спуске по иерархии скорость снижается (1 → 200 тактов)

2. При спуске увеличивается размер (128 Б → ГБ)

3. Разрыв огромен: DRAM в 100-200 раз медленнее L1

Во встраиваемых системах эта иерархия часто оказывается проще:

Типичный микроконтроллер (например, RISC-V RV32IMC с частотой 100 МГц):

Уровень	Тип	Задержка	Размер
Регистры	32 регистра	1 такт	128 Б
I-кэш L1 Cache	Команды	1 такт	16 КБ
D-кэш L1/SRAM	Данные	1-2 такта	8-32 КБ
Флэш-память	Хранилище кода	Примерно 10 тактов	128 КБ - 1 МБ
Внешняя DRAM (дополнительная)	Данные (при наличии)	50-100 тактов	8-64 МБ

Отличия встраиваемых систем:

• Меньший размер кэшей (8-64 КБ против 256 КБ-32 МБ)

• Часто отсутствует кэш L2/L3

• Флэш-память вместо DRAM для хранения кода

• Меньший бюджет памяти

Линии кэша: фундаментальная единица измерения

Очень важно то, что кэши получают не отдельные байты, а линии кэша.

В современных процессорах (и десктопных, и встраиваемых) линия кэша обычно имеет размер 64 байт. При получении доступа к одному байту оборудование получает весь 64-байтный блок, содержащий этот байт.

Пример: доступ к одному integer

int x = array[0];  // Получаем доступ к 4 байтам по адресу 0x1000

Что происходит на самом деле:

CPU запрашивает: 4 байта по адресу 0x1000
Кэш получает: 64 байта с 0x1000 по 0x103F

Линия кэша включает в себя:

• Запрошенный integer (4 байта)

• Следующие 15 integer (60 байт)

Именно поэтому последовательный доступ быстр:

// Выполняется быстро: всё находится в одной линии кэша
for (int i = 0; i < 16; i++) {
    sum += array[i];  // Первая операция доступа: промах, следующие 15: попадания
}

А произвольный доступ медленный:

// Выполняется медленно: каждая операция доступа, скорее всего, обращается к отдельной линии кэша
for (int i = 0; i < 16; i++) {
    sum += array[random_index[i]];  // Каждая операция доступа: промах с большой долей вероятности
}

Организация кэша

Кэши упорядочены в наборы (set) и каналы (way). Понимание этого помогает объяснить конфликты кэша.

Кэш с прямым отображением (1-канальный):

Биты адреса: [     Тэг     |   Индекс  |     Смещение    ]
             └─────────────┴───────────┴──────────────────
              Идентифицирует  Выбирает     Байт внутри
               строку кэша     набор        линии кэша

Пример: кэш на 32 КБ, 64-байтные линии, с прямым отображением

• Линии кэша: 32 КБ ÷ 64 Б = 512 линий

• Индексные биты: log₂(512) = 9 бит

• Биты смещения: log₂(64) = 6 бит

• Биты тэгов: оставшиеся биты (то есть 32 - 9 - 6 = 17 бит для 32-битного адреса)

Проблемы с прямым отображением: конфликты кэша

int a[1024];  // По адресу 0x10000
int b[1024];  // По адресу 0x18000

// Эти два массива отображаются на О��ИНАКОВЫЕ наборы кэша!
// 0x10000 и 0x18000 различаются только в бите 15
// Для индекса используются биты 6-14, так что возникает их коллизия

Наборно-ассоциативный кэш (N-канальный):

4-канальный наборно-ассоциативный кэш имеет 4 «сегментов» на набор:

Набор 0: [Линия 0] [Линия 1] [Линия 2] [Линия 3]
Набор 1: [Линия 0] [Линия 1] [Линия 2] [Линия 3]
...

Когда адрес отображается на Набор 0, он может относиться к любому из четырёх сегментов. Это снижает количество конфликтов.

Типичные конфигурации:

• L1: 8-канальный наборно-ассоциативный (32-64 КБ)

• L2: 8-16-канальный наборно-ассоциативный (256-512 КБ)

• L3: 16-канальный наборно-ассоциативный (2-32 МБ)

Встраиваемые системы:

• Часто с прямым отображением или 2-канальные (у простого оборудования)

• Чем меньше размер кэшей, тем больше конфликтов

Пространственная и временная локальность

Скорость кэша зависит от двух типов локальности:

Пространственная локальность: доступ к соседним адресам

// Хорошая пространственная локальность
for (int i = 0; i < n; i++) {
    sum += array[i];  // Последовательный доступ
}

// Плохая пространственная локальность
for (int i = 0; i < n; i++) {
    sum += array[random[i]];  // Произвольный доступ
}

Временная локальность: многократный доступ к одному и тому же адресу

// Хорошая временная локальность
int temp = array[0];
for (int i = 0; i < 1000; i++) {
    result += temp * i;  // Многократное использование temp
}

// Плохая временная локальность
for (int i = 0; i < 1000; i++) {
    result += array[i % 10] * i;  // Вытеснение перед повторным использованием
}

В дружественном к кэшу коде используются обе:

// Матричное умножение: дружественная к кэшу версия
for (int i = 0; i < N; i++) {
    for (int k = 0; k < N; k++) {
        int r = A[i][k];
        for (int j = 0; j < N; j++) {
            C[i][j] += r * B[k][j];  // Хорошая пространственная локальность B
        }
    }
}

Prefetcher

У современных CPU есть устройства упреждающей выборки (prefetcher), прогнозирующие паттерны доступа к памяти и получающие данные ещё до того, как они понадобятся.

Как работает prefetcher:

Последовательный prefetcher: распознаёт последовательный доступ

// Prefetcher обнаруживает паттерн и выполняет упреждающую выборку
for (int i = 0; i < n; i++) {
    sum += array[i];  // Prefetcher получает array[i+1], array[i+2], ...
}

Шаговый prefetcher: распознаёт постоянный шаг

// Prefetcher распознаёт шаг в 8 байт
for (int i = 0; i < n; i++) {
    sum += array[i * 2];  // Доступ к каждому второму элементу
}

Ограничения prefetcher:

1. Не может помочь при произвольном доступе:

for (int i = 0; i < n; i++) {
    sum += array[random[i]];  // Непредсказуемо, упреждающая выборка невозможна
}

2. Ограниченное расстояние: обычно 10-20 линий кэша вперёд

3. Его можно обмануть:

// Чередующийся паттерн сбивает prefetcher с толку
for (int i = 0; i < n; i++) {
    if (i % 2 == 0)
        sum += array[i];
    else
        sum += other_array[i];
}

Встраиваемые системы: у многих микроконтроллеров нет prefetcher или есть простые prefetcher только последовательного доступа. Из-за этого последовательный доступ становится ещё более критичным.

Пропускная способность памяти

Даже при идеальном поведении кэша мы ограничены пропускной способностью памяти.

Пример расчёта (для десктопа):

• DDR4-3200: 25,6 ГБ/с на канал

• Двухканальная: суммарно 51,2 ГБ/с

• Кэш L3: ~200 ГБ/с

• Кэш L2: ~400 ГБ/с

• Кэш L1: ~1000 ГБ/с

Следствие: передача больших массивов ограничена пропускной способностью

// Ограничение по пропускной способности: передача массива размером 1 ГБ
for (int i = 0; i < 256*1024*1024; i++) {
    array[i] = 0;  // Ограничено пропускной способностью DRAM
}

У встраиваемых систем пропускная способность намного ниже:

• SRAM типичного микроконтроллера: 1-4 ГБ/с

• Внешняя DRAM (если есть): 100-500 МБ/с

Из-за этого критичным становится размер рабочего набора — данные нужно хранить в SRAM на чипе.

Согласованность кэшей (многоядерная система)

В многоядерных системах кэши должны оставаться согласованными, то есть все ядра должны видеть согласованные данные.

Протокол MESI (общий для x86 и ARM):

• Modified: строка была изменена и отличается от содержимого основной памяти, этот кэш содержит единственную валидную копию

• Exclusive: строка идентична содержимому основной памяти, этот кэш содержит единственную валидную копию

• Shared: валидные кэши содержатся в нескольких кэшах

• Invalid: строка кэша содержит устаревшие данные

Ложное совместное использован��е: убийца производительности в многоядерных системах

// ПЛОХО: ложное совместное использование
struct {
    int counter_core0;  // Используется ядром 0
    int counter_core1;  // Используется ядром 1
} shared;  // Обе находятся в одной линии кэша!

// Ядро 0 записывает counter_core0 → инвалидирует линию кэша ядра 1
// Ядро 1 записывает counter_core1 → инвалидирует линию кэша ядра 0
// Эффект пинг-понга: ужасная производительность

Решение: заполнение данных так, чтобы они попадали в разные линии кэша

// ХОРОШО: отсутствие ложного совместного использования
struct {
    int counter_core0;
    char pad[60];       // Заполнение до 64 байт
    int counter_core1;
} shared;

RISC-V: использует RVWMO (RISC-V Weak Memory Ordering) с командами fence для синхронизации.

Модель памяти RISC-V

У RISC-V слабая модель памяти — если не используются fence, порядок операций памяти можно менять.

Порядок операций памяти:

// Без fence: порядок может быть изменён
store A
store B
load C
load D

Команда fence:

sw   a0, 0(a1)    # Сохраняем A
fence w, w        # Гарантирует, что сохранение завершится до следующей записи
sw   a2, 0(a3)    # Сохраняем B

Типы fence:

• fence r, r: fence «загрузка-загрузка»

• fence w, w: fence «сохранение-сохранение»

• fence rw, rw: полный fence

• fence.i: fence команд (для самомодифицирующегося кода)

Атомарные операции (A extension):

lr.w  a0, (a1)    # Зарезервирована для загрузки
# ... изменяем a0 ...
sc.w  a2, a0, (a1) # Сохранение с условием (не выполняется, если резервирование нарушено)

Практические инструкции

Исходя из этого понимания иерархии памяти, приведу практические советы по проектированию структур данных:

1. Минимизируйте промахи кэшей

• По возможности используйте паттерны последовательного доступа

• Ограничивайте размер рабочего набора (чтобы он умещался в L1/L2)

• Избегайте следования по указателям (связанные списки, деревья)

2. Пользуйтесь преимуществами линий кэша

• Упаковывайте связанные данные вместе (struct)

• Согласуйте размер структур данных с границами линий кэша

• Избегайте ложного совместного использования в многоядерных системах

3. Учитывайте наличие prefetcher

• Используйте предсказуемые паттерны доступа

• Последовательный доступ или доступ с постоянным шагом

• По возможности избегайте произвольного доступа

4. Понимайте особенности своего оборудования

• Размеры кэшей (L1, L2, L3)

• Размер линий кэша (обычно 64 байта)

• Ассоциативность (влияет на конфликты)

• Возможности prefetcher

5. Не гадайте, а делайте замеры

• Измеряйте промахи кэша с помощью perf

• Сначала выполняйте профилирование, потом оптимизацию

• Проводите тестирование на целевом оборудовании

Подведём итог

Проблема ста тактов была решена благодаря пониманию иерархии памяти. Утеря пакетов драйвером устройства была вызвана 45 тысячами промахов кэша, на которые тратилось 4,5 миллиона тактов, то есть 90% время исполнения уходило на ожидание памяти. Оптимизация паттернов доступа к памяти снизило количество промахов кэша и повысила производительность с 200 тысяч пакетов до ожидавшихся 2 миллионов.

Основные выводы:

• Промахи кэша стоят 100-200 тактов (попадания — всего 1-4)

• Кэши получают 64-байтные линии, а не отдельные байты

• Последовательный доступ в 10-100 раз быстрее, чем произвольный

• У встраиваемых систем меньше размер кэшей и проще иерархии

Как это влияет на проектирование

• Массивы лучше, чем связанные списки (благодаря пространственной локальности)

• Маленькие рабочие наборы лучше больших (временная локальность)

• Последовательный доступ лучше произвольного (prefetcher)

• Измерения лучше, чем догадки (используйте инструменты профилирования)

В следующей главе: мы создадим комплексный фреймворк бенчмаркинга для точного измерения этих эффектов и научимся эффективному применению инструментов профилирования.