Как извлечь выгоду из кэша процессора в игровом движке системной сущности?

15

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

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

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

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

Но эти списки дают компоненты случайным образом, а не последовательно.

Итак, как спроектировать ECS, чтобы максимизировать попадание в кеш?

РЕДАКТИРОВАТЬ :

Например, физической системе требуется список объектов для объекта, который имеет компоненты RigidBody и Transform (существует пул для RigidBody и пул для компонентов Transform).

Так что его цикл обновления сущностей будет таким:

for (Entity eid in entitiesList) {
    // Get rigid body component
    RigidBody *rigidBody = entityManager.getComponentFromEntity<RigidBody>(eid);

    // Get transform component
    Transform *transform = entityManager.getComponentFromEntity<Transform>(eid);

    // Do something with rigid body and transform component
}

Проблема заключается в том, что компонент RigidBody объекта entity1 может находиться в индексе 2 его пула, а компонент Tranform объекта entity1 - в индексе 0 его пула (поскольку некоторые объекты могут иметь некоторые компоненты, а не другие, и из-за добавления / удаления объектов / компоненты случайным образом).

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

Разве есть способ предварительной выборки следующих компонентов в цикле?

Johnmph
источник
Можете ли вы показать нам, как вы распределяете каждый компонент?
concept3d
С простым распределителем пула и менеджером дескрипторов для наличия ссылки на компонент для управления перемещением компонентов в пуле (чтобы компоненты были непрерывными в памяти).
Johnmph
Ваш примерный цикл предполагает, что обновления компонентов чередуются для каждой сущности. Во многих случаях возможно массовое обновление компонентов по типу компонента (например, сначала обновите все компоненты жесткого тела, затем обновите все преобразования с законченными данными твердого тела, а затем обновите все данные рендеринга с новыми преобразованиями ...) - это может улучшить кэш использовать для каждого обновления компонента. Я думаю, что этот тип структуры - то, что Ник Уиггилл предлагает ниже.
DMGregory
Это мой пример, который плох, на самом деле это скорее «обновление всех преобразований с помощью готовых данных твердого тела», чем физическая система. Но проблема остается той же: в этих системах (обновление transform с твердым телом, update рендеринг с помощью transform, ...) нам нужно будет иметь более одного типа компонентов одновременно.
Johnmph
Не уверен, что это может быть актуально тоже? gamasutra.com/view/feature/6345/…
DMGregory

Ответы:

13

Статья Мика Уэста полностью объясняет процесс линеаризации данных компонентов сущности. Несколько лет назад он работал в серии Tony Hawk на гораздо менее впечатляющем оборудовании, чем у нас сегодня, чтобы значительно повысить производительность. Он в основном использовал глобальные, предварительно распределенные массивы для каждого отдельного типа данных объекта (позиция, оценка и тому подобное) и ссылается на каждый массив в отдельной фазе своей общесистемной update()функции. Можно предположить, что данные для каждой сущности будут иметь одинаковый индекс массива в каждом из этих глобальных массивов, поэтому, например, если проигрыватель создается первым, он может иметь свои данные [0]в каждом массиве.

Еще более специфичные для оптимизации кэша, слайды Кристер Эрикссон для C и C ++.

Чтобы дать немного больше подробностей, вы должны попытаться использовать смежные блоки памяти (наиболее легко распределяемые как массивы) для каждого типа данных (например, позиции, xy и z), чтобы обеспечить хорошую локальность ссылок, используя каждый такой блок данных в разных update()этапы ради временной локализации, т. е. чтобы гарантировать, что кэш не очищен с помощью аппаратного алгоритма LRU, прежде чем вы повторно используете любые данные, которые вы намерены использовать повторно, в рамках данного update()вызова. Как вы и предполагали, вам не нужно выделять ваши сущности и компоненты как отдельные объекты new, так как данные разных типов в каждом экземпляре сущности будут затем чередоваться, уменьшая локальность ссылок.

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

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

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

инженер
источник
1
Просто примечание для тех, кто может быть std::vectorновичком в C ++: в основном это динамически изменяемый размер массива, и, следовательно, он также является смежным (де-факто в старых версиях C ++ и де-юре в новых версиях C ++). Некоторые реализации std::dequeтакже являются "достаточно смежными" (хотя не Microsoft).
Шон Миддледич
2
@Johnmph Проще говоря: если у вас нет населенного пункта, у вас ничего нет. Если две части данных тесно связаны (например, пространственная и физическая информация), то есть они обрабатываются вместе, то вам, возможно, придется сжать их как один компонент с чередованием. Но имейте в виду, что любая другая логика (скажем, AI), которая использует пространственные данные, может пострадать в результате того, что пространственные данные не будут включены вместе с ней . Так что это зависит от того, что требует наибольшей производительности (возможно, физика в вашем случае). Имеет ли это смысл?
Инженер
1
@Johnmph: да, я полностью согласен с Ником в том, как они хранятся в памяти, если у вас есть сущность с указателями на два компонента, которые находятся далеко в памяти, у вас нет локальности, они должны помещаться в строку кэша.
concept3d
2
@Johnmph: Действительно, статья Мика Уэста предполагает минимальные взаимозависимости. Итак: минимизируйте зависимости; Репликация данных по строкам кэша , где вы не можете свести к минимуму этой зависимости ... например , включают в себя преобразование вместе как RigidBody и визуализации; и чтобы уместить строки кэша, вам может потребоваться максимально уменьшить количество атомов данных ... это может быть достигнуто частично путем перехода от плавающей запятой к фиксированной (4 байта против 2 байтов) на значение десятичной запятой. Но так или иначе, независимо от того, как вы это делаете, ваши данные должны соответствовать ширине строки кэша, как было отмечено concept3d, для максимальной производительности.
Инженер
2
@Johnmph. Нет. Всякий раз, когда вы пишете данные Transform, вы просто записываете их в оба массива. Это не те записи, о которых нужно беспокоиться. Как только вы отправите письмо, это будет так же хорошо, как и сделано. Это чтения , которые будут позже в обновлении, когда вы запустите Physics и Renderer, должны иметь доступ ко всем соответствующим данным, сразу же, в одной строке кэша, близко к персональному процессору. Кроме того, если вам действительно нужно все это вместе, то вы либо делаете дополнительные репликации, либо убедитесь, что физика, преобразование и рендеринг соответствуют одной строке кэша ... 64 байта являются общими и на самом деле довольно много данных! ...
Инженер