Разработчики 4X-исторической стратегии столкнулись с классической проблемой производительности при работе с многопоточностью. Задача заключалась в том, чтобы вынести часть логики в отдельные потоки, передав им снапшот игрового состояния. Это позволило бы основному потоку обрабатывать свой тик, пока другие потоки (AI, поиск пути, UI) параллельно выполняют свои вычисления без блокировок.
Для реализации такой системы потребовалось создать обратный индекс полков по локации — структуру, позволяющую быстро определить, какие юниты находятся в каждой точке игрового мира. На ревью был представлен код, использующий jagged array (массив массивов), который в академической терминологии известен как CSR (compressed sparse row) или разреженные матрицы.
Типичная задача в глобальных стратегиях
Структура jagged array широко применяется в игровой разработке. Она позволяет эффективно хранить данные о том, какой лут разложен в каждой локации, какие армии принадлежат областям, какие монстры населяют территории, а также для построения путей и заливки областей в глобальных стратегиях.
Отношения между элементами уже присутствуют в исходных данных — не нужно придумывать новые связи, достаточно построить структуру для быстрого выбора набора. Например, если есть список армий с указанием их расположения, то нужен обратный индекс для константного времени доступа без лишней нагрузки на кэш процессора.
Неожиданная цена копирования
Основная проблема выявилась при создании снапшота структуры для потоков. Копирование std::vector на миллион локаций заняло 90 миллисекунд. Для сравнения, полный обход этой же структуры, ради которого и нужен снапшот, занимает всего 14 миллисекунд.
| Ключевые факты | |
|---|---|
| Время копирования jagged array на 1 млн локаций | 90 мс |
| Время полного обхода той же структуры | 14 мс |
| Объем служебных данных на одну пустую локацию | 24 байта |
| Фактический расход памяти на 6 элементов | 72 байта (вместо 24) |
Таким образом, попытка распараллелить работу на 14 мс оборачивается затратой 90 мс только на подготовку данных. Причина — высокая стоимость глубокого копирования миллиона векторов.
Структура затрат: откуда берутся 72 байта на 24 байта данных
Внешний массив std::vector на 64-битной системе занимает 24 байта (три указателя или указатель плюс два размера). Миллион элементов — это 24 мегабайта только на служебную обвязку, причем эти 24 байта платятся за каждую локацию, включая пустые. Если юниты стоят лишь в 5% локаций, остальные 95% честно занимают свое место в кэше.
Кроме того, реальный размер блока памяти вектора растет быстрее, чем фактический размер данных. Для 6 элементов capacity обычно составляет 8, что уже дает 8 «объемов» данных. Метаданные аллокатора и округление блоков (особенно в glibc) превращают запрос на 32 байта в блок на 48 байт.
Цена аллокаций: четыре миллиона malloc на миллион списков
Чтобы достичь capacity 8, каждый внутренний вектор аллоцируется четыре раза, причем трижды копирует уже накопленное. Для миллиона локаций это примерно четыре миллиона malloc и три миллиона free. Хотя эти операции растянуты по фреймам, они отнимают процессорное время, которое можно было бы использовать для игровой логики.
Что это значит для разработчиков
История с jagged array — не единичный случай. Подобные структуры часто встречаются в ECS-системах, поиске соседей на карте, работе с модификаторами и ордерами. Ключевой вывод: фазы build и query должны быть разделены, а стоимость построения структуры не должна превышать выгоду от ее использования.
Для тех, кто работает с игровой логикой, особенно в многопоточных сценариях, стоит внимательно оценивать накладные расходы на создание снапшотов. Иногда более эффективным решением может быть иммутабельность данных на время кадра с однократным построением индекса на старте, а не глубокое копирование всей структуры.
