Data-Oriented Design на практиці

останнім часом все частіше можна зустріти обговорення цікавої, але не дуже популярною парадигми — так званої Data-Oriented Design (DOD). Якщо ви влаштовуєтеся на роботу, пов'язану з високопродуктивними обчисленнями, будьте готові до відповідних питань. Але я був дуже здивований, дізнавшись, що деякі мої колеги не чули про цьому підході і після недовго обговорення поставилися до неї скептично. У цій статті я постараюся порівняти традиційний OOP підхід з DOD.

Що таке DOD?
Дана стаття була задумана як спроба порівняти різні підходи без спроби пояснити їх суть. На Хабре є кілька статей по темі, наприклад . Варто також подивитися відео з конференції CppCon. Але в двох словах, DOD — це спосіб оперувати даними в cache friendly манері. Звучить незрозуміло, приклад пояснить краще.

Приклад
#include <chrono>
#include < iostream>
#include < vector>

using namespace std;
using namespace std::chrono;

struct S
{
uint64_t u;
double d;
int i;
float f;
};

struct Data
{
vector<uint64_t> vu;
vector<double> vd;
vector<int> vi;
vector<float> vf;
};

int test1(const S & s1, const S & s2)
{
return s1.i + s2.i;
}

int test2(Data const & data, size_t const ind1, size_t const ind2)
{
return data.vi[ind1] + data.vi[ind2];
}

int main()
{
size_t const N{ 30000 };
size_t const R{ 10 };

vector<S> v(N);
Data data;
data.vu.resize(N);
data.vd.resize(N);
data.vi.resize(N);
data.vf.resize(N);

int result{ 0 };

cout << "test #1" << endl;
for (uint32_t i{ 0 }; i < R; i++)
{
auto const start{ high_resolution_clock::now() };
for (size_t a{ 0 }; a < v.size() - 1; ++a)
{
for (size_t b{ a + 1 }; b < v.size(); ++b)
{
result += test1(v[a], v[b]);
}
}
cout << duration<float>{ high_resolution_clock::now() - start }.count() << endl;
}

cout << "test #2" << endl;
for (uint32_t i{ 0 }; i < R; i++)
{
auto const start{ high_resolution_clock::now() };
for (size_t a{ 0 }; a < v.size() - 1; ++a)
{
for (size_t b{ a + 1 }; b < v.size(); ++b)
{
result += test2(data, a, b);
}
}
cout << duration<float>{ high_resolution_clock::now() - start }.count() << endl;
}

return result;
}


Другий тест виконується швидше на 30% (в VS2017 і gcc7.0.1). Але чому?

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

Як справи йдуть на практиці?
Наведений вище приклад наочно показує переваги використання SoA (Struct of Arrays) замість AoS (Array of Structs), але цей приклад з розряду
Hello World
, тобто далекий від реального життя. У реальному коді багато залежностей і специфічних даних, які, можливо не дадуть приросту продуктивності. До того ж, якщо в тестах ми будемо звертатися до всіх полів структури, різниці в продуктивності не буде.

Щоб зрозуміти реальність застосування підходу я вирішив написати більш-менш комплексний код, використовуючи обидві техніки і порівняти результати. Нехай це буде 2d симуляція твердих тіл — ми створимо N опуклих багатокутників, задамо параметри — масу, швидкість і т. п. і подивимося, скільки об'єктів ми зможемо симулювати залишаючись на позначці 30 fps.

1. Array of Structures
1.1. Перша версія програми
Вихідний код для першої версії програми можна взяти з цього коміта. Зараз ми коротко пробіжимося по коду.

Для простоти програма написана для Windows і використовує DirectX11 для відтворення. Мета цієї статті — порівняння продуктивності на процесорі, тому графіком ми обговорювати не будемо. Клас
Shape
, який являє фізичне тіло, виглядає так:

