Data Oriented Design на практиці
Останнім часом все частіше можна зустріти обговорення цікавої, але не дуже популярної парадигми - так званої Data Oriented Design (DOD ). Якщо ви влаштовуєтеся на роботу, пов'язану з високопродуктивними обчисленнями, будьте готові до відповідних питань. Але я був дуже здивований, дізнавшись, що деякі мої колеги не чули про цей підхід і після недовго обговорення поставилися до нього скептично. У цій статті я постараюся порівняти традиційнийOOPпідхід зDOD.
Що таке DOD?
Другий тест виконується швидше на 30% (у VS2017 та gcc7.0.1). Але чому?
Розмір структури S дорівнює 24 байтам. Мій процесор (Intel Core i7) має 32KB кеш на ядро з 64B кеш-лінією (cache line). Це означає, що з запиті даних із пам'яті в одну кеш-лінію повністю помістяться лише дві структури S . У першому тесті читаю лише одне int поле, тобто. при одному зверненні до пам'яті в одній кеш-лінії буде лише 2 (іноді 3) потрібні нам поля. У другому тесті я читаю таке саме int значення, але з вектора. std::vector гарантує послідовність даних. Це означає, що при зверненні до пам'яті в одній кеш-лінії буде 16 потрібних нам значень. Виходить, що у другому тесті ми звертаємося до пам'яті рідше. А звернення до пам'яті, як відомо, є слабкою ланкою у сучасних процесорах.
Як справи на практиці?
Приклад вище наочно показує переваги використанняSoA(Struct of Arrays) замістьAoS(Array of Structs), але це приклад з розряду Hello World , тобто. далекий від реального життя. У реальному коді багато залежностей та специфічних даних, які, можливо, не дадуть приросту продуктивності. До того ж, якщо в тестах ми звертатимемося до всіх полів структури,різниці у продуктивності не буде.
Щоб зрозуміти реальність застосування підходу, я вирішив написати більш-менш комплексний код, використовуючи обидві техніки та порівняти результати. Нехай це буде 2d симуляція твердих тіл - ми створимо N опуклих багатокутників, поставимо параметри - масу, швидкість і т.п. і подивимося, скільки об'єктів ми зможемо симулювати, залишаючись на позначці 30 fps.
1. Array of Structures
1.1. Перша версія програми
Вихідний код для першої версії програми можна взяти із цього комміту. Зараз ми коротко пробіжимося за кодом.
Для простоти програма написана дляWindowsі використовуєDirectX11для малювання. Мета цієї статті – порівняння продуктивності на процесорі, тому графіку ми не обговорюватимемо. Клас Shape, який представляє фізичне тіло, виглядає так:
- Призначення position і velocity, гадаю, очевидно. vertices - вершини фігури задані рандомно.
- bounds — це прямокутник, що обмежує, який повністю містить фігуру — використовується для попередньої перевірки перетинів.
- massInverse - одиниця, розділена на масу - ми будемо використовувати тільки це значення, тому зберігатимемо його замість маси.
- color - колір - використовується тільки при рендерингу, але зберігається в екземплярі фігури, що задається рандомно.
- overlapResolveAccumulator див. нижче.
Коли трикутник перетинається з фігуроюa, ми повинні трохи посунути його, щоб виключити накладання фігур один на одного. Також ми повинні перерахувати bounds. Але після переміщення трикутник перетинає іншу фігуру -b, і ми знову маємо перемістити його і знову перерахувати bounds. Зауважте, що після другого переміщення трикутник зновуопиниться над фігуроюa. Щоб уникнути повторних обчислень ми зберігатимемо величину, яку потрібно перемістити трикутник у спеціальному акумуляторі — overlapResolveAccumulator — і потім переміщатимемо фігуру цього значення, але тільки один раз.
Серце нашої програми – це метод ShapesApp::update(). Ось його спрощений варіант:
Кожен кадр ми викликаємо ShapesApp::updatePositions() метод, який змінює положення кожної фігури і розраховує новий Shape::bounds. Потім ми перевіряємо кожну фігуру з кожною іншою на перетин - CollisionSolver::solveCollision() . Я використав Separating Axis Theorem (SAT). Всі ці перевірки ми робимо NUM_PHYSICS_STEPS разів. Ця змінна служить кільком цілям - по-перше, фізика виходить стабільніша, по-друге, вона обмежує кількість об'єктів на екрані. з + + швидкий, дуже швидкий, і без цієї змінної у нас будуть десятки тисяч фігур, що сповільнить малювання. Я використав NUM_PHYSICS_STEPS = 20
На моєму старенькому ноутбуці ця програма розраховує 500 фігур максимум, перед тим, як fps починає падати нижче 30. Фуууу, всього 500. Згоден, небагато, але не забувайте, що кожен кадр ми повторюємо розрахунки 20 разів.
Думаю, що варто розбавити статтю скріншотами, тому:
1.2. Оптимізація номер 1. Spatial Grid
Я згадував, що хочу провести тести на якомога більш наближеній до реальності програмі. Те, що ми написали вище, насправді не використовується — перевіряти кожну фігуру з кожною дуже повільно. Для прискорення розрахунків використовується спеціальна структура. Пропоную використовувати звичайну 2d сітку – я назвав її Grid – яка складається з NxM осередків – Cell. На початку розрахунків ми записуватимемо в кожну комірку об'єкти, які знаходяться в ній.Тоді нам потрібно буде лише пробігтися по всіх осередках і перевірити перетин кількох пар об'єктів. Я неодноразово використовував цей підхід у релізах і він зарекомендував себе – пишеться дуже швидко, легко налагоджується, простий у розумінні.
Коміт другої версії програми можна переглянути тут. З'явився новий клас Grid і трохи змінився метод ShapesApp::update() - тепер він викликає методи сітки для перевірки перетинів.
Ця версія тримає вже 8000 фігур при 30 fps (не забуваємо про 20 ітерацій у кожному кадрі)! Довелося зменшити фігури вдесятеро, щоб вони помістилися у вікні.
1.3. Оптимізація номера 2. Multithreading.
Поділ основних завдань додав трохи головного болю. Так наприклад, якщо фігура перетинає кордон осередку в сітці, то вона буде одночасно в декількох осередках:
Тут фігураaзнаходиться в одному осередку, тоді якbвідразу в чотирьох. Тому доступ до цих осередків необхідно синхронізувати. Також потрібно синхронізувати доступ до деяких полів класу Shape. Для цього ми додали std::mutex Shape і Cell .
Запустивши цю версію я можу спостерігати 13000 фігур у 30 fps. Для такої кількості об'єктів довелося збільшити вікно! І знову – у кожному кадрі ми повторюємо симуляцію 20 разів.
2. Structure of Arrays
2.1. Перша версія програми
Те, що ми писали вище, я називаю традиційним підходом — я пишу такий код багато років і читаю, в основному, схожий код. Але тепер ми вб'ємо структуру Shape і подивимося, чи зможе ця невелика модифікація вплинути на продуктивність. На загальну радість рефакторинг виявився не складним, навіть тривіальним. Замість Shape ми будемо використовувати структуру із векторами:
І передаємо ми цюструктуру так:
Тобто. замість конкретних фігур передаються їх індекси та у методі з потрібних векторів беруться потрібні дані.
Ця версія програми видає 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підходу викликало б лише подив колег. Загалом, профілюйте, вимірювайте та робіть висновки самі :).