Ориентиран към данни дизайн. Виртуални функции.

Наскоро имаше доста интересна дискусия за DOD (Data Oriented Design). Следвах някои от аргументите от дискусията и исках сам да изпробвам тази техника. Най-важното е, че съм програмист, обсебен от оптимизацията. Исках да се уверя, че DOD дава много голям тласък на производителността. Всъщност, може ли виртуалните функции или няколко допълнителни байта в структурата, 30 години след пускането на процесори x86, да са толкова важни по отношение на производителността?

За да разберем, нека дефинираме двойка обекти - Автомобил и Камион. Следвайки правилата на традиционния ООП и имайки предвид, че и двата обекта могат да бъдат преместени, нека ги накараме да наследят от класа Movable. След това ще актуализираме тези обекти във всеки кадър, както би било в играта.

Не изглежда сложно. Добавих някои полета с данни за класовете Car и Truck, за да могат да бъдат добавени към кеша при актуализиране на всеки обект.

Сега за мениджърите на актуализации. Написах няколко различни мениджъри на актуализации, за да тествам различни начини за актуализиране на подвижни обекти. Най-лошият от тях ми се струва вектор std: vector от указатели към обектите Cars & Trucks. Всички обекти се „актуализират“, така че да не могат да бъдат разположени последователно в паметта, поради което получаваме големи загуби в кеша.

Следващата реализация на мениджъра на актуализации е масив с фиксиран размер вместо вектор, който ще ни позволи да се отървем от наказанието за производителност при актуализиране на векторния итератор. Все още се използват указатели, така че данните не са последователни.

Следващият начин е масив с фиксиран размер за всеки тип обект Car & Truck. В този случай чрез изоставяне на указатели се гарантира последователно поставяне на данни в паметта. Този метод трябва да помогне да се избегнат големи загуби на кеш.

И последният начин за внедряването му е Data Oriented Design - масив с фиксиран размер, като Movable. Няма виртуални повиквания и толкова данни, колкото е необходимо за тяхното актуализиране.

резултати

4 начина: вектор на указатели, масив от указатели, два масива от обекти и DOD.

Числата са както следва (време за изпълнение в μs):

Указател вектор: 86961
Масив от указатели: 77188
Два масива от обекти: 71645
Ориентиран към данни дизайн: 37521

Преходът от вектор към масив от указатели, от масив от указатели към масив от обекти дава 10% подобрение на производителността. Ориентираният към данни дизайн обаче осигурява 100% увеличение на производителността! Мениджърът на актуализации в реални игри е много по-сложен, но тези примери показват, че премахването на виртуални функции има значително влияние върху производителността.

Моля, обърнете внимание, че горният пример се основава на много малка функция - практически един ред код. Повече време се извършват много по-сложни действия с обекти: може би физика, откриване на сблъсъци, анимация и т.н. Така че ако увеличите сложността на функцията, резултатите няма да бъдат толкова впечатляващи.

Е, усложнявайки функцията и добавяйки най-простата дефиниция на сблъсъци към нея, получихме следните показатели (време за изпълнение в μs):

Указател вектор: 118566
Масив от указатели: 100268
Два масива от обекти: 87025
Ориентиран към данни дизайн: 70832

Сега DOD дава около 60% производителност спрямо векторния метод.