Shape.h
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(const float w, const float h, math::Vec2 const pos);

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


  • Призначення
    position
    та
    velocity
    , думаю, очевидно.
    vertices
    — вершини фігури задані рандомно.
  • bounds
    — це обмежує прямокутник, який повністю містить фігуру — використовується для попередньої перевірки перетинів.
  • massInverse
    — одиниця, поділена на масу — ми будемо використовувати це значення, тому будемо зберігати його, замість маси.
  • color
    — колір — використовується тільки при рендерінгу, але зберігається в примірнику фігури, задається рандомно.
  • overlapResolveAccumulator
    див. пояснення нижче.
image
Коли трикутник перетинається з фігурою a, ми повинні посунути його трохи, щоб виключити накладення фігур один на одного. Також ми повинні перерахувати
bounds
. Але після переміщення трикутник перетинає іншу фігуру — b, і ми знову повинні перемістити його і знову перерахувати
bounds
. Зауважте, що після другого переміщення трикутник знову опиниться над фігурою a. Щоб уникнути повторних обчислень ми будемо зберігати величину, на яку треба перемістити трикутник у спеціальному акумуляторі —
overlapResolveAccumulator
— і пізніше будемо переміщати фігуру на це значення, але тільки один раз.

Серце нашої програми — це метод
ShapesApp::update()
. Ось його спрощений варіант:

ShapesApp.cpp
void ShapesApp::update(const float dt)
{
const float 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());
}
}
}
}


Кожен кадр ми викликаємо
ShapesApp::updatePositions()
метод, який змінює положення кожної фігури і розраховує новий
Shape::bounds
. Потім ми перевіряємо кожну фігуру з кожної іншої на перетин —
CollisionSolver::solveCollision()
. Я використовував Separating Axis Theorem (SAT). Всі ці перевірки ми робимо
NUM_PHYSICS_STEPS
разів. Ця змінна служить декільком цілям — по-перше, фізика виходить більш стабільна, по-друге, вона обмежує кількість об'єктів на екрані. с++ швидкий, дуже швидкий, і без цієї змінної у нас будуть десятки тисяч фігур, що сповільнить зарисовку. Я використовував
NUM_PHYSICS_STEPS = 20


На моєму старенькому ноутбуці ця програма розраховує 500 фігур максимум, перед тим, як fps починає падати нижче 30. Фуууу, всього 500???! Згоден, трохи, але не забувайте, що кожен кадр ми повторюємо розрахунки 20 разів.

Думаю, що варто розбавити статтю скріншотами, тому ось:

image

1.2. Оптимізація номер 1. Spatial Grid
Я згадував, що хочу провести тести на як можна більш наближеною до реальності програмі. Те, що ми написали вище в реальності не використовується — перевіряти кожну фігуру з кожної дуууже повільно. Для прискорення розрахунків зазвичай використовується спеціальна структура. Пропоную використовувати звичайну 2d сітку — я назвав її
Grid
— яка складається з M комірок —
Cell
. На початку розрахунків ми будемо записувати в кожну клітинку об'єкти, які знаходяться в ній. Тоді нам потрібно буде всього лише пробігтися по всіх комірках і перевірити перетину декількох пар об'єктів. Я неодноразово використовував цей підхід в релізах і він зарекомендував себе пишеться дуже швидко, легко відладжується, простий в розумінні.

Комміт другій версії програми можна подивитися здесь. З'явився новий клас
Grid
і трохи змінився метод
ShapesApp::update()
— тепер він викликає методи сітки для перевірки перетинів.

Ця версія тримає вже 8000 фігур при 30 fps (не забуваємо про 20 ітерацій в кожному кадрі)! Довелося зменшити фігури в 10 разів, щоб вони помістилися в вікні.

image

