Оптимизация хранения данных
Этот пост является частью серии, в которой я рассказываю о своем опыте создания игрового движка ECS с нуля. Посетите домашнюю страницу этого проекта, чтобы получить дополнительные сообщения, информацию и исходный код.
В следующих нескольких сообщениях в блоге мы собираемся погрузиться в самую суть. Я оставлю это как предупреждение: на самом деле для ECS ничего из этого не требуется. Разница в производительности в подавляющем большинстве игр будет незначительной и, в конечном итоге, значительно усложнит внутреннюю работу диспетчера компонентов. Если ваша цель - просто создать ECS и заставить ее работать, пропустите остальные сообщения блога 4.x Nomad Engine и начните читать Часть 5: Системы.
Тем не менее, информация в этих сообщениях * невероятно крутая * и очень уникальная. Вы познакомитесь с радостями шаблонного метапрограммирования с очень конкретными примерами из-за того, что мы создаем очень конкретную систему: игровой движок. Если вы хотите расширить свой кругозор, читайте дальше!
Цель этих сообщений в блоге - обосновать обоснование следующих двух сообщений, предоставив архитектуру и объяснение высокого уровня.
Массив структур против структуры массивов
Давайте быстро оглянемся на нашу реализацию для нашей первой итерации «универсального диспетчера компонентов». Наша структура хранения выглядела так:
struct ComponentData {
unsigned int size = 1;
std::array<ComponentType, 1024> data;
}
Обратите внимание, что наши данные хранятся в виде массива структур (в данном случае структура - это ComponentType). В оставшейся части этого сообщения в блоге мы будем использовать пример компонента, с которым мы столкнулись, но добавим к нему немного дополнительных «вещей»:
struct Transform {
int x;
float y;
double z;
}
Позвольте мне сказать заранее: реальный компонент, очевидно, не будет выглядеть так. Мы делаем это только для того, чтобы наши примеры имели больше смысла. Фактически, большинство компонентов будут иметь разные типы членов, поэтому это будет имитировать его, не делая их имена слишком сложными.
Что такое хранилище «SoA»?
Структура хранения массива переворачивает общепринятое соглашение о программировании с ног на голову. Вместо хранения массива структур создается структура с массивом для каждого элемента исходной структуры. Эту концепцию лучше всего проиллюстрировать на реальном примере.
//Array of structs
struct Transform {
int x;
float y;
double z;
}
std::array<Transform, 1024> aos;
//Struct of arrays
struct soa {
std::array<int, 1024> x;
std::array<float, 1024> y;
std::array<double, 1024> z;
}
Почему хранилище SoA лучше?
Прежде чем ответить, позвольте мне пояснить, что на самом деле не всегда лучше. Что лучше - SoA или AoS-хранилище, в основном зависит от того, как используется компонент.
//Probably best as AoS storage
struct Transform {
float x;
float y;
float z;
}
Хранилище Array of Structs лучше, когда все поля компонента обычно доступны одновременно. Например, у нас может быть компонент Transform со значениями x, y и z - каждый из них, вероятно, будет доступен вместе, поскольку не так много ситуаций, в которых мы хотели бы только значение x компонента.
//Probably best as SoA storage
struct Health {
float currentHealth;
float maxHealth;
float healthRegen;
int shieldAmount;
int shieldModifier;
bool isImmune;
}
Хранилище структуры массивов лучше, когда в компоненте есть несколько полей, к которым можно получить доступ индивидуально. Например, если мы посмотрим на наш компонент "Здоровье", который мы определили выше, вполне вероятно, что разные системы будут обновлять разные части компонента сами по себе. Система может отвечать за обновление работоспособности компонента на основе его значения healthRegen, а другая система может управлять иммунитетом. Когда сущность получает урон, независимо от того, какая система за это отвечает, потребуется доступ к currentHealth, shieldAmount и isImmune, но не нужно заботиться о maxHealth или healthRegen. В подобных ситуациях лучше использовать хранилище Struct of Array.
Вот несколько гифок с шаблонами доступа к хранилищу для каждого из этих двух сценариев, чтобы проиллюстрировать этот момент:
Пример 1
Мы собираемся выполнить следующий код в компоненте Transform и сравнить шаблон доступа к памяти между AoS и SoA:
Еще раз: если вы не видите суть в строке из-за того, что работаете на iOS, попробуйте открыть его в браузере (средний: исправьте ошибки).
В этом примере мы предположим, что никакие объекты не находятся за пределами границ (это, вероятно, будет наиболее вероятным случаем, учитывая, что этот код будет запускаться каждый тик). Это означает, что наши обращения к памяти выглядят так:
Вы заметите, что оба они читают память последовательно. Это отлично подходит для повышения производительности, поскольку означает меньшее количество промахов в кеш-памяти. В зависимости от размера наших различных уровней кеша решение AoS может быть немного лучше, но в целом они оба получают доступ к данным последовательно, что означает, что наш процессор сможет максимально использовать наш кеш.
Пример 2
Вместо этого давайте еще раз взглянем на наш компонент здоровья, который мы представили ранее в этом посте. Мы собираемся внедрить вышеупомянутую «систему регенерации», которая увеличивает здоровье сущностей на основе их регенерации здоровья. Вот код:
Теперь давайте посмотрим на шаблон доступа к памяти в зависимости от того, как мы храним компонент:
Вы заметите, что в версии хранилища AoS очень много пустого места! Это связано с тем, что мы обращаемся только к двум полям в компоненте, поэтому остальные без причины втягиваются в кеш. Версия SoA по-прежнему имеет отличную производительность кеширования, поскольку в нее загружаются только необходимые поля компонентов.
Время математики!
Хотя визуализации могли убедить вас сами по себе, если вы все еще не уверены, давайте подумаем!
Большинство компьютеров имеют размер строки кэша 64 байта. Предположим, что наш компонент "Здоровье" таков, как мы определили его выше, что означает, что он займет:
float(4 bytes) * 3 = 12 bytes int(4 bytes) * 2 = 8 bytes bool(1 byte) * 1 = 1 byte
Я обращусь к фактическому пространству, которое эта структура будет занимать ниже (из-за заполнения структуры), но предположим, что тогда структура составляет 12 + 8 + 1 = 21 байт.
Предположим, мы выполняем приведенный выше код для восстановления здоровья. Если мы сохраняем структуру с использованием хранилища AoS, каждая строка кэша, которую мы извлекаем, будет содержать 3 полных компонента (64 / 21 ~= 3).
Давайте представим, что в нашей игре на экране 10 000 сущностей, которые восстанавливают здоровье каждый тик. Если мы используем хранилище AoS, это означает, что мы будем использовать 10,000 / 3 ~= 3300 строки кэша.
Если бы мы использовали хранилище SoA, мы бы загружали два плотно упакованных массива значений currentHealth и healthRegen. Каждая строка кэша будет содержать значения 64 / 4 = 16 компонентов, но нам придется выделить две строки - одну для currentHealth и одну для healthRegen. Более простой способ представить себе это - загрузить два массива по 10 000 чисел с плавающей запятой. Если предположить, что мы можем поместить 64 / 4 = 16 плавающих объектов в строку кэша, это будет означать 10,000 / 16 ~= 625 строк кеша для каждого из наших двух массивов. Чтобы выполнить наш код для всех 10 000 сущностей, нам пришлось бы использовать 625 * 2 = 1250 строк кэша, или около 1/3 строк по сравнению с AoS.
Замечание о заполнении структуры
В приведенном выше примере вы могли предположить, что healthRegen займет 12 + 8 + 1 = 21 байтов пространства, но на самом деле он занимает 24 байта из-за заполнения структуры. На самом деле это дополнительное преимущество хранилища SoA - поскольку каждый из членов хранится в плотно упакованных массивах отдельно, мы не теряем места для заполнения структуры.
Это действительно необходимо?
См. Первый абзац этого сообщения в блоге, но это серьезная проблема. Даст ли это нам такой прирост производительности?
Чтобы ответить на этот вопрос, в конечном итоге все сводится к промахам кеша. Если вы делаете много обращений к памяти (много объектов на экране), данные, удобные для кеширования, становятся все более и более важными. Давайте воспользуемся этим сообщением 2012 года, чтобы увидеть, сможем ли мы приблизительно оценить некоторые цифры в теории.
Intel Xeon 5500 i7 имеет время доступа к кэш-памяти L2 ~ 10 циклов, в то время как доступ к кеш-памяти L3 занимает около 40 циклов - или примерно в 4 раза дольше. Если у нас будет достаточно компонентов (или достаточно больших компонентов), использование структуры хранения массива вместо массива структуры хранения может значительно ускорить некоторые пакетные операции.
Примечание. Не следует понимать, что последний абзац означает, что наши последовательные и случайные обращения сделают наш код в 4 раза быстрее. Это не так из-за того, как DRAM / процессоры обрабатывают кеширование. См. Этот пост SO для лучшего объяснения деталей.
