Кеш и размер строки кеша
Если ты пишешь код, то наверняка анализируешь алгоритмическую сложность: O(N), O(log N) и прочее. Но оказывается, что даже при одинаковой асимптотике реальное время выполнения может варианть в разы. Причина — архитектура памяти твоего процессора.
Когда ты обращаешься к одному байту в памяти, процессор не загружает в кеш только этот байт. Вместо этого он целиком заполняет так называемую cache line — строку кеша. На современных машинах это обычно 64 байта.
┌─────────────────────────────────────────────┐
│ 64 bytes │
│ byte 0 byte 1 byte 2 ... byte 63 │
└─────────────────────────────────────────────┘
Это сделано не просто так: данные в памяти часто расположены рядом и обращаются к ним последовательно, поэтому кеширование соседних 64 байт — умная стратегия.
Иерархия памяти и задержки
Чтобы понять, почему это критично, посмотри на реальные задержки доступа:
- Регистры: < 1 нс
- L1d кеш: ~1–2 нс (35 КiB на ядро, ~560 строк кеша)
- L2 кеш: ~4–5 нс (2 МiB на пару ядер, ~32 000 строк)
- L3 кеш: ~10–15 нс (12 МiB на всех, ~196 000 строк)
- DRAM: ~60–100 нс
Разница между L1 и DRAM — в 50–100 раз! Поэтому попадание в кеш — это всё.
Пример: структура Monster
Представь, что у тебя есть массив монстров, и тебе нужно отфильтровать живых. Вот структура на 64 байта:
struct Monster {
uint32_t id; // 4 байта
float x, y, z; // 12 байт (позиция)
float vx, vy, vz; // 12 байт (скорость)
int32_t hp; // 4 байта
int32_t attack; // 4 байта
int32_t defense; // 4 байта
uint8_t is_alive; // 1 байт (нужен только этот!)
uint8_t team; // 1 байт
char name[22]; // 22 байта
}; // всего: 64 байта
Когда ты итерируешь по массиву и проверяешь is_alive, каждая итерация загружает в кеш всю строку на 64 байта — ради одного байта данных!
Идея: разделяй структуры
Таким образом, когда тебе нужна только часть данных, размер структуры напрямую влияет на скорость. Классический способ оптимизации — перейти от Array of Structs (AoS) к Struct of Arrays (SoA):
Вместо одного массива Monster[] создай несколько массивов:
struct Monsters {
uint32_t* ids; // отдельный массив
uint8_t* is_alive; // отдельный массив
// остальные поля отдельно
};
Теперь при итерации по is_alive ты загружаешь в кеш плотный массив байтов — одна cache line вместит сразу 64 значения is_alive!
Итог
Манетка простая: каждый добавленный в структуру байт имеет цену, потому что “пассажиры” на одной cache line конкурируют за пространство. Если ты работаешь с большими наборами данных и критична скорость — подумай о раскладке данных в памяти, а не только об O-нотации.