Nomad Game Engine: Част 4.3 - AoS срещу SoA

Оптимизиране на съхранението на данни

Тази публикация е част от поредица, в която документирам опита си в изграждането на ECS игра на двигателя от нулата. Вижте началната страница на този проект за още публикации, информация и изходен код.

В следващите няколко публикации в блога ще се потопим от дълбокия край. Ще оставя това като предупреждение тук: нищо от това всъщност не е необходимо за ECS. Разликата в производителността в по-голямата част от игрите ще бъде незначителна и в крайна сметка добавя много сложност към вътрешната работа на компонентния мениджър. Ако целта ви е просто да изградите ECS и да го накарате да работи, пропуснете останалите от 4.x публикации в блога 4.x Nomad Engine и започнете да четете Част 5: Системи.

Това каза, че информацията в тези публикации е * невероятно готина * и много уникална. Ще се запознаете с радостите на метапрограмирането на шаблони, с много конкретни примери поради факта, че изграждаме много конкретна система: игра на двигателя. Ако искате да разширите ума си, четете нататък!

Целта на този блог е да настрои разсъжденията за следващите две публикации, като предостави архитектура и обяснение на високо ниво.

Масив от структури срещу Структура на масиви

Нека да разгледаме бързо нашата реализация за първата ни итерация на „мениджъра на общи компоненти“. Нашата структура за съхранение изглеждаше така:

struct ComponentData {
 неподписан размер на int = 1;
 std :: array  данни;
}

Забележете, че нашите данни се съхраняват като масив от структури (в този случай структурата е ComponentType). В останалата част от тази публикация в блога ще използваме примерен компонент, който срещнахме, но ще добавим малко допълнителни неща към него:

структура Трансформира {
  int x;
  плувам y;
  двойно z;
}

Нека кажа това отпред: Истински компонент очевидно не би изглеждал така. Единствената причина да правим това е така, че нашите примери имат повече смисъл. Повечето компоненти всъщност ще имат различни видове членове, така че това ще го симулира, без да прави имената им твърде сложни.

Какво е съхранение на "SoA"?

Структурата на хранилището на Array прехвърля общоприетото програмно споразумение на главата си. Вместо да съхранява масив от структури, се създава структура с масив за всеки елемент от оригиналната структура. Тази концепция е най-добре илюстрирана с действителен пример.

// Масив от структури
структура Трансформира {
 int x;
 плувам y;
 двойно z;
}
std :: масив <Трансформирай, 1024> aos;
// Структура на масиви
struct soa {
 std :: масив  x;
 std :: масив  y;
 std :: масив <двойно, 1024> z;
}

Защо SoA съхранение е по-добро?

Нека поясня, преди да отговоря на това, че всъщност не винаги е по-добре. Дали SoA или AoS съхранението е по-добро, е най-вече въпросът как се използва компонентът.

// Вероятно най-добре като AoS съхранение
структура Трансформира {
  плава х;
  плувам y;
  float z;
}

Масивът от структури за съхранение е по-добър, когато всички полета на компонент обикновено се осъществяват едновременно. Например, може да имаме компонент Transform със стойности x, y и z - всяка от тях вероятно ще бъде достъпна заедно, тъй като няма много ситуации, които бихме искали само стойността x на компонент.

// Вероятно най-доброто като SoA съхранение
Stru Health {
  плаващ токЗдраве;
  float maxHealth;
  float healthRegen;
  int shieldAmount;
  int shieldModifier;
  bool isimmune;
}

Структурата на съхранението на масиви е по-добра, когато компонентът има множество полета в него, които могат да бъдат достъпни поотделно. Например, ако разгледаме нашия компонент Health, който дефинирахме по-горе, вероятно е различните системи да актуализират различни части от компонента сами. Една система може да отговаря за актуализирането на здравето на компонента въз основа на стойността му на HealthRegen, а друга система може да се справи с контрола на имунитета. Когато образуванието нанесе щети, която и система да е отговорна за това, трябва да има достъп до текущите Здраве, shieldAmount и isimmune, но няма да се грижи за maxHealth или healthRegen. В ситуации като тези, съхранението на Struct of Array е по-добро.

Ето някои gifs модели на достъп за съхранение за всеки от тези два сценария, за да онагледят тази точка:

Пример 1

Ще изпълним следния код на компонента Transform и ще сравним модела за достъп до памет между AoS и SoA:

