Ориентированный на данные доступ к нескольким индексированным массивам данных

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

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

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

weightarray ->   [0,1,2,3]
positionarray -> [0,1,2,3]
velocityarray -> [0,1,2,3]

Этот подход хорошо работает, если все объекты имеют каждый из атрибутов. Однако, если только сущности 0 и 2 имеют все атрибуты дерева, а другие являются сущностями типа, который не перемещается, они не будут иметь скорости, и данные будут выглядеть так:

weightarray ->   [0,1,2,3]
positionarray -> [0,1,2,3]
velocityarray -> [0,2]     //either squash it like this
velocityarray -> [0  ,2  ]     //or leave "empty gaps" to keep alignment

Внезапно это не так легко повторить. Компонент, заинтересованный только в повторении и управлении скоростью, должен был бы либо каким-либо образом пропустить пустые промежутки, если бы я пошел вторым подходом. Первый подход к сокращению массива не будет работать хорошо и в более сложных ситуациях. Скажем, если у меня есть один объект 0 со всеми тремя атрибутами, другой объект 1, имеющий только вес и положение, и объект 2, имеющий только положение и скорость. Наконец, есть одна последняя сущность 3, которая имеет только вес. Сжатые массивы будут выглядеть так:

weightarray ->   [0,1,3]
positionarray -> [0,1,2]
velocityarray -> [0,2]

Другой подход оставил бы пробелы примерно так:

weightarray ->   [0,1, ,3]
positionarray -> [0,1,2, ]
velocityarray -> [0, ,2, ]

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

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

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

Благодарю.

14

Решение

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

Давайте сначала посмотрим на цель. Цель состоит не в том, чтобы поместить все данные в линейные массивы, а просто в средствах достижения цели. Цель состоит в том, чтобы оптимизировать производительность за счет минимизации пропадания кеша. Это все. Если вы используете OOP-объекты, данные ваших сущностей будут окружены данными, которые вам не обязательно нужны. Если ваша архитектура имеет размер строки кэша 64 байта и вам нужны только вес (float), позиция (vec3) и скорость (vec3), вы используете 28 байтов, но остальные 36 байтов будут загружены в любом случае. Еще хуже то, что когда эти 3 значения не расположены рядом в памяти или ваша структура данных перекрывает границу строки кэша, вы загрузите несколько строк кэша только для 28 байтов фактически используемых данных.

Теперь это не так уж плохо, когда вы делаете это несколько раз. Даже если вы сделаете это сто раз, вы вряд ли заметите это. Однако, если вы делаете это тысячи раз каждую секунду, это может стать проблемой. Поэтому введите DOD, где вы оптимизируете использование кэша, обычно путем создания линейных массивов для каждой переменной, в ситуациях, когда существуют линейные шаблоны доступа. В вашем случае массивы для веса, положения, скорости. Когда вы загружаете позицию одного объекта, вы снова загружаете 64 байта данных. Но поскольку ваши данные позиции расположены рядом в массиве, вы не загружаете 1 значение позиции, вы загружаете данные для 5 смежных объектов. Следующая итерация вашего цикла обновления, вероятно, будет нуждаться в следующем значении позиции, которое уже было загружено в кэш и т. Д., Пока только на 6-м объекте не потребуется загружать новые данные из основной памяти.

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

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

Вы можете хранить наиболее доступные данные в непрерывном массиве. Например, позиция часто используется многими различными компонентами, поэтому она является основным кандидатом в непрерывный массив. Вес, с другой стороны, используется только гравитационной составляющей, поэтому здесь могут быть пробелы. Вы оптимизировали для наиболее часто используемых случаев и получите меньшую производительность для данных, которые используются реже. Тем не менее, я не большой поклонник этого решения по ряду причин: оно все еще неэффективно, вы будете загружать слишком много пустых данных, чем меньше отношение # конкретных компонентов / # полных объектов, тем хуже оно становится. Если только одна из восьми сущностей имеет гравитационные компоненты, и эти сущности равномерно распределены по массивам, вы все равно получаете одну ошибку кэша для каждого обновления. Он также предполагает, что все объекты будут иметь позицию (или что-то еще, что является общей переменной), трудно добавлять и удалять объекты, это негибко и просто некрасиво (в любом случае, imho). Это может быть самое простое решение, хотя.

