Что можно сделать с массивом массивов

На одном из проектов (4Х историческая стратегия) появилась задача убрать часть логики в потоки, отдав им снапшот игрового состояния, чтобы пока основной поток считает свой тик, остальные (AI, поиск пути, UI и др) могли крутить свою логику, вроде "кто стоит в этой локации" и делать это без блокировок или риска увидеть половину чужой записи. Чтобы реализовать такую систему, надо придумать как получить обратный индекс полка по локации, причем сделать поиск дешевым для потоков, т.е. у потока должен быть свой снапшот состояния некоторой части игрового мира на момент старта апдейта (кадра, тика логики, дня, месяца и т.д)

Общепринятая практика - это сделать данные иммутабельными на время кадра, и построить нужный индекс один раз на старте, а дальше дать читателям возможность работать с ним. И вообщем от ребят, которые делали эту задачу на ревью прилетел вот такой код (выделю тут только основную часть):

struct Regiment {
    unsigned int location;
    float        health;
    float        mood;
    float        speed;
};

std::vector<Regiment> regiments; // все полки мира
std::vector<std::vector<unsigned int>> by_location(location_count);

for (unsigned int r = 0; r < regiment_count; ++r) {
    by_location[regiment_location[r]].push_back(r);
}

... тут мы что-то делаем с полученным массивом 

Такая структура (regiments) называется jagged array, массив массивов (зачем она и как с ней работать я показывал в книге Game++), или, если вам ближе академическая терминология, CSR (compressed sparse row) немного другая форма записи таких массивов, либо разреженные матрицы. И такие стуктуры довольно частое явление в играх, если у вас много локаций и вам надо:

• узнать какой лут разложен в каждой локации, какие армии принадлежат каждой области;

• или какие монстры живут в локации, какие локации входят в область, какие области в регион;

• или почекать соседей локации на карте, adjacency region, на чем строится pathfinding и вся заливка областей в глобальных стратегих;

• или найти узлы в иерархии сцены или в скелете;

• поискать сущности по чанку мира, компоненты по сущности, entity по архетипу в ECS;

• найти подписчиков по типу события, активные модификаторы по объекту

• походить по соседям локации и пособирать метрики

• выбрать полки по армии / корпусу, чтобы посчитать суммарный health и средний mood соединения;

• то же отношение "владелец → набор сущностей" для зданий в локации, ордеров на рынке, модификаторов на стране, соседей на карте, entity по чанку в ECS.

• и еще много чего...

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

Еще одно неявное свойство - эту структуру мы обновляем редко, а читаем много раз. Обновляем на загрузке карты, на старте кадра или после перестройки сцены и в целом когда - уже не важно, но важно, что фазы build и query разделены. Выглядит как достаточно жёсткое ограничение, но посмотрите на список выше... там почти все данные на некотором интервале времени не меняют свою позицию внутри общей структуры и это открывает дорогу к разным трюкам и хакам.

Идея vs реальная жизнь

И вроде всё хорошо, пока у вас этот массив массивов маленький, но для нашего кейса использования выяснилось, что снапшот такой структуры после середины игры стоит дороже, чем вся работа, ради которой его делали и например скопировать std::vector<std::vector<unsigned int>> на миллион локаций - это глубокая копия миллиона векторов занимает 90 миллисекунд (на моей машине, на цифры не смотрите он показательные и важно отношение одного к другому, а не абсолютное время). Полный обход этой же структуры, ради которого снапшот и нужен, занимает 14 миллисекунд, т.е. мы собирались распараллелить работу на 14 мс и заплатили 90 мс просто, чтобы начать. Для тестов я взял миллион элементов во внешнем массиве и шесть миллионов элементов суммарно во внутренних, то есть в среднем шесть на список, что на самом деле немного и столько суммарно набегает в разных системах к середине сессии где-нибудь в Victoria3/EU4.

Давайте посчитаем, за что мы заплатили. Cам внешний массивstd::vector на 64-битной системе будет 24 байта (три указателя, либо указатель плюс два размера) и миллион элементов занимает 24 мегабайта только на служебную обвязку, ещё до всяких данных, причём эти 24 байта платятся за каждую локацию, включая пустые. И если юниты стоят в пяти процентах локаций карты, то остальные 95% честно занимают свои 24 байта, но, что хуже, занимают и место в кэше, когда вы по этому массиву массивов проходите.

Еще одно неявное свойство, которое часто упускают - это запас (capacity) и реальный размер блока памятиvectorа растёт быстрее, чем реальный размер вектора, и наши 6 элементов, на самом деле занимают восемь "объемов" данных.