За пореден път, ако не можете да видите съдържанието на реда, защото сте на iOS, опитайте да го отворите в браузър (Medium: оправете нещата си).

За този пример ще приемем, че никоя единица не е извън границите (това вероятно ще е най-вероятният случай, като се има предвид, че този код ще стартира всеки отметка). Това означава, че достъпът до паметта ни изглежда така:

Масив от структури позволява достъп до паметтаСтруктура на достъпа до паметта на масивите

Ще забележите, че и двамата по същество четат памет последователно. Това е чудесно за ефективност, защото означава по-малко пропуски в кеша. В зависимост от размера на различните ни нива на кеша, решението AoS може да бъде малко по-добро, но като цяло и двамата имат достъп до данни последователно, което означава, че нашият процесор ще може да използва максимално кеша си.

Пример 2

Сега вместо това нека разгледаме още един наш здравословен компонент, който представихме по-рано в публикацията. Ще прилагаме гореспоменатата „система за реген“, която увеличава здравето на субектите въз основа на техния здравен режим. Ето кода:

Сега нека да разгледаме модела за достъп до паметта въз основа на това как съхраняваме компонента:

Масив от структури позволява достъп до паметтаСтруктура на достъпа до паметта на масивите

Тук ще забележите, че версията за съхранение на AoS има много празно място! Това е така, защото ние имаме достъп само до две полета на компонента, а останалите се изтеглят в кеша без причина. Версията SoA продължава да има голяма кеш производителност, тъй като се включват само полетата на компонента, които са необходими.

Математическо време!

Докато визуализациите може да са ви убедили сами, ако все още не сте убедени, нека да направим малко математика!

Повечето компютри имат размер на кеширащата линия от 64 байта. Да приемем, че компонентът ни за здраве е такъв, както го дефинирахме по-горе, което ще означава, че ще отнеме:

float (4 байта) * 3 = 12 байта
int (4 байта) * 2 = 8 байта
bool (1 байт) * 1 = 1 байт

Ще се спра на действителното пространство, което тази структура ще заеме по-долу (поради подплънките на структура), но нека приемем, че тогава структурата е 12 + 8 + 1 = 21 байта.

Да допуснем, че изпълняваме нашия код по-горе за възстановяване на здравето. Ако съхраняваме структурата, използвайки AoS съхранение, всеки ред на кеш, който дърпаме, ще съдържа 3 пълни компонента (64/21 ~ = 3).

Нека се преструваме, че играта ни има 10 000 единици на екрана, които всички регенерират здравето всеки кърлеж. Ако използваме AoS пространство за съхранение, това означава, че ще изтеглим 10,000 / 3 ~ = 3300 кеш линии.

Ако използвахме SoA съхранение, щяхме да зареждаме два плътно опаковани масива с текущи стойности Health and HealthRegen. Всеки ред на кеша ще съдържа 64/4 = 16 компонента на стойност, но ще трябва да издърпаме в два реда - един за currentHealth и един за healthRegen. По-лесен начин да мислим за това е, че зареждаме два масива от 10 000 плаваща. Ако приемем, че можем да поберем 64/4 = 16 плава в кеш линия, това би означавало 10,000 / 16 ~ = 625 кеш линии за всеки от нашите два масива. За да изпълним нашия код на всички 10 000 единици, в крайна сметка ще изтеглим 625 * 2 = 1250 кеш линии, или около 1/3 от редовете в сравнение с AoS

Бележка за структурни подплънки

В горния пример бихте предположили, че healthRegen ще заеме 12 + 8 + 1 = 21 байта пространство, но в действителност това отнема 24, поради структурно подплащане. Това всъщност е допълнително предимство на SoA съхранението - тъй като всеки от членовете се съхранява в плътно опаковани масиви, ние няма да загубим място за структуриране на подложки.

Това наистина ли е необходимо?

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

За да отговорите на това, в крайна сметка се свежда до кеширане на пропуски. Ако правите много достъп до паметта (много субекти на екрана), удобните за кеширане данни стават все по-важни. Нека използваме тази публикация от 2012 г., за да видим дали можем на теория да представим някои числа.

Intel Xeon 5500 i7 има време за достъп до кеш L2 от ~ 10 цикъла, докато достъпът до L3 кеш отнема около 40 цикъла - или около 4 пъти по-дълъг. Ако в крайна сметка имаме достатъчно компоненти (или достатъчно големи компоненти), използването на структура за съхранение на масив вместо масив от структурно съхранение може значително да ускори някои пакетни операции.

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