[Из песочницы] Data Oriented Design на практике03.02.2017 15:48

Размер структуры S равен 24 байтам. Мой процессор (Intel Core i7) имеет 32KB кэш на ядро с 64B кэш-линией (cache line). Это значит, что при запросе данных из памяти в одну кэш-линию полностью поместятся только две структуры S. В первом тесте я читаю только одно int поле, т.е. при одном обращении к памяти в одной кэш-линии будет только 2 (иногда 3) нужных нам поля. Во втором тесте я читаю такое же int значение, но из вектора. std::vector гарантирует последовательность данных. Это означает, что при обращении к памяти в одной кэш-линии будет 16 (64KB / sizeof(int) = 16) нужных нам значений. Получается, что во втором тесте мы обращаемся к памяти реже. A обращение к памяти, как известно, является слабым звеном в современных процессорах.

Как дела обстоят на практике?

Чтобы понять реальность применения подхода я решил написать более-менее комплексный код, используя обе техники и сравнить результаты. Пускай это будет 2d симуляция твердых тел — мы создадим N выпуклых многоугольников, зададим параметры — массу, скорость и т.п. и посмотрим, сколько объектов мы сможем симулировать оставаясь на отметке 30 fps.

1. Array of Structures

1.1. Первая версия программы

Для простоты программа написана для Windows и использует DirectX11 для отрисовки. Цель этой статьи — сравнение производительности на процессоре, поэтому графику мы обсуждать не будем. Класс Shape, который представляет физическое тело, выглядит так:

class Shape
{
public:
	Shape(uint32_t const numVertices, float radius, math::Vec2 const pos, math::Vec2 const vel, float m, math::Color const col);

	static Shape createWall(float const w, float const h, math::Vec2 const pos);

public:
	math::Vec2 position{ 0.0f, 0.0f };
	math::Vec2 velocity{ 0.0f, 0.0f };
	math::Vec2 overlapResolveAccumulator{ 0.0f, 0.0f };
	float massInverse;
	math::Color color;
	std::vector vertices;
	math::Bounds bounds;
};

• Назначение position и velocity, думаю, очевидно. vertices — вершины фигуры заданные рандомно.
• bounds — это ограничивающий прямоугольник, который полностью содержит фигуру — используется для предварительной проверки пересечений.
• massInverse — единица, разделенная на массу — мы будем использовать только это значение, поэтому будем хранить его, вместо массы.
• color — цвет — используется только при рендеринге, но хранится в экземпляре фигуры, задается рандомно.
• overlapResolveAccumulator см. пояснение ниже.

Сердце нашей программы — это метод ShapesApp::update(). Вот его упрощенный вариант:

void ShapesApp::update(float const dt)
{
	float const dtStep{ dt / NUM_PHYSICS_STEPS };
	for (uint32_t s{ 0 }; s < NUM_PHYSICS_STEPS; ++s)
	{
		updatePositions(dtStep);

		for (size_t i{ 0 }; i < _shapes.size() - 1; ++i)
		{
			for (size_t j{ i + 1 }; j < _shapes.size(); ++j)
			{
				CollisionSolver::solveCollision(_shapes[i].get(), _shapes[j].get());
			}
		}
	}
}

На моем стареньком ноутбуке эта программа рассчитывает 500 фигур максимум, перед тем, как fps начинает падать ниже 30. Фуууу, всего 500???! Согласен, немного, но не забывайте, что каждый кадр мы повторяем расчеты 20 раз.

Думаю, что стоит разбавить статью скриншотами, поэтому вот:

1.2. Оптимизация номер 1. Spatial Grid

Коммит второй версии программы можно посмотреть здесь. Появился новый класс Grid и немного изменился метод ShapesApp::update() — теперь он вызывает методы сетки для проверки пересечений.

Эта версия держит уже 8000 фигур при 30 fps (не забываем про 20 итераций в каждом кадре)! Пришлось уменьшить фигуры в 10 раз, чтобы они поместились в окне.

1.3. Оптимизация номер 2. Multithreading.

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

Запустив эту версию я могу наблюдать 13000 фигур при 30 fps. Для такого количества объектов пришлось увеличить окно! И снова — в каждом кадре мы повторяем симуляцию 20 раз.

2. Structure of Arrays

2.1. Первая версия программы

struct ShapesData
{
	std::vector positions;
	std::vector velocities;
	std::vector overlapAccumulators;
	std::vector massesInverses;
	std::vector colors;
	std::vector> vertices;
	std::vector bounds;
};

solveCollision(struct ShapesData & data, std::size_t const indA, std::size_t const indB);

Эта версия программы выдает 500 фигур при 30 fps, т.е. не отличается от самой первой версии. Связано это с тем, что измерения проводятся на малом количестве данных и к тому же самый тяжелый метод использует почти все поля структуры.

Далее без картинок, т.к. они точно такие же, как были ранее.

2.2. Оптимизация номер 1. Spatial Grid

2.3. Оптимизация номер 2. Multithreading

3. Заключение

Поэтому однозначно ответить — стоит ли переходить на новую парадигму всем и каждому — невозможно. Когда я работал в геймдеве над игровым движком, 10% прироста производительности — внушительная цифра. Когда я писал пользовательские утилиты типа лаунчера, то применение DOD подхода вызвало бы только недоумение коллег. В общем, профилируйте, измеряйте и делайте выводы сами :).