Ориентиран към данни дизайн на практика

Напоследък все по-често човек може да попадне на дискусия на интересна, но не особено популярна парадигма - т.нар. Ориентиран към данни дизайн (DOD). Ако кандидатствате за високопроизводителна компютърна работа, бъдете подготвени за подходящите въпроси. Но бях много изненадан да разбера, че някои от моите колеги не са чували за този подход и след кратка дискусия бяха скептични към него. В тази статия ще се опитам да сравня традиционното ООП подход с DOD.

Какво е DOD?

Вторият тест работи с 30% по-бързо (във VS2017 и gcc7.0.1). Но защо?

Размерът на S структурата е 24 байта. Моят процесор (Intel Core i7) има 32KB кеш на ядро ​​с 64B кеш линия. Това означава, че когато се искат данни от паметта, само две S структури напълно ще се поберат в една кеш линия. В първия тест прочетох само едно поле int, т.е. с един достъп до паметта в една кеш линия ще има само 2 (понякога 3) полета, от които се нуждаем. Във втория тест чета същата стойност int, но от вектор. std: vector гарантира последователност на данните. Това означава, че когато имаме достъп до паметта в един кеш ред, ще имаме 16 (64KB/sizeof (int) = 16) стойности, от които се нуждаем. Оказва се, че при втория тест имаме достъп до паметта по-рядко. Известно е, че достъпът до памет е слабо звено в съвременните процесори.

Как стоят нещата на практика?

Примерът по-горе ясно показва ползите от използването SoA (Структура на масиви) вместо AoS (Масив от структури), но този пример е от категорията Hello World, т.е. далеч от реалния живот. В реалния код има много зависимости и специфични данни, които може да не дадат печалба в производителността. Освен това, ако в тестовете се позоваваме на всички полета на структурата, няма да има разлика в производителността.

За да разбера реалността на прилагането на подхода, реших да напиша повече или по-малко сложен код, използвайки и двете техники, и да сравня резултатите. Нека бъде 2d симулация на твърди тела - ще създадем N изпъкнали полигони, ще зададем параметри - маса, скорост и т.н. и вижте колко обекта можем да симулираме, докато останем на 30 fps.

1. Масив от структури

1.1. Първата версия на програмата

Изходният код за първата версия на програмата може да бъде взет от този ангажимент. Сега ще разгледаме накратко кода.

За простота програмата е написана за Windows и използва DirectX11 за рендиране. Целта на тази статия е да сравнява производителността на процесор, така че няма да обсъждаме графики. Класът Shape, който представлява физическото тяло, изглежда така:

  • Мисля, че определянето на позицията и скоростта е очевидно. върхове - произволно посочени върхове на фигурата.
  • граници е ограничителното поле, което съдържа цялата форма - използва се за предварителна проверка за пресичания.
  • massInverse - единица, разделена на маса - ще използваме само тази стойност, така че ще я съхраняваме вместо маса.
  • color - цвят - използва се само за рендиране, но се съхранява в екземпляр на форма, зададен произволно.
  • overlapResolveAccumulator вижте обяснението по-долу.

практика

Когато триъгълник пресича фигура а, трябва да го преместим малко, за да предотвратим припокриването на фигурите. Също така трябва да преизчислим границите. Но след преместване триъгълникът пресича друга форма - б, и трябва да го преместим отново и отново да преизчислим границите. Забележете, че след втория ход триъгълникът отново ще бъде над формата. а. За да избегнем многократни изчисления, ще съхраним сумата, с която трябва да преместим триъгълника в специален акумулатор - overlapResolveAccumulator - и по-късно ще преместим фигурата с тази стойност, но само веднъж.