Насколько эффективны системы кеша сущностей?

В последнее время я много читал о системах сущностей, чтобы реализовать их в своем игровом движке C ++ / OpenGL. Два ключевых преимущества, которые я постоянно слышу, хвалят о системах сущностей:

1. простое конструирование новых типов объектов, благодаря тому, что им не приходится путать сложные иерархии наследования, и
2. эффективность кеша, которую я с трудом понимаю.

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

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

Вы можете иметь компоненты, хранящие указатели на другие компоненты, или указатели на сущности, которые хранят указатели на компоненты. Однако, как только вы добавляете указатели в микс, вы уже убиваете эффективность кеша. Вы можете убедиться, что каждый массив компонентов имеет «n» большой размер, где «n» - это количество сущностей, живущих в системе, но этот подход ужасно бесполезен: это очень затрудняет добавление новых типов компонентов в движок, но все же отбрасывает эффективность кэша, потому что вы переходите с одного массива на другой. Вы можете чередовать свой массив объектов, вместо того чтобы хранить отдельные массивы, но вы все равно тратите впустую память; добавление новых компонентов или систем обходится слишком дорого, но теперь с дополнительным преимуществом - аннулирование всех ваших старых уровней и сохранение файлов.

Все это при условии, что объекты обрабатываются линейно в списке, каждом кадре или тике. На самом деле это не часто так. Скажем, вы используете рендерер секторов / порталов или октри для выполнения отбора окклюзии. Возможно, вы сможете хранить объекты непрерывно внутри сектора / узла, но вы будете прыгать вокруг, нравится вам это или нет. Тогда у вас есть другие системы, которые могут предпочесть сущности, хранящиеся в каком-то другом порядке. ИИ может быть хорошо с хранением сущностей в большом списке, пока вы не начнете работать с AI LOD; затем вы захотите разделить этот список в зависимости от расстояния до игрока или какой-либо другой метрики LOD. Физика захочет использовать это октри. Скриптам все равно, им нужно бежать, несмотря ни на что.

Я мог видеть разделение компонентов между «логикой» (например, ai, скриптами и т. Д.) И «миром» (например, рендеринг, физика, аудио и т. Д.) И управлением каждым списком по отдельности, но эти списки по-прежнему должны взаимодействовать друг с другом. ИИ бессмыслен, если он не может повлиять на состояние трансформации или анимации, используемое для рендеринга объекта.

Как системы сущностей "эффективно кешируют" в реальном игровом движке? Возможно, есть гибридный подход, который все используют, но не обсуждают, как хранение сущностей в массиве глобально и ссылки на него внутри октодерева?

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

Обратите внимание, что (1) является преимуществом проектирования на основе компонентов , а не только ES / ECS. Вы можете использовать компоненты разными способами, в которых отсутствует «системная» часть, и они работают просто отлично (и во многих инди-играх и играх AAA такие архитектуры используются).

Стандартная объектная модель Unity (с использованием GameObjectи MonoBehaviourобъектов) - это не ECS, а проектирование на основе компонентов. Новая функция Unity ECS, конечно же, является реальной ECS.

Системы должны иметь возможность работать с более чем одним компонентом, т. Е. Как система рендеринга, так и физическая система должны иметь доступ к компоненту преобразования.

Некоторые ECS сортируют свои контейнеры компонентов по идентификатору объекта, что означает, что соответствующие компоненты в каждой группе будут в том же порядке.

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

Это похоже на то, как рекомендуется использовать структуру массивов (SOA) для HPC. Процессор и кэш могут работать с несколькими линейными массивами почти так же хорошо, как с одним линейным массивом, и гораздо лучше, чем с произвольным доступом к памяти.

Другая стратегия, используемая в некоторых реализациях ECS, включая Unity ECS, заключается в выделении Компонентов на основе Архетипа их соответствующей сущности. То есть, все Сущности с точно набором компонентов ( PhysicsBody, Transform) будут выделены отдельно от лиц с различными компонентами (например PhysicsBody, Transform, и Renderable ).

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

Вы можете иметь компоненты, хранящие указатели на другие компоненты, или указатели на сущности, которые хранят указатели на компоненты.

Компоненты, ссылающиеся на другие компоненты одной и той же сущности, не должны ничего хранить. Чтобы ссылаться на компоненты в других объектах, просто сохраните идентификатор объекта.

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

Вы можете убедиться, что каждый массив компонентов имеет «n» большой размер, где «n» - это количество сущностей, живущих в системе.

Используйте дескрипторы (например, индексы + маркеры генерации), а не указатели, и тогда вы сможете изменять размеры массивов, не опасаясь разрыва ссылок на объекты.

Вы также можете использовать подход «чанкованный массив» (массив массивов), аналогичный многим распространенным std::dequeреализациям (хотя и без жалко маленького размера чанка в указанных реализациях), если вы хотите по какой-то причине разрешить указатели или если у вас возникли проблемы с изменение размера массива

Во-вторых, все это предполагает, что объекты обрабатываются линейно в списке каждый кадр / тик, но в действительности это не часто так

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

Некоторые из ваших компонентов будут легко обрабатываться линейно. Даже в обычно «тяжелых» случаях использования мы определенно наблюдали увеличение производительности при использовании плотно упакованных массивов (в основном в случаях, где используется не более нескольких сотен N, как в случае с агентами ИИ в типичной игре).

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