Это еще не все и тут надо вспомнить про метаданные аллокатора и округление блока, которые от нас скрыты но тоже занимают место в кучу, и у glibc заголовок чанка плюс выравнивание превращают запрос на 32 байта в блок на 48, то есть на данные, которых всего 24 байта, потрачено 48.

Но и это еще не все, и чтобы дойти до capacity 8, вектор аллоцируется четыре раза, и три раза при этом копирует уже накопленное, поэтому на постройку миллиона списков у нас будет примерно четыре миллиона malloc и три миллиона free. Пусть это уже не про память и это все растянуто по фреймам, но это чистое время, которое вынуждены забрать у игры, я называю это "размазаным" перфом, в смысле что мы "размазали" наше время кадра по множеству мелких мест. Итого получаем на элемент (~примерно): 24 байта на внешний vector, 48 байт на блок в куче и семьдесят два байта, чтобы сохранить двадцать четыре.

Наивная схема, миллион локаций:
regiments[]                   куча (блоки разбросаны)
+----------------+            +--------------------------+
| ptr size cap   | ---------> | hdr | 7 idx | 2 unused  |  48 байт
+----------------+            +--------------------------+
| ptr size cap   | ---------> | hdr | 4 idx | 2 unused  |  48 байт
+----------------+            +--------------------------+
| ptr size cap   | --> nullptr   (локация пустая, но 24 байта урплочены)
+----------------+
   24 байта              +          48 байт          = 72 байта на 24 полезных 
// примерно, зависит от режима сборки

regiments[]  [ {loc, health, mood, speed}, ... ]   // плотный массив сущностей

И вот возникает важный момент, из-за которого вообще имело смысл лезть внутрь этого кода и что-то чинить внутри массива массивов, и вся эта математика с байтами выше и разговор про размер памяти это всего лишь следствие, а главная причина - опять кеш. Когда игровой апдейт идет по локациям и для каждого полка читает mood и speed, процессор на каждый список делает минимум два обращения за индексом: одно в by_location[i], второй по указателю в кучу, потом еще один за данными. Но второй и (особенно) третий прыжок будет почти гарантированным промахом, когда cpu придется остановить работу сходить в L2/L3 или вообще в оператику, потому что блоки лежат вразнобой (может быть между чужими аллокациями других подсистем игры) и пока процессор ждёт ответа от памяти, он не делает ничего, что превращает такие пустые такты в просадку кадра, когда "у вас всего миллион объектов".

Замеры, чтобы дальше было с чем сравнивать

Дальше по тексту я буду возвращаться к первому бенчмарку (миллион локаций, шесть миллионов структур, случайное распределение по локациям с длинным хвостом, x86-64, MSVC 19.4 в релизе). Длинный хвост означает, что часть ваших данных выпадает из кеша и за ними приходится идти в оперативку. Меряется отдельно:

• build - построить индекс локация → сущности с нуля;

• query - пройти все списки по порядку локаций (прочитать health / mood / speed) и выполнить какую-то логику над ними;

• query random - то же самое, что и build, но локации обходятся в случайном порядке (так выглядит реальный запрос из геймплея, когда игрок что-то делает в процессе игры);

• snapshot - глубокая копия индекса для другого потока (начало кадра, раскидываем данные по потокам);

• teardown - освободить индекс (редко, такое надо откладывать на конец фрейма).

Почему аллокаций так много? А потому что мы не знаем длину каждого списка заранее, отсюда получаем и рост capacity, и цепочку реаллокаций, и запас в буфере.

Хак первый

Но нам никто не мешает узнать у каждой сущности location - данные-то уже есть и надо просто пройти по ним лишний раз и посчитать, поэтому...

struct RegimentList {
    unsigned int count   = 0;
    unsigned int written = 0;
    unsigned int* data   = nullptr;
};

std::vector<RegimentList> by_location(location_count);

// проход 1: сколько полков в каждой локации
for (unsigned int r = 0; r < regiment_count; ++r)
    by_location[regiments[r].location].count++;

// проход 2: выделить ровно столько, сколько надо
for (unsigned int i = 0; i < location_count; ++i)
    if (by_location[i].count > 0)
        by_location[i].data = new unsigned int[by_location[i].count];

// проход 3: разложить индексы
for (unsigned int r = 0; r < regiment_count; ++r) {
    RegimentList& list = by_location[regiments[r].location];
    list.data[list.written] = r;
    list.written++;
}

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

Заодно мы выбросили std::vector из внутренних списков и нам стали не нужны его size и capacity, длину мы уже знаем, а расти список больше не будет до следующего апдейта. Там осталась только структура на 16 байт вместо 24 и один блок в куче на непустой.