Другой способ решить эту проблему — использовать индексы. Каждый массив для компонента будет упакован, но есть два дополнительных массива: один для получения идентификатора объекта из индекса массива компонентов и второй для получения индекса массива компонента из идентификатора объекта. Скажем, положение разделяют все сущности, а вес и скорость используются только гравитацией. Теперь вы можете перебирать упакованные массивы веса и скорости, и чтобы получить / установить соответствующую позицию, вы можете получить значение gravityIndex -> entityID, перейти к компоненту Position, использовать его entityID -> positionIndex, чтобы получить правильный индекс в Положение массива. Преимущество состоит в том, что ваш доступ к весу и скорости больше не даст вам промахов в кеше, но вы все равно будете получать промахов в позициях, если соотношение между # компонентами гравитации / # компонентами позиции низкое. Вы также получаете 2 дополнительных поиска в массиве, но 16-разрядного индекса без знака int в большинстве случаев будет достаточно, поэтому эти массивы будут хорошо вписываться в кэш, что означает, что в большинстве случаев это может быть не очень дорогой операцией. Тем не менее, профиль профиль профиль, чтобы быть уверенным в этом!

Третий вариант — дублирование данных. Теперь, я уверен, что это не будет стоить усилий в случае вашего компонента Gravity, я думаю, что это более интересно в сложных вычислительных ситуациях, но давайте все равно возьмем это в качестве примера. В этом случае компонент Gravity имеет 3 упакованных массива для веса, скорости и положения. Он также имеет таблицу индексов, аналогичную той, что вы видели во втором варианте. Когда вы запускаете обновление компонента Gravity, вы сначала обновляете массив позиций из исходного массива позиций в компоненте Position, используя таблицу индексов, как в примере 2. Теперь у вас есть 3 упакованных массива, которые вы можете выполнять своими вычислениями линейно с максимальным кешем. использование. Когда вы закончите, скопируйте позицию обратно в исходный компонент Position, используя таблицу индексов. Теперь, это не будет быстрее (на самом деле, вероятно, медленнее), чем второй вариант, если вы используете его для чего-то вроде Gravity, потому что вы только читаете и пишете позицию один раз. Однако предположим, что у вас есть компонент, в котором сущности взаимодействуют друг с другом, причем каждый этап обновления требует нескольких операций чтения и записи, это может быть быстрее. Тем не менее, все зависит от моделей доступа.

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

Так что серебряной пули нет. Вариантов много. Лучшее решение полностью зависит от вашей ситуации, ваших данных и способа обработки этих данных. Возможно, ни один из приведенных мною примеров не подходит вам, может быть, все они таковы. Не каждый компонент должен работать одинаково, некоторые могут использовать систему изменения / сообщения, в то время как другие используют опцию indexes. Помните, что хотя многие рекомендации по производительности DOD хороши, если вам нужна производительность, она полезна только в определенных ситуациях. DOD — это не всегда использование массивов, это не всегда максимальное использование кэша, вы должны делать это только там, где это действительно важно. Профиль профиль профиль. Знай свои данные. Знайте свои шаблоны доступа к данным. Знай свою (кеш) архитектуру. Если вы сделаете все это, решения станут очевидными, когда вы расскажете об этом 🙂

Надеюсь это поможет!

12

Другие решения

Решение на самом деле признает, что существуют пределы того, насколько далеко вы можете оптимизировать.

Решение проблемы разрыва приведет только к следующему:

  • Если операторы (ответвления) обрабатывают данные об исключениях (объектах, в которых отсутствует компонент).
  • Введение дыр означает, что вы можете итерировать списки случайным образом. Сила DoD заключается в том, что все данные плотно упакованы и упорядочены по способу их обработки.

Что вы можете сделать:

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

Наличие следующих упрощенных списков и их атрибутов:

  • жесткое тело (сила, скорость, трансформация)
  • столкновение (ограничивающий прямоугольник, преобразование)
  • рисуем (texture_id, shader_id, transform)
  • rigidbody_to_collision (hardbody_index, collision_index)
  • collision_to_rigidbody (collision_index, hardbody_index)
  • rigidbody_to_drawable (hardbody_index, drawable_index)

так далее…

Для процессов / заданий может потребоваться следующее:

  • RigidbodyApplyForces (…), приложить силы (например, гравитацию) к скоростям
  • RigidbodyIntegrate (…), применять скорости для преобразований.
  • RigidbodyToCollision (…), Копирование твердого тела преобразуется в преобразования столкновений только для объектов, имеющих компонент столкновения. Список «solidbody_to_collision» содержит индексы того, какой идентификатор жесткого тела должен быть скопирован в какой идентификатор столкновения. Это держит список столкновений плотно упакованным.
  • RigidbodyToDrawable (…), Преобразование из жесткого тела в нарисованные преобразования для объектов, имеющих компонент рисования. Список «solidbody_to_drawable» содержит индексы того, какой идентификатор жесткого тела должен быть скопирован в какой идентификатор рисования. Это держит список drawabkl плотно упакованным.
  • CollisionUpdateBoundingBoxes (…), обновить ограничивающие рамки, используя новые преобразования.
  • CollisionRecalculateHashgrid (…), обновите hashgrid, используя ограничивающие рамки. Вы можете выполнить это в нескольких кадрах, чтобы распределить нагрузку.
  • CollisionBroadphaseResolve (…), рассчитать возможные коллизии, используя hashgrid и т.д ….
  • CollisionMidphaseResolve (…), рассчитать столкновения, используя ограничивающие рамки для широкофазных и т. д ….
  • CollisionNarrowphaseResolve (…), рассчитать столкновение, используя полигоны из средней фазы и т.д ….
  • CollisionToRigidbody (…), добавьте реактивные силы сталкивающихся объектов к силам твердого тела. Список «collision_to_rigidbody» содержит индексы, с какого идентификатора столкновения сила должна быть добавлена ​​к какому идентификатору жесткого тела. Вы также можете создать еще один список под названием «active_forces_to_be_added ». Вы можете использовать это, чтобы отложить добавление сил.
  • RenderDrawable (…), рендеринг рисованных объектов на экран (рендер просто упрощен).

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

Когда создается объект, данные компонента также будут создаваться вместе и сохраняться в том же порядке. То есть списки останутся в основном в том же порядке.

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

5

Я полагаюсь на две структуры для этой проблемы. Надеемся, что диаграммы достаточно ясны (в противном случае я могу добавить дальнейшие объяснения):

введите описание изображения здесь

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

Вы можете использовать блок меньшего размера, чем 512, так как он может быть довольно большим для определенного типа компонента. Что-то вроде 32 может быть разумным, или вы можете настроить размер блока на лету на основе sizeof(ComponentType), При этом вы можете просто связать свои компоненты параллельно с вашими сущностями, не увеличивая объем используемой памяти из незанятых пространств, хотя я не использую это таким образом (я использую вертикальный тип представления, но моя система имеет много типов компонентов — — если у вас есть только несколько, вы можете просто хранить все параллельно).

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

введите описание изображения здесь

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

В качестве бонуса, он также позволяет вам установить пересечения в лучшем случае Log(N)/Log(64) (например: возможность найти пересечение наборов между двумя плотными наборами индексов, содержащих миллион элементов каждый за 3-4 итерации), если вам когда-либо понадобятся быстрые пересечения наборов, которые часто могут быть довольно удобными для ECS.

Эти две структуры являются основой моего двигателя ECS. Они довольно быстрые, поскольку я могу обработать 2 миллиона сущностей частиц (получая доступ к двум различным компонентам) без кэширования запроса для сущностей с обоими компонентами со скоростью чуть менее 30 FPS. Конечно, это дурацкая частота кадров только для 2 миллионов частиц, но это при представлении их как целых объектов с двумя компонентами, прикрепленными каждый (движение и спрайт) к системе частиц, выполняющей запрос в каждом отдельном кадре, без кэширования — что люди обычно никогда не будут делать (лучше использовать как ParticleEmitter компонент, который представляет множество частиц для данного объекта, а не превращает частицу в отдельный объект).

Надеемся, что диаграммы достаточно ясны, чтобы реализовать собственную версию, если вам интересно.

4

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

В игровом движке есть список менеджеров, отвечающих за различные системы в игре (InputManager, PhysicsManager, RenderManager и т. Д.).

Большинство вещей в трехмерном мире представлены классом Object, и каждый объект может иметь любое количество компонентов. Каждый компонент отвечает за различные аспекты поведения объекта (RenderComponent, PhysicsComponent и т. Д.).

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

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

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

Что касается структуры данных, вы можете использовать систему, о которой я говорил выше, и структурировать ее несколькими способами. Обычно объекты хранятся либо в векторе, либо на карте, а компоненты — в векторе или списке объекта. Что касается информации о физике, PhysicsManager имеет список всех физических объектов, которые могут быть сохранены в массиве / векторе, а у PhysicsComponent есть копия его положения, скорости и других данных, чтобы он мог делать все, что угодно. эти данные должны обрабатываться менеджером по физике. Например, если вы хотите изменить скорость объекта, вы просто скажете PhysicsComponent, он изменит его значение скорости и затем уведомит PhysicsManager.

Я более подробно расскажу о предмете структуры движка объекта / компонента здесь: https://gamedev.stackexchange.com/a/23578/12611

3