Скажем, вы используете рендерер секторов / порталов или октри для выполнения отбора окклюзии. Возможно, вы сможете хранить объекты непрерывно внутри сектора / узла, но вы будете прыгать вокруг, нравится вам это или нет.

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

Есть также древовидные структуры, которые построены так, чтобы жить в плотно упакованных массивах. Например, с вашим октодвижением вы можете использовать структуру, подобную куче (родители перед детьми, братья и сестры рядом друг с другом), и гарантировать, что даже когда вы «сверляете» дерево, вы всегда выполняете итерацию вперед в массиве, что помогает ЦП оптимизирует доступ к памяти / поиск в кэше.

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

Тогда у вас есть другие системы, которые могут предпочесть сущности, хранящиеся в каком-то другом порядке.

Вы можете хранить их несколько раз. Как только вы уменьшите массивы до минимума, вы можете обнаружить, что действительно экономите память (так как вы удалили свои 64-битные указатели и можете использовать меньшие индексы) с этим подходом.

Вы можете чередовать свой массив объектов вместо хранения отдельных массивов, но вы все еще тратите память

Это противоречит хорошему использованию кэша. Если все, что вас волнует, - это преобразования и графические данные, зачем машине тратить время на сбор всех этих других данных для физики и ИИ, а также ввода и отладки и так далее?

Это точка зрения, которая обычно делается в пользу ECS против монолитных игровых объектов (хотя в действительности это не применимо при сравнении с другими компонентными архитектурами).

Что бы это ни стоило, большинство реализаций ECS «промышленного уровня», о которых я знаю, используют чередованное хранилище. Популярный подход Archetype, о котором я упоминал ранее (используемый в Unity ECS, например), очень явно создан для использования чередующегося хранилища для компонентов, связанных с Archetype.

ИИ бессмыслен, если он не может повлиять на состояние трансформации или анимации, используемое для рендеринга объекта.

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

Вы также забываете кеш кода . Когда вы используете системный подход ECS (в отличие от некоторой более наивной архитектуры компонентов), вы гарантируете, что выполняете один и тот же небольшой цикл кода и не перепрыгиваете через таблицы виртуальных функций к множеству случайных Updateфункций, разбросанных по всему ваш двоичный файл Таким образом, в случае с AI вы действительно хотите хранить все свои различные компоненты AI (потому что, конечно, у вас есть более одного, чтобы вы могли составлять поведения!) В отдельных корзинах и обрабатывать каждый список отдельно, чтобы получить наилучшее использование кэша кода.

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

Используя подход, при котором каждая система знает, какие очереди событий считывать для фрейма, вы даже можете сделать чтение событий быстрым. Или быстрее, чем без, по крайней мере.

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

По-прежнему ведутся активные исследования по улучшению работы многих игровых систем с архитектурой ECS и шаблонами проектирования, ориентированными на данные. Подобно некоторым удивительным вещам, которые мы видели в SIMD в последние годы (например, парсеры JSON), мы видим, что все больше и больше вещей делают с архитектурой ECS, которая не кажется интуитивно понятной для классических игровых архитектур, но предлагает ряд преимущества (скорость, многопоточность, тестируемость и т. д.).

Или, возможно, есть гибридный подход, который все используют, но никто не говорит о

Это то, что я защищал в прошлом, особенно для людей, которые скептически относятся к архитектуре ECS: используйте хорошие ориентированные на данные подходы к компонентам, где производительность критична. Используйте более простую архитектуру, где простота сокращает время разработки. Не подсовывайте каждый отдельный компонент строгому определению компонентов, как предлагает ECS. Разрабатывайте свою компонентную архитектуру таким образом, чтобы вы могли легко использовать подходы, подобные ECS, где они имеют смысл, и использовать более простую структуру компонентов, где подход, подобный ECS, не имеет смысла (или имеет меньший смысл, чем древовидная структура и т. Д.) ,

Я лично относительно недавно обратился к истинной силе ECS. Хотя для меня решающим фактором было то, что редко упоминалось в ECS: это делает написание тестов для игровых систем и логики почти тривиальными по сравнению с тесно связанными логически-нагруженными компонентами, с которыми я работал в прошлом. Поскольку архитектуры ECS помещают всю логику в системы, которые просто потребляют компоненты и производят обновления компонентов, создание «фиктивного» набора компонентов для тестирования поведения системы довольно просто; поскольку большая часть игровой логики должна жить исключительно внутри систем, это фактически означает, что тестирование всех ваших систем обеспечит достаточно высокий охват кода вашей игровой логики. Системы могут использовать фиктивные зависимости (например, интерфейсы графического процессора) для испытаний с гораздо меньшей сложностью или влиянием на производительность, чем вы

Кроме того, вы можете заметить, что многие люди говорят о ECS, даже не понимая, что это такое. Я вижу классический Unity, называемый ECS с удручающей частотой, иллюстрирующий, что слишком многие разработчики игр отождествляют «ECS» с «Components» и практически полностью игнорируют часть «Entity System». Вы видите много любви к ECS в Интернете, когда большая часть людей действительно просто выступает за компонентный дизайн, а не за реальный ECS. На этом этапе спорить почти бессмысленно; ECS был искажен из своего первоначального значения в общий термин, и вы могли бы также принять, что «ECS» не означает то же самое, что «ориентированный на данные ECS». : /