Отдельно скажу про соблазн заменить всё это на reserve() с угаданным числом. Работать это не будет, угадали мало и вернулись к реаллокациям, угадали много и заплатили памятью за все миллион списков сразу, а тут мы не угадываем, мы считаем сколько будет у нас в памяти и раскладываем эти данные. Давайте посмотрим, что получилось после этого трюка:

А получилось очень интересно, мы и build ускорилил и память упала в полтора раза, а вот query почти не изменился, что логично, поскольку мы всё ещё делаем два прыжка по памяти на список, прежде чем добраться до regiments[id].mood. Зато улучшилось время рандомной выборки, потому что данные лежат плотнее и их больше влезает в кеш.

Хак второй

Заметили что каждый список все равно остался жить в своей аллокации? Пусть вектора мы убрали, но сами аллокации никуда не делись, поэтому остались и метаданные кучи, и разбросанность в памяти, и необходимость таскать в каждой записи 8-байтовый указатель.

Если мы на первом шаге посчитали размеры, почему теперь не выделить и один большой буфер под все списки и разложить их в нём подряд? Тогда мы получим только одну аллокацию и разложенные по смещениям списки, и указатель оказывается не нужен и будет достаточно смещения, и если вы не будете аллоцировать за 4Гб, то смещение прекрасно живёт в 32 битах. Как вы видите данных у нас всего-то 48Мб и нам это вполне подходит.

Для решения этой задачи почти не нужно нового кода, в предыдущем варианте пришлось ввести offset для каждого списка, чтобы было знать, в какой слот писать следующий элемент. Разница лишь в том, что теперь offset стартует не с нуля, а с суммы длин всех предыдущих списков, это известный трюк и называется он - префиксная сумма.

struct RegimentList {
    unsigned int count  = 0;
    unsigned int offset = 0;
};

std::vector<RegimentList> by_location(location_count);
for (unsigned int r = 0; r < regiment_count; ++r)
    by_location[regiments[r].location].count++;

// префиксная сумма: где начинается список каждой локации
unsigned int sum = 0;
for (unsigned int i = 0; i < location_count; ++i) {
    by_location[i].offset = sum;
    sum += by_location[i].count;
}

// одна аллокация на все индексы сразу
std::vector<unsigned int> data(sum);
for (unsigned int r = 0; r < regiment_count; ++r) {
    RegimentList& list = by_location[regiments[r].location];
    data[list.offset] = r;
    list.offset++;
}

// offset уехал вперед на длину списка, надо вернуть на место
for (unsigned int i = 0; i < location_count; ++i)
    by_location[i].offset -= by_location[i].count;

Как теперь наши данные будут лежать в памяти:

Слитая схема:
regiments[]                  blob[] — один буфер на всё
+---------------+            +---+---+---+---+---+---+---+---+---+---+---+
| cnt=1 off=0   |----------> | 0 |                                       |
+---------------+            +---+---+---+---+---+---+---+---+---+---+---+
| cnt=6 off=1   |--------------->| 1 | 2 | 3 | 4 | 5 | 6 |
+---------------+                +---+---+---+---+---+---+---+---+
| cnt=5 off=7   |--------------------------------------->| 7 | 8 | ...
+---------------+                                        +---+---+
   8 байт            +        24 байта данных      = 32 байта на 24 полезных

// данные лежат отдельно
regiments[]  [ {loc, health, mood, speed}, ... ]

И что получится по времени:

Пятнадцать раз... не процентов, с этим можно идти хоть к техлиду, хоть на конференцию и гордо нести флаг превозмогания. Аллокаций стало две - на массив описаний и на буфер индексов, но снапшот индекса перестал быть глубокой копией миллиона векторов и стал двумя memcpy с 5мс вместо 90 и освобождение тоде два free вместо сотен тысяч. Случайный обход ускорился примерно втрое относительно первой версии, потому что соседние списки полков теперь лежат в плотно, и префетчер успевает подтаскивать нужные данные для расчетов. Сами сущности при этом можно снапшотить отдельно, одним копированием плотного массива, а можно и не снапшотить... главное в процессе расследования не выйти на самих себя :) Оказывается, что дорогим была именно удобная реализация jagged index через стандартные контейнеры, а не доступ к массиву сущностей.

Не думайте, что я такой умный... как обычно все уже придумано до нас, этот трюк придумали еще в восьмидесятых для раскладки спрайтов в памяти на NES с максимальной упаковкой, потому что памяти было мало, а спрайтов много :) И там оффсеты были индексами спрайтов, когда вы хотели отрисовать его на экране.

