«Массив — самая важная структура данных в computer science», — Дональд Кнут (вольное изложение цитаты)
Простейшая структура данных
Массивы настолько просты, что мы иногда воспринимаем их, как нечто само собой разумеющееся. Смежная память, доступ за O(1): что тут ещё оптимизировать?
Всё.
Я работал над конвейером обработки пакетов сетевого коммутатора. Код был простым: считываем пакеты из кольцевого буфера (массива), обрабатываем их и записываем результаты в другой массив. Всё просто, правда?
Но производительность была ужасной. Мы обрабатывали 100 тысяч пакетов в секунду, хотя оборудование должно было справляться с 1 миллионом.
Профилировщик показал нечто странное:
$ perf stat -e cache-misses,instructions ./packet_processor Performance counter stats: 450,000 cache-misses 1,000,000 instructions
450000 промахов кэша на 1000000 команд? То есть промах происходил раз в 2-3 команды. При простых операциях с массивами это не имело никакого смысла.
Проблема заключалась не в самих массивах, а в том, как мы их использовали.
Важна структура памяти
Давайте начнём с основ. Массив — это смежная память:
int array[8] = {0, 1, 2, 3, 4, 5, 6, 7};
В памяти это выглядит так (если используются 4-байтные integer):
Адрес: 0x1000 0x1004 0x1008 0x100C 0x1010 0x1014 0x1018 0x101C Значение: 0 1 2 3 4 5 6 7 └───────────────────────────────────────────────────────┘ Одна 64-байтная линия кэша
Важное наблюдение: все 8 integer умещаются в одну 64-байтную линию кэша.
Последовательный доступ к массиву:
int sum = 0; for (int i = 0; i < 8; i++) { sum += array[i]; }
Поведение кэша с упреждающей выборкой:
Поведение кэша:
Первая операция доступа (
array[0]): промах кэша (100 тактов)Получение всей линии кэша (64 байт = 16 integer)
Следующие 7 операций доступа (с
array[1]поarray[7]): попадания �� кэш (по 1 такту каждый)Prefetcher: распознаёт паттерн, выполняет упреждающую выборку
Общие затраты: 100 + 7 = 107 тактов на 8 операций доступа = 13,4 тактов на одну операцию доступа
Сравним это с произвольным доступом:
int indices[8] = {7, 2, 5, 0, 3, 6, 1, 4}; int sum = 0; for (int i = 0; i < 8; i++) { sum += array[indices[i]]; }
Если indices вызывает доступ к разным линиям кэша:
Каждая операция доступа: промах кэша (100 тактов)
Общие затраты: 800 тактов на 8 операций доступа = 100 тактов на операцию
Последовательный доступ в 7,5 раз быстрее произвольного, хоть оба и выполняются за O(n).
Шаговые паттерны
Не все последовательные операции доступа одинаковы. Важен ещё и шаг.
Доступ с шагом 1 (наилучший случай):
for (int i = 0; i < n; i++) { sum += array[i]; // Шаг = 1 элемент = 4 байта }
Доступ с шагом 2 (тоже неплохо):
for (int i = 0; i < n; i += 2) { sum += array[i]; // Шаг = 2 элемента = 8 байт }
Большой шаг (хуже):
for (int i = 0; i < n; i += 16) { sum += array[i]; // Шаг = 16 элементов = 64 байт }
Почему шаг важен?
Использование линий кэша: при шаге 1 используются все 64 полученных байта. При шаге 16 используется всего по 4 байта на линию кэша (доля использования — 6,25%).
Эффективность prefetcher: аппаратные prefetcher распознают шаговые паттерны, но большие шаги могут превышать расстояние упреждающей выборки.
Бенчмарк (массив из 1 миллиона элементов):
Шаг 1: 1,2 мс (использование линий кэша на 100%) Шаг 2: 1,3 мс (использование линий кэша на 50%, упреждающая выборка всё равно происходит) Шаг 4: 1,5 мс (использование линий кэша на 25%) Шаг 8: 2,1 мс (использование линий кэша на 12,5%) Шаг 16: 3,8 мс (использование линий кэша на 6,25%) Шаг 64: 8,5 мс (использование линий кэша на 1,56%, новая линия кэша при каждом доступе)
Рекомендация: для хорошей производительности шаг должен быть маленьким (≤ 8 элементов).
Инструмент из реального мира: lmbench lat_mem_rd
В классическом бенчмарк-пакете lmbench есть lat_mem_rd, измеряющий задержки памяти при разных размерах и шагах массивов. Именно об этом мы и говорили выше.
Как это работает:
// Упрощённая версия lmbench lat_mem_rd char *p = array; for (int i = 0; i < iterations; i++) { // Следование по у��азателям с настраиваемым шагом p = *(char **)p; // Следование по указателю на следующий элемент }
Массив инициализируется таким образом, что каждый элемент указывает на следующий элемент на расстоянии stride:
// Инициализируем массив с шагом for (size_t i = 0; i < size; i += stride) { array[i] = &array[(i + stride) % size]; }
Результат выполнения lmbench:
$ lat_mem_rd 64M 128 # Array size: 64 MB, stride: 128 bytes Output: Stride Latency 128 3.2 ns (L1 cache) 256 3.5 ns (L1 cache) 512 4.1 ns (L1 cache) 1024 5.8 ns (L2 cache) 4096 12.5 ns (L2 cache) 16384 45.0 ns (L3 cache) 65536 102.0 ns (DRAM)
Что это демонстрирует:
Малые шаги (128-512 байт): остаёмся в кэше L1 (~3-4 нс)
Средние шаги (1-4 КБ): кэш L2 (~6-12 нс)
Большие шаги (16-64 КБ): кэш L3 или DRAM (45-100+ нс)
Почему шаг влияет на задержки:
Малый шаг: последовательный доступ, prefetcher помогает, остаёмся в L1
Большой шаг: скачем по линиям кэша, prefetcher бесполезен, выходим из L1
Важное наблюдение: именно поэтому критична схема структуры данных. Если структура имеет размер 128 байт и вы итеративно обходите её массив, то вы выполняете доступ с шагом 128. Если «горячими» (с частым доступом) являются всего 8 байт структуры, то вы впустую тратите 93,75% каждой линии кэша.
Встраиваемые системы: во встраиваемых системах без кэша L3 скачок задержек происходит ещё резче. Выйдя за пределы объёма L1/L2, вы переходите сразу в DRAM или флэш-память (замедление в 100-1000 раз).
Многомерные массивы
При использовании многомерных массивов нужно сделать критически важный выбор: схема с размещением по строкам или по столбцам.
В C используется порядок по строкам:
int matrix[4][4] = { {0, 1, 2, 3}, {4, 5, 6, 7}, {8, 9, 10, 11}, {12, 13, 14, 15} };
Схема памяти (по строкам):
Адрес: 0x1000 0x1004 0x1008 0x100C 0x1010 0x1014 0x1018 0x101C ... Значение: 0 1 2 3 4 5 6 7 ... └─────────── Строка 0 ──────────┘└──────────── Строка 1 ─────────┘
Обход по строкам (хорошо):
for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { sum += matrix[i][j]; // Последовательное размещение в памяти } }
Обход по столбцам (плохо):
for (int j = 0; j < 4; j++) { for (int i = 0; i < 4; i++) { sum += matrix[i][j]; // Шаг = 4 элемента = 16 байт } }
Бенчмарк (матрица 1024×1024):
По строкам: 12 мс (последовательный доступ) По столбцам: 45 мс (доступ с шагом 1024)
При одном и том же алгоритме обход по столбцам в 3,75 раза медленнее!
Проблема перемножения матриц
Перемножение матриц — классический пример оптимизации кэша:
// Наивная реализация for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { for (int k = 0; k < N; k++) { C[i][j] += A[i][k] * B[k][j]; } } }
Паттерны доступа:
A[i][k]: по строкам, хороший (шаг 1)C[i][j]: один и тот же элемент многократно, отличный (временная локальность)B[k][j]: по столбцам, ужасный (шаг N)
При N=1024: доступ к B[k][j] выполняется с шагом 1024 элемента = 4096 байт = 64 линий кэша!
Решение 1: изменение порядка циклов (порядок ikj)
// Лучше: порядок ikj 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 упорядочен по строкам! } } }
Новые паттерны доступа:
A[i][k]: по строкам, хорошийB[k][j]: по строкам, хороший (раньше был по столбцам)C[i][j]: по строкам, хороший
Бенчмарк (матрицы 512×512):
Порядок ijk (наивный): 2450 мс Порядок ikj: 680 мс (быстрее в 3,6 раза)
Решение 2: разбиение на блоки (тайлинг)
В случае очень больших матриц, не помещающихся в кэш, используйте разбиение на блоки:
#define BLOCK_SIZE 64 for (int ii = 0; ii < N; ii += BLOCK_SIZE) { for (int jj = 0; jj < N; jj += BLOCK_SIZE) { for (int kk = 0; kk < N; kk += BLOCK_SIZE) { // Обрабатываем подматрицу BLOCK_SIZE × BLOCK_SIZE for (int i = ii; i < ii + BLOCK_SIZE && i < N; i++) { for (int k = kk; k < kk + BLOCK_SIZE && k < N; k++) { int r = A[i][k]; for (int j = jj; j < jj + BLOCK_SIZE && j < N; j++) { C[i][j] += r * B[k][j]; } } } } } }
Почему разбиение на блоки помогает:
Обрабатываются малые блоки, умещающиеся в кэш L1
Многократное использование данных перед удалением из кэша
Существенно снижается количество промахов кэша
Бенчмарк (матрицы 1024×1024):
Наивный (ijk): 18500 мс С изменённым порядком (ikj): 5200 мс (быстрее в 3,6 раза) С разбиением на блоки: 1800 мс (в 10,3 раза быстрее наивного, в 2,9 раза быстрее изменённого порядка)
Структура массивов и массив структур
Способ организации данных в массивы сильно влияет на производительность.
Сравнение схемы памяти:
Массив структур (AoS):
typedef struct { float x, y, z; // Позиция (12 байт) float vx, vy, vz; // Скорость (12 байт) float mass; // Масса (4 байта) int id; // ID (4 байта) } particle_t; // Всего: 32 байта particle_t particles[1000]; // Обновляем позиции for (int i = 0; i < 1000; i++) { particles[i].x += particles[i].vx * dt; particles[i].y += particles[i].vy * dt; particles[i].z += particles[i].vz * dt; }
Схема памяти:
Линия кэша 0: [p0.x, p0.y, p0.z, p0.vx, p0.vy, p0.vz, p0.mass, p0.id] Линия кэша 1: [p1.x, p1.y, p1.z, p1.vx, p1.vy, p1.vz, p1.mass, p1.id] ...
Проблема: в каждой линии кэша содержатся ненужные нам данные (mass, id). Мы используем всего 24 байта из 64 (37,5%).
Структура массивов (SoA):
typedef struct { float x[1000]; float y[1000]; float z[1000]; float vx[1000]; float vy[1000]; float vz[1000]; float mass[1000]; int id[1000]; } particles_t; particles_t particles; // Обновляем позиции for (int i = 0; i < 1000; i++) { particles.x[i] += particles.vx[i] * dt; particles.y[i] += particles.vy[i] * dt; particles.z[i] += particles.vz[i] * dt; }
Схема памяти:
Линия кэша 0: [x[0], x[1], x[2], ..., x[15]] Линия кэша 1: [x[16], x[17], ..., x[31]] ...
Преимущество: линии кэша используются на 100%. Каждая линия кэша содержит только нужные нам данные.
Бенчмарк (1 миллион частиц, 1000 итераций):
AoS: 2850 мс SoA: 1200 мс (быстрее в 2,4 раза)
Когда использовать SoA:
Операции выполняют доступ только к малому количеству полей
Большие массивы (> размера кэша)
Критичные для производительности циклы
Когда использовать AoS:
Операции выполняют доступ ко всем полям
Малые массивы (< размера кэша)
Понятность кода важнее, чем производительность
Выравнивание и заполнение
Выравнивание в памяти влияет и на корректность, и на производительность.
Естественное выравнивание:
char: выровнен по 1 байтуshort: выровнен по 2 байтамint: выровнен по 4 байтамlong: выровнен по 8 байтамdouble: выровнен по 8 байтам
Доступ без выравнивания:
char buffer[16]; int *p = (int*)(buffer + 1); // Выравнивания нет! *p = 42; // Может быть медленным или привести к вылетам
На x86: доступ без выравнивания работает, но он медленнее (может выходить за границы линий кэша)
На ARM/RISC-V: может вызвать ошибку или требовать нескольких операций доступа
Заполнение структур:
struct bad { char a; // 1 байт int b; // 4 байта, требует выравнивания по 4 байтам char c; // 1 байт }; // Размер: 12 байт (с заполнением)
Схема памяти:
Смещение: 0 1 2 3 4 5 6 7 8 9 10 11 Значение: a pad pad pad b b b b c pad pad pad
Улучшенный порядок:
struct good { int b; // 4 байта char a; // 1 байт char c; // 1 байт }; // Размер: 8 байт (с заполнением)
Схема памяти:
Смещение: 0 1 2 3 4 5 6 7 Значение: b b b b a c pad pad
Рекомендация: для минимизации заполнения порядок членов структуры должен идти от наибольшего до наименьшего.
Выравнивание по линиям кэша:
Критичные для производительности структуры следует выравнивать по границам линий кэша:
struct __attribute__((aligned(64))) cache_aligned { int data[16]; };
Почему?
Предотвращает ложное совместное использование в многоядерных системах
Гарантирует, что структура не будет разбита на несколько линий кэша
Предсказуемое поведение кэша
Границы массивов и упреждающая выборка
Современные CPU выполняют упреждающую выборку данных, но они не могут выполнять выборку за пределами границ массивов, которые они не знают.
Помогаем prefetcher:
// ПЛОХО: непредсказуемая граница цикла for (int i = 0; i < get_count(); i++) { sum += array[i]; } // ХОРОШО: константная граница цикла int n = get_count(); for (int i = 0; i < n; i++) { sum += array[i]; } // ЕЩЁ ЛУЧШЕ: компилятор видит границу #define SIZE 1000 for (int i = 0; i < SIZE; i++) { sum += array[i]; }
Упреждающей выборке помогает разворачивание циклов:
// Ручное разворачивание for (int i = 0; i < n; i += 4) { sum += array[i]; sum += array[i+1]; sum += array[i+2]; sum += array[i+3]; }
Преимущества:
Снижает оверхед циклов
Обеспечивает больший параллелизм
Помогает prefetcher видеть паттерн
Компилятор может автоматически разворачивать циклы:
#pragma GCC unroll 4 for (int i = 0; i < n; i++) { sum += array[i]; }
Встраиваемые системы: маленькие массивы, большой эффект
Во встраиваемых системах с маленькими кэшами (8-32 КБ) оптимизация массивов ещё более критична.
Пример: микроконтроллер RISC-V с кэшем L1 на 16 КБ
// Этот массив займёт 40% от всего объёма кэша! int buffer[1000]; // 4 КБ
Рекомендации для встраиваемых систем
1. Маленькие массивы
// ПЛОХО: впустую тратит кэш int large_buffer[10000]; // 40 КБ, не умещается в кэше // ХОРОШО: помещается в кэш int small_buffer[1000]; // 4 КБ, умещается без проблем
2. Многократное использование массивов
// ПЛОХО: несколько массивов конкурируют за кэш int input[1000]; int temp[1000]; int output[1000]; // ХОРОШО: многократно используется один и тот же буфер int buffer[1000]; process_in_place(buffer);
3. Использование типов меньшего размера
// ПЛОХО: впустую тратит память и кэш int32_t values[1000]; // 4 КБ // ХОРОШО: если позволяет диапазон int16_t values[1000]; // 2 КБ, в два раза больше данных в кэше
4. Упаковка данных
// ПЛОХО: 4 байта на флаг int flags[1000]; // 4 КБ // ХОРОШО: 1 бит на флаг uint32_t flags[32]; // 128 байт, в 32 раз меньше! void set_flag(int i) { flags[i / 32] |= (1 << (i % 32)); } int get_flag(int i) { return (flags[i / 32] >> (i % 32)) & 1; }
Пример из реального мира: буфер пакетов
Вернёмся к моей проблеме обработки пакетов. Вот, что мы делали не так:
Изначальный код (плохой):
typedef struct { uint8_t data[1500]; // Данные пакета uint32_t length; // Длина пакета uint32_t timestamp; // Временная метка uint32_t src_ip; // IP источника uint32_t dst_ip; // IP получателя uint16_t src_port; // Порт источника uint16_t dst_port; // Порт получателя uint8_t protocol; // Протокол uint8_t flags; // Флаги } packet_t; // Всего: ~1520 байт packet_t packets[1000]; // 1,52 МБ // Обработка пакетов for (int i = 0; i < count; i++) { if (packets[i].protocol == TCP) { process_tcp(&packets[i]); } }
Проблема: каждая итерация получает 1520 байт (24 линий кэша) лишь для одной проверки protocol (1 байт).
Исправленный код (хороший):
// Разделяем горячие и холодные данные typedef struct { uint8_t protocol; // Горячие: проверяется на каждой итерации uint8_t flags; // Горячие: проверяются часто uint16_t length; // Горячие: используется для обработки uint32_t data_offset; // Смещение в массиве данных } packet_header_t; // 8 байт packet_header_t headers[1000]; // 8 КБ uint8_t packet_data[1500 * 1000]; // 1,5 МБ // Обработка пакетов for (int i = 0; i < count; i++) { if (headers[i].protocol == TCP) { uint8_t *data = &packet_data[headers[i].data_offset]; process_tcp(&headers[i], data); } }
Результат:
Заголовки умещаются в кэш (8 КБ против 1,52 МБ)
Первый цикл: в 8 раз меньше линий кэша
Получение данных пакетов только при необходимости
Производительность: 100 тысяч → 950 тысяч пакетов/с (в 9,5 раза быстрее)
Подведём итог
Проблема ужасной производительности конвейера обработки пакетов (100000 пакетов в секунду вместо 1 миллиона) была устранена благодаря пониманию паттернов доступа к массивам. 450000 промахов кэша возникло из-за плохих схемы памяти и порядка доступа. Преобразовав данные в структуру массивов и оптимизировав порядок обхода, мы повысили производительность до 950000 пакетов в секунду, то есть добились ускорения почти в десять раз.
Основные принципы:
Последовательный доступ побеждает произвольный (быстрее в 7-10 раз)
Малые шаги побеждают большие
Обход массивов C по порядку строк
Структуры массивов побеждают массивы структур в случае выборочного доступа к полям
Выравнивание важно (влияет на корректность и производительность)
Рабочий набор должен находиться в кэше
Методики оптимизации:
Изменение порядка циклов (ikj против ijk)
Разбиение на блоки/тайлинг в случае больших массивов
Структура массивов (SoA)
Подходящее выравнивание и заполнение
Разворачивание циклов
Встраиваемые системы:
Малый размер массивов (должны умещаться в кэш)
Многократное использование буферов
Использование малых типов данных
Упаковка данных (битовые массивы)
Разделение горячих и холодных данных
Измерения:
Сначала профилирование, потом оптимизация
Измерение промахов кэша
Тестирование на целевом оборудовании
В следующей главе: мы разобрались, почему массивы быстры. Теперь исследуем, почему медленны связанные списки, и поймём, когда их всё равно стоит использовать.