1.3. Оптимізація номер 2. Multithreading.
Сьогодні, коли навіть на телефонах встановлюються процесори з чотирма ядрами, ігнорувати багатопоточність просто нерозумно. В цій, останній, оптимізації ми додамо пул потоків і розділимо основні завдання на рівні таски. Так, наприклад, метод
ShapesApp::updatePositions
, який раніше пробігав по всім фігурам, встановлюючи нову позицію і перераховуючи
bounds
, тепер пробігає лише частини фігур, зменшуючи тим самим навантаження на одне ядро. Клас пулу був чесно скопипастен звідси. У тестах я використовую чотири потоки (враховуючи основний). Готову версію можна знайти на здесь.

Поділ основних завдань додало трохи головного болю. Так наприклад, якщо фігура перетинає кордон комірки в сітці, то вона буде знаходиться одночасно в декількох осередках:

image
Тут фігура a знаходиться в одній клітинці, тоді як b відразу в чотирьох. Тому доступ до цих клітинок необхідно синхронізувати. Також потрібно синхронізувати доступ до деяких полів класу
Shape
. Для цього ми додали
std::mutex
на
Shape
та
Cell
.

Запустивши цю версію я можу спостерігати 13000 фігур при 30 fps. Для такої кількості об'єктів довелося збільшити вікно! І знову — в кожному кадрі ми повторюємо симуляцію 20 разів.

image

2. Structure of Arrays
2.1. Перша версія програми
Те, що ми писали вище я називаю традиційним підходом — я пишу такий код багато років і читаю, в основному, схожий код. Але тепер ми вб'ємо структуру
Shape
і подивимося, чи зможе ця невелика модифікація вплинути на продуктивність. До загальної радості рефакторинг виявився складним, навіть тривіальним. Замість
Shape
ми будемо використовувати структуру з векторами:

Shape.h
struct ShapesData
{
std::vector<math::Vec2> positions;
std::vector<math::Vec2> velocities;
std::vector<math::Vec2> overlapAccumulators;
std::vector<float> massesInverses;
std::vector<math::Color> colors;
std::vector<std::vector<math::Vec2>> vertices;
std::vector<math::Bounds> bounds;
};


І ми передаємо цю структуру так:

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

Тобто замість конкретних фігур передаються їх індекси і в методі з потрібних векторів беруться потрібні дані.

Ця версія програми видає 500 фігур при 30 fps, тобто не відрізняється від самої першої версії. Пов'язано це з тим, що вимірювання проводяться на малій кількості даних і до того ж найважчий метод використовує майже всі поля структури.

Далі без зображеннь, т. к. вони точно такі ж, як були раніше.

2.2. Оптимізація номер 1. Spatial Grid
Все як і раніше, міняємо тільки AoS SoA. Код здесь. Результат краще, ніж був раніше — 9500 фігур (було 8000), тобто різниця в продуктивності близько 15%.

2.3. Оптимізація номер 2. Multithreading
Знову беремо старий код, міняємо структури і отримуємо 15000 фігур при 30 fps. Тобто приріст продуктивності близько 15%. Вихідний код фінальної версії лежить здесь.

3. Висновок
Спочатку код писався для себе з метою перевірити різні підходи, їх продуктивність і зручність. Як показали результати, невелика зміна в коді може дати досить відчутний приріст. А може і не дати, може бути навіть навпаки — продуктивність буде гірше. Так наприклад, якщо нам потрібна лише один примірник, то використовуючи стандартний підхід ми прочитаємо його з пам'яті тільки один раз і будемо мати доступ до всіх полів. Використовуючи ж структуру векторів, ми змушені будемо запитувати кожне поле індивідуально, маючи cache miss при кожному запиті. Плюс до всього трохи погіршується читабельність і ускладнюється код.

Тому однозначно відповісти, чи варто переходити на нову парадигму всім і кожному — неможливо. Коли я працював в геймдеве над ігровим движком, 10% приросту продуктивності — значна цифра. Коли я писав користувацькі утиліти типу лаунчер, то застосування DOD підходу викликало б тільки подив колег. Загалом, профилируйте, вимірюйте і робіть висновки самі :).
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.