А заодно мы получаем набор бонусов, теперь эта структура сериализуется как есть и её можно положить в сейв без обхода, получаем просто два fwrite, а на загрузка другие два fread, и никакой починки указателей после чтения. И еще она просто копируется одним memcpy и если нужен снапшот структуры для другого потока, то можно просто скопировать два буфера и не нужно никакого глубокого копирования миллиона векторов.

Продолжаем список бонусов... теперь эта структура может жить в линейном аллокаторе и если она строится раз в кадр, её можно целиком положить в память на старте кадра и обнулить указатель в начале следующего и вообще избавиться от free, а еще такая структура перестала ломаться при релокации и перемещении, если вдруг понадобилось её переместить то индексы останутся валидными.

Хак третий

Этот хак приехал через полгода использования новой структуры в игре, когда кто-то из коллег обратил внимание, что можно оптимизировать длины списков. Смотрите что получается с длинами:

count:   [ 1   7   4   4  5  ]
offset:  [ 0   1   8  12  16 ]

А теперь, что получается в массиве смещений:

offset:  [ 0   1   8  12  16 ]
   count:  [ 1   7   4   4  ... ]

Длина списка i будет разностью двух соседних смещений count[i] == offset[i + 1] - offset[i]. Так получается потому, что все списки лежат в одном буфере подряд, и конец одного списка есть начало следующего, а значит, поле длины можно не хранить и надо только дописать в массив смещений один элемент в конец, который показывает на конец последнего списка. Остается один массив на N + 1 элемент.

// N + 1 элемент: полки локации i лежат между offsets[i] и offsets[i + 1]
std::vector<unsigned int> offsets(location_count + 1);

// offsets[0] стартует с нуля и нулем остается
unsigned int* offsets1 = &offsets[1];

// проход 1: считаем длины, но пишем их со сдвигом на единицу
for (unsigned int r = 0; r < regiment_count; ++r)
    offsets1[regiments[r].location]++;

// проход 2: превращаем длины в смещения на месте
unsigned int sum = 0;
for (unsigned int i = 0; i < location_count; ++i) {
    unsigned int count = offsets1[i];
    offsets1[i] = sum;
    sum += count;
}

// проход 3: раскладываем индексы; смещения сами доезжают до правильных значений
std::vector<unsigned int> blob(sum);
for (unsigned int r = 0; r < regiment_count; ++r) {
    const unsigned int location = regiments[r].location;
    blob[offsets1[location]] = r;
    offsets1[location]++;
}

// четвертый проход не нужен: offsets1[i] доехал ровно до offsets[i + 1]

А обходить мы такой массив будем так:

const unsigned int begin = offsets[location];
const unsigned int end   = offsets[location + 1];
for (unsigned int i = begin; i < end; ++i) {
    const Regiment& regiment = regiments[data[i]];
    if (regiment.mood < 0.25f || regiment.health <= 0.0f) {
        continue;
    }
    travel_budget += regiment.speed;
}

Финальная схема:
offsets[]  [ 0 | 1 | 8 | 12 | 16 | 21 ]        N + 1 элемент, по 4 байта
             \___/\___/\__/
              loc0 loc1  loc2
blob[]     [ 0 | 1 2 3 4 5 6 7 | 8 9 10 11 12 | ... ]
   4 байта     +     24 байта данных     = 28 байт на 24 полезных

Убрав всего четыре байта на элемент ( и четырех мегабайт на все сущности ) получили структуру как её в академической литературе описывает CSR... помимо всего прочего, получили формат, который понимают библиотеки разреженной линейной алгебры. Это нам, правда, не сильно помогло, потому что непропатченый Eigen работает раза в два медленнее нашей собственной математики, но об этом в другой раз...

На маленьких размерах (100 и 1k) все варианты почти неотличимы, потому что данные целиком в кеше и разрыв мы получаем ближе к 64k-128k, и становится достаточно большим при достижении миллиона объектов.

Относительно последнего варианта сборка быстрее в 17 раз, снапшот в 23 раза, освобождение в 32 раза, случайный обход в 3.6 раза, памяти в 2.4 раза меньше, аллокаций две вместо трех с половиной миллионов.

Почему выигрыш в реальном коде будет даже больше

Вы заметили строку с фрагментированной кучей? Такое происходит, если во время сборки нашего массива массивов, другая подсистема игры успевает аллоцировать свои блоки между нашими массивами, что происходит в 99% случаев в большой игре и потом половина из них остается в виде дыр, и вместо 63 МБ где-то в близком блоке памяти, мы получаем в три раза большую область, на которой раскиданы блоки, что выразится уже в стоимости работы всего алгоритма, и такая фрагментация бьет и по скорости чтения, и по стоимости жизненного цикла.

В наивной версии, которая пришла на ревью, на каждый список процессор делает два независимых обращения к памяти и эти обращения связаны, а префетчер их все равно не видит. Кэш-линия всего 64 байта, и в неё влезает либо два с половиной внешних vector, либо шестнадцать индексов, то есть в наивной схеме мы на каждый список запрашиваем в кэш минимум две линии, из которых используем только 24 байта из 128. А в последнем варианте одна линия blob[] покрывает уже два-три списка целиком, а offsets[] читается последовательно и префетчер просто подкладывает следующие блоки данных в кеш L1, т.е. мы получаем выигрыш от того, что правильно оптимизировали данные под структуру процессора

За всё приходится платить, и тут придется расплачиваться железобетонностью этой структуры. Если списки надо менять произвольно, то вставка в середину означает сдвиг всего буфера, т.е. это не структура для динамики и если у вас список меняется по одному элементу в ответ на игровые события, то лучше оставить вектор векторов. Но очень часто получается изменить задачу так, чтобы перестраивать индекс целиком один раз (за кадр например), и что полная перестройка миллиона элементов выходит дешевле, чем держать вектор векторов.

Почему миллион

В глобальных стратегиях вроде Civilazation, Stellaris, Victoria, Humankind будет не "миллион провинций на карте". Карта редко превышает 16 тысяч локаций (~12k суша, ~3k море), но каждая страна имеет свой снапшот локаций, каждый режим отображения добавляет еще один слой, чтобы вы могли быстро переключиться с общего вида на леса, или дороги, или прибыльность. И миллион набегает как сумма живых объектов симуляции, а не как размер одного массива locations[].

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

А еще накладывается экономика, каждый тип здания тоже порождает свою карту локаций, добавьте сюда города, уникальные постройки, уровни, рынки, торговые ордера, спрос/предложение по товарам на рынок и локацию. К концу игры это все превращается в тысячи отдельных сущностей, каждая со своим health / mood / speed.

А еще есть временные и производные объекты, вроде модификаторов на страну/локацию/армию/персонажа, подписчики на события, пути. Вы их никогда не увидите на карте, но в памяти и в индексах они есть в виде «владелец → набор сущностей».

Поэтому в бенче «миллион слотов снаружи, шесть миллионов индексов внутри» это не буквальный размер карты стратегии, но порядок числа объектов, до которого вырастает игра к середине длинной партии. Поэтому в следущий раз открывая диспетчер задач и удивляясь почему игра заняла 24 гигабайта оперативки... не удивляйтесь, вот по названным выше причинам. И надо еще как-то заставить все эти гигабайты шевелиться :)

Это было еще до игр и ECS

Придумано это было задолго до нас, и даже не в геймдеве. Раскладку в виде "посчитать, префиксная сумма, разложить" известна вообще с середины 1950-х и идея хранить разреженную структуру парой массивов "смещения плюс данные" пришло из линейной алгебры конца 1960-х, как я уже упоминал про CSR и Yale format. Мы просто "придумали" и применили к нашим проблемам и поиску локациям "немного" численных методов из работы с матрицами.

Этот приём, который возможно вам понравится и вы возьмете его себе в проект, вообще не про jagged arrays. Он про разделение операции на build и query, чтобы появилась возможность построить данные в форме, которая радикально лучше подходит для чтения. Это работает не только со списками и так устроены навигационные меши, так работают архетипы в ECS, так живут вершинные буферы, и получается что мы платим за структуру один раз на этапе сборки, чтобы не платить каждый раз на чтении.

Когда я с коллегами готовил презентацию этого решения для команды, то наткнулся на статью Efficient jagged arrays 2023 года, где он пришел к той же укладке для вертексов в меше для своего проекта. Мы шли со стороны игровых сущностей и снапшота между потоками, а он со стороны индексов треугольников, но в итоге пришли к одной и той же схеме. Само по себе это хороший признак, что задача встречается в разработке достаточно часто, чтобы не изобретать ее заново и найти какое-то более переиспользуемое решение. К сожалению, я такого в открытом доступе не нашел... возможно плохо искал.

Фундаментально задача осталась той же, что и в 80-х и раньше, надо чтобы данные оказались в правильном месте, в правильной форме, к тому моменту, когда по ним пойдёт хотпас.

Если эта публикация вас вдохновила и вы хотите поддержать автора — не стесняйтесь нажать на кнопку