Кэш-дружественный доступ к памяти в тесных циклах физики и столкновений

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

Функциональность, которую я хочу:

  • Есть класс, который представляет PhysicsBody
  • Есть класс, который представляет объем столкновения (скажем, поле)
  • Каждое физическое тело может иметь еще один объем столкновений
  • Возможно иметь физическое тело без объема столкновения
  • Необязательно: CollisionVolume без физического тела. (подумайте о том, как запустить)

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

Я знаю, что идеальный способ — хранить объекты в смежных массивах.

std::vector<PhysicsBody> m_bodies;
std::vector<CollisionVolume> m_colliders;

Проблемы, которые я нашел с этим подходом:

  • Трудно поддерживать отношения PhysicsBody -> CollisionVolume. Например, если я хочу удалить CollisionVolume из моего вектора, я поменяю его на последний и вернусь обратно. Данные перемещаются, и если я сохраняю индекс в CollisionVolume в PhysicsBody, он больше не действителен.
  • Каждый раз, когда я уничтожаю PhysicsBody, деструктор проверит, не был ли к нему прикреплен какой-либо том столкновения, и соответствующим образом удалит его из системы Physics. Проблема состоит в том, что вектор будет делать внутренние копии и уничтожать их, и когда это произойдет, он нанесет ущерб, удалив тома столкновений, которые не должны были быть удалены.
  • CollisionVolume на самом деле является базовым классом (необязательно), и другие классы являются производными от него, как коробки / сферы, а что нет. Я мог бы потенциально не использовать наследование и придумать какой-то другой сложный дизайн, но об этом нужно помнить.

Я изо всех сил пытался найти способ обойти это, но вместо этого получал указатели:

std::vector<PhysicsBody*> m_bodies;
std::vector<CollisionVolume*> m_colliders;

Лучшее решение для минимизации ошибок кэша, которое я придумал, — это перегрузка new / delete и сохранение этих объектов в пуле памяти только для физической системы.

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

6

Решение

Фундаментальный вопрос: в отсутствие потоков, работающих и изменяющих данные из разных ядер (ЦП), где вы видите необходимость заботиться о стоимости когерентности кэша?

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

Похоже, вы на самом деле имели ввиду кеш-локальность? Это правильно?

С единством Vs. местность из пути, вот мое взятие:

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

Знаете ли вы количество элементов заранее? Если да, вы можете сделать это.

vector<T> myVec;
myVec.reserve(NUM_ELEMS);

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

myvec[i] = ...

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

2

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

Я хотел бы указать на существенную разницу в модели данных, планируете ли вы использовать векторный движок (GPU) для вычислений или нет. Типичное расположение данных следует за ООП и называется Array-of-Structures. Для использования векторного механизма какого-либо вида, данные должны быть реорганизованы в структуру массивов. Больше по теме от Intel

https://software.intel.com/en-us/articles/creating-a-particle-system-with-streaming-simd-extensions

0

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

Здесь, если вы хотите пройти полный путь создания своего собственного контейнера, действительно полезно, если вы все еще хотите вызывать деструкторы для этих удаленных объектов, чтобы понять, как реализованы контейнеры STL с использованием ‘размещения новых’ и ручного вызова деструктора для Избегайте таких вещей, как оператор присваивания для типа T.

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

union PhysicsNode
{
PhysicsBody body;
PhysicsNode* next_free;
};
PhysicsNode* free_physics_nodes;

То же самое касается узла столкновения. В этом случае вы рассматриваете этот PhysicsNode, как будто он PhysicsBody, когда он «занят», и как односвязный узел списка, когда он «свободен» или «свободен» для восстановления.

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

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

0