C++ Academy · Урок

Структуры данных, эффективные для кэша

Проектируйте структуры массивов и упаковывайте данные для локальности кэша.

«Структуры данных, эффективные для кэша» — бесплатный урок C++ Academy на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения C++ Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс C++ Academy содержит 4 уроков всего.

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

У CPU есть несколько уровней кэша (L1, L2, L3), которые работают гораздо быстрее основной памяти. Код, оптимизированный для кэша, хранит часто используемые данные ближе к CPU.

Строки кэша

Память загружается строками кэша — обычно по 64 байта. Чтение одного байта загружает всю строку. Используйте это в своих интересах.

Локальность обращений

Важны два свойства:

Пространственная локальность — скорое использование близлежащей памяти
Временная локальность — скорое повторное использование той же памяти

Непрерывное хранение и связные структуры

Векторы хранят данные непрерывно, поэтому их обход хорошо использует кэш. Связные списки распределяют элементы по разным участкам памяти, вызывая промах кэша на каждом шаге.

// Cache friendly
std::vector<int> v(1000);
for (auto& x : v) ++x;

// Cache UNfriendly
std::list<int> l(1000);
for (auto& x : l) ++x;

AoS и SoA

Два способа размещения массивов записей:

AoS (массив структур) — естественный вариант, но при обходе одного поля затрагиваются все поля
SoA (структура массивов) — лучше, когда большинство циклов использует только некоторые поля

// AoS
struct Particle { float x, y, z, vx, vy, vz; };
std::vector<Particle> particles;

// SoA
struct Particles {
    std::vector<float> x, y, z, vx, vy, vz;
};

Упаковка структур

Располага‍йте члены от самых крупных к самым маленьким, чтобы свести дополнение к минимуму. Такие инструменты, как pahole, показывают фактическое размещение.

struct Bad  { char c; double d; char c2; };  // padded
struct Good { double d; char c; char c2; };  // smaller

Ложное совместное использование

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

struct alignas(64) Counter {
    std::atomic<int> value;
};

Разделение часто и редко используемых данных

Разделяйте часто используемые данные и редко используемые данные, помещая их в разные структуры. CPU кэширует только часто используемую часть.

Предварительное выделение памяти

Заранее выделяйте память для векторов с помощью reserve, чтобы избежать повторных перераспределений. При каждом перераспределении копируются все элементы — это дорого и приводит к промахам кэша.

Преимущество последовательного доступа

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

Избегайте косвенной адресации

Указатели заставляют CPU отслеживать зависимости. std::vector<T*> при обходе работает медленнее, чем std::vector<T>. Используйте косвенную адресацию только при необходимости.

Профилируйте до оптимизации

«Оптимизация под кэш» — это рекомендация, а не правило. Измеряйте с помощью таких инструментов, как perf или VTune, чтобы увидеть, где промахи кэша снижают производительность, а затем оптимизируйте.

Быстрая проверка

Почему обход std::vector обычно намного быстрее обхода std::list того же размера?

Итоги

Современные CPU зависят от кэшей. Предпочитайте контейнеры с непрерывным размещением, используйте SoA для выборочного доступа к полям, упаковывайте структуры, избегайте ложного совместного использования и профилируйте промахи кэша с помощью perf или VTune, чтобы находить узкие места.

Часто задаваемые вопросы

Урок «Структуры данных, эффективные для кэша» бесплатный?

Да — полный текст урока «Структуры данных, эффективные для кэша» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс C++ Academy, подпишись на CoddyKit PRO. Курс C++ Academy содержит 4 уроков всего.

Чему я научусь в уроке «Структуры данных, эффективные для кэша»?

Проектируйте структуры массивов и упаковывайте данные для локальности кэша. Ты практикуешь C++ Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать C++ Academy?

Предыдущий опыт не требуется. C++ Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.

Сколько времени занимает урок «Структуры данных, эффективные для кэша»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке C++ Academy?

Да. Каждый урок C++ Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

Структуры данных, эффективные для кэша
Предсказание ветвлений и горячие циклы
Профилирование с perf, vtune и санитайзерами
Микротестирование с Google Benchmark

← Назад к C++ Academy