Автор, проработавший много лет с Java, привык добавлять новые поля в класс, не задумываясь о цене. Но оказалось, что размер структуры данных напрямую влияет на скорость — и дело не в алгоритмической сложности, а в том, как процессор таскает данные из памяти.
Сначала — железо. Команда lscpu показывает кэши: L1d — 352 KiB на 10 ядер (то есть ~35 KiB на ядро), L2 — 10 MiB на 5 пар ядер, L3 — 12 MiB общий. Размер cache line — 64 байта. Когда читаешь хотя бы один байт, железо подтягивает все 64 байта в кэш. Задержки: регистры <1 ns, L1d ~1–2 ns, L2 ~4–5 ns, L3 ~10–15 ns, DRAM ~60–100 ns.
Дальше — пример с монстрами. Есть структура Monster размером 64 байта. Если хранить массив таких структур (Array of Structs), то каждый cache line вмещает ровно одного монстра. Чтобы достать только поле is_alive (один байт), процессор тащит все 64 байта. Если же разложить данные по отдельным массивам (Struct of Arrays), то в одну cache line помещается 64 значения is_alive. Для структуры размером 1 KiB разница достигает 30 раз.
При последовательном обходе CPU-префетчер подтягивает следующие cache line заранее, и задержка почти не чувствуется. Но при случайном доступе — хэш-таблицы, деревья, обход графов — префетчер пасует. Процессору нужно, чтобы весь рабочий набор целиком помещался в кэш. Чем больше структура, тем быстрее данные вываливаются в более медленные уровни.
Таблица из статьи: при 512 монстрах структура в 64 байт занимает 32 KiB — помещается в L1d (~3 ns). Та же структура в 128 байт — уже 64 KiB, вылетает в L2 (~11 ns). При 131072 монстрах разница становится ещё заметнее: 8 MiB (64B) — ~163 ns, 16 MiB (128B) — ~162 ns (уже в DRAM). На графике pointer-chasing видно, что все размеры проходят одни и те же «ступеньки» кэшей, но крупные структуры сдвинуты влево — попадают на более медленные уровни при меньшем количестве элементов.
Вывод: контроль над размером структуры и общего рабочего набора даёт огромный выигрыш в производительности, особенно при хаотичном доступе.