Jak wydajne są pamięci podręczne systemów encji?

Ostatnio dużo czytałem na temat systemów encji do implementacji w moim silniku gry C ++ / OpenGL. Dwie kluczowe korzyści, które stale słyszę o systemach chwalonych, to:

1. łatwa konstrukcja nowych rodzajów bytów, ponieważ nie trzeba zaplątać się w złożone hierarchie dziedziczenia, oraz
2. wydajność pamięci podręcznej, którą trudno mi zrozumieć.

Teoria jest oczywiście prosta; każdy komponent jest przechowywany w sposób ciągły w bloku pamięci, więc system, który dba o ten komponent, może po prostu iterować całą listę, bez konieczności przeskakiwania w pamięci i zabijania pamięci podręcznej. Problem polega na tym, że tak naprawdę nie mogę wymyślić sytuacji, w której jest to rzeczywiście praktyczne.

Najpierw przyjrzyjmy się, jak są przechowywane komponenty i jak się do siebie odnoszą. Systemy muszą być zdolne do pracy z więcej niż jednym komponentem, tzn. Zarówno system renderujący, jak i fizyka muszą mieć dostęp do komponentu transformacji. Widziałem wiele możliwych implementacji, które rozwiązują ten problem i żadna z nich nie robi tego dobrze.

Możesz mieć komponenty przechowujące wskaźniki do innych komponentów lub wskaźniki do podmiotów przechowujących wskaźniki do komponentów. Jednak gdy tylko wrzucisz wskaźniki do miksu, już zabijasz wydajność pamięci podręcznej. Możesz upewnić się, że każda tablica komponentów jest „n” duża, gdzie „n” to liczba bytów żyjących w systemie, ale takie podejście jest strasznie marnowaniem pamięci; bardzo utrudnia to dodawanie nowych typów komponentów do silnika, ale wciąż zmniejsza wydajność pamięci podręcznej, ponieważ przeskakujesz z jednej tablicy do drugiej. Możesz przeplatać tablicę jednostek, zamiast utrzymywać osobne tablice, ale wciąż marnujesz pamięć; co sprawia, że ​​dodawanie nowych komponentów lub systemów jest zbyt drogie, ale teraz z dodatkową zaletą unieważnienia wszystkich starych poziomów i zapisywania plików.

Wszystko to przy założeniu, że jednostki są przetwarzane liniowo na liście, w każdej ramce lub tikowaniu. W rzeczywistości często tak nie jest. Załóżmy, że używasz mechanizmu renderującego sektor / portal lub ośmiokąta, aby wykonać usuwanie okluzji. Możesz być w stanie przechowywać jednostki w sposób ciągły w sektorze / węźle, ale będziesz się skakał, czy ci się to podoba, czy nie. Następnie masz inne systemy, które mogą preferować byty przechowywane w innej kolejności. AI może być w porządku z przechowywaniem jednostek na dużej liście, dopóki nie zaczniesz pracować z AI LOD; następnie będziesz chciał podzielić tę listę według odległości od gracza lub innej miary LOD. Fizyka będzie chciała skorzystać z tego oktatu. Skrypty nie dbają o to, muszą działać, bez względu na wszystko.

Widziałem rozdzielanie komponentów między „logikę” (np. Ai, skrypty itp.) I „świat” (np. Renderowanie, fizykę, audio itp.) Oraz zarządzanie każdą listą osobno, ale listy te nadal muszą ze sobą współdziałać. AI jest bezcelowe, jeśli nie może wpływać na stan transformacji lub animacji używany do renderowania jednostki.

W jaki sposób systemy encji są „wydajne dla pamięci podręcznej” w silniku gier w świecie rzeczywistym? Być może istnieje podejście hybrydowe, z którego wszyscy korzystają, ale o którym nie mówi, na przykład globalne przechowywanie jednostek w tablicy i odwoływanie się do nich w obrębie oktetu?

Dwie kluczowe zalety, które ciągle chwalą systemy encji, to: 1) łatwa konstrukcja nowych rodzajów encji ze względu na to, że nie trzeba zaplątać się w złożone hierarchie dziedziczenia, oraz 2) wydajność pamięci podręcznej.

Należy pamiętać, że (1) jest zaletą projektowania opartego na komponentach , a nie tylko ES / ECS. Możesz używać komponentów na wiele sposobów, które nie mają części „systemowej” i działają one dobrze (a wiele gier indie i AAA korzysta z takich architektur).

Standardowy model obiektowy Unity (przy użyciu GameObjecti MonoBehaviourobiektów) nie jest ECS, ale jest projektem opartym na komponentach. Nowszą funkcją Unity ECS jest oczywiście rzeczywisty ECS.

Systemy muszą być zdolne do pracy z więcej niż jednym komponentem, tzn. Zarówno system renderowania, jak i fizyki muszą mieć dostęp do komponentu transformacji.

Niektóre ECS sortują kontenery komponentów według identyfikatora jednostki, co oznacza, że ​​odpowiednie komponenty w każdej grupie będą w tej samej kolejności.

Oznacza to, że jeśli iterujesz liniowo nad komponentem graficznym, to również iterujesz liniowo nad odpowiednimi komponentami transformacji. Być może pomijasz niektóre transformacje (ponieważ możesz mieć fizyczne wyzwalacze, których nie renderujesz itp.), Ale ponieważ zawsze przeskakujesz do przodu w pamięci (i zwykle nie na szczególnie dużych odległościach), nadal jedziesz uzyskać wzrost wydajności.

Jest to podobne do tego, w jaki sposób zaleca się stosowanie Struktury Tablic (SOA) w HPC. Procesor i pamięć podręczna poradzą sobie z wieloma tablicami liniowymi prawie tak dobrze, jak poradzą sobie z jedną tablicą liniową, i znacznie lepiej niż z przypadkowym dostępem do pamięci.

Inną strategią stosowaną w niektórych implementacjach ECS - w tym w Unity ECS - jest alokacja Komponentów na podstawie Archetypu ich odpowiedniej Jednostki. Oznacza to, że wszystkie podmioty z właśnie zestawu składników ( PhysicsBody, Transform) zostaną przyznane oddzielnie od podmiotów, z różnych komponentów (np PhysicsBody, Transform, i Renderable ).

Systemy w takich projektach działają najpierw poprzez znalezienie wszystkich Archetypów, które pasują do ich wymagań (które mają wymagany zestaw Komponentów), iteracji tej listy Archetypów i iteracji Komponentów przechowywanych w obrębie każdego pasującego Archetypu. Pozwala to na całkowicie liniowy i prawdziwy dostęp do komponentu O (1) w Archetype i pozwala Systemom znaleźć kompatybilne Encje o bardzo niskim obciążeniu (przeszukując małą listę Archetypów zamiast przeszukiwać potencjalnie setki tysięcy Encji).

Możesz mieć komponenty przechowujące wskaźniki do innych komponentów lub wskaźniki do podmiotów przechowujących wskaźniki do komponentów.

Komponenty odwołujące się do innych komponentów w tej samej encji nie muszą niczego przechowywać. Aby odwoływać się do komponentów w innych jednostkach, po prostu zapisz identyfikator jednostki.

Jeśli komponent może istnieć więcej niż jeden raz dla jednej encji i musisz odwoływać się do konkretnej instancji, zapisz identyfikator drugiej encji i indeks komponentu dla tej encji. Wiele implementacji ECS nie pozwala jednak na to, szczególnie dlatego, że sprawia, że ​​operacje te są mniej wydajne.

Możesz upewnić się, że każda tablica komponentów jest „n” duża, gdzie „n” to liczba bytów żyjących w systemie

Używaj uchwytów (np. Indeksów + znaczników generowania), a nie wskaźników, a następnie możesz zmieniać rozmiar tablic bez obawy o zerwanie odniesień do obiektu.

Możesz także zastosować podejście „tablica porcji” (tablica tablic) podobne do wielu popularnych std::dequeimplementacji (choć bez żałośnie małej wielkości porcji wspomnianych implementacji), jeśli chcesz zezwolić na wskaźniki z jakiegoś powodu lub jeśli mierzyłeś problemy z wydajność zmiany rozmiaru tablicy.

Po drugie, wszystko to zakłada, że ​​jednostki są przetwarzane liniowo na liście co klatkę / tik, ale w rzeczywistości tak często nie jest

To zależy od bytu. Tak, w wielu przypadkach nie jest to prawdą. Rzeczywiście, dlatego tak mocno podkreślam różnicę między projektowaniem opartym na komponentach (dobre) a systemem encji (szczególna forma CBD).

Niektóre elementy będą z pewnością łatwe do przetwarzania liniowego. Nawet w przypadkach użycia zwykle „obciążonych drzewem” zdecydowanie widzieliśmy wzrost wydajności wynikający z używania ciasno upakowanych tablic (głównie w przypadkach obejmujących maksymalnie N kilkuset, jak agenci AI w typowej grze).

Niektórzy programiści stwierdzili również, że korzyści płynące z zastosowania zorientowanych liniowo struktur danych zorientowanych na dane przewyższają korzyści płynące ze stosowania „inteligentniejszych” struktur opartych na drzewach. Wszystko zależy oczywiście od gry i konkretnych przypadków użycia.

Załóżmy, że używasz mechanizmu renderującego sektor / portal lub ośmiokąta, aby wykonać usuwanie okluzji. Możesz być w stanie przechowywać jednostki w sposób ciągły w sektorze / węźle, ale będziesz skakał, czy ci się to podoba, czy nie.

Byłbyś zaskoczony, jak bardzo tablica nadal pomaga. Skaczesz w znacznie mniejszym regionie pamięci niż „gdziekolwiek”, a nawet przy tych wszystkich skokach nadal istnieje większe prawdopodobieństwo, że skończysz w coś w pamięci podręcznej. W przypadku drzewa określonego rozmiaru lub mniejszego może być nawet w stanie wstępnie pobrać całość do pamięci podręcznej i nigdy nie przegapić pamięci podręcznej tego drzewa.

Istnieją również struktury drzew, które są zbudowane tak, aby żyć w ciasno upakowanych tablicach. Na przykład, używając swojego oktatu, możesz użyć struktury przypominającej stertę (rodzice przed dziećmi, rodzeństwo obok siebie) i upewnić się, że nawet podczas „drążenia” drzewa zawsze iterujesz do przodu w tablicy, co pomaga procesor optymalizuje dostęp do pamięci / wyszukiwania pamięci podręcznej.

Co jest ważnym punktem do zrobienia. Procesor x86 to złożona bestia. Procesor skutecznie uruchamia optymalizator mikrokodu w kodzie maszynowym, dzieląc go na mniejsze mikrokody i instrukcje zmiany kolejności, przewidywania wzorców dostępu do pamięci itp. Wzorce dostępu do danych są ważniejsze niż może być łatwo widoczne, jeśli wszystko, co masz, to zrozumienie na wysokim poziomie jak działa procesor lub pamięć podręczna.

Następnie masz inne systemy, które mogą preferować byty przechowywane w innej kolejności.

Możesz przechowywać je wiele razy. Po usunięciu tablic z dokładnością do minimum, może się okazać, że faktycznie oszczędzasz pamięć (ponieważ usunąłeś 64-bitowe wskaźniki i możesz użyć mniejszych indeksów) przy takim podejściu.

Możesz przeplatać tablicę jednostek zamiast utrzymywać osobne tablice, ale wciąż marnujesz pamięć

Jest to sprzeczne z dobrym użyciem pamięci podręcznej. Jeśli zależy Ci tylko na transformacjach i danych graficznych, dlaczego zmuszasz maszynę do pobierania wszystkich innych danych dotyczących fizyki i sztucznej inteligencji, wprowadzania danych, debugowania itd.?

Jest to zwykle argument na korzyść ECS w porównaniu do monolitycznych obiektów gry (choć tak naprawdę nie ma zastosowania w porównaniu do innych architektur opartych na komponentach).

Za to, co jest warte, większość implementacji ECS „produkcyjnych”, o których wiem, że używa przeplatanej pamięci. Popularne podejście Archetype, o którym wspomniałem wcześniej (używane na przykład w Unity ECS), jest bardzo wyraźnie zbudowane w celu użycia przeplatanej pamięci dla komponentów powiązanych z Archetypem.

AI jest bezcelowe, jeśli nie może wpływać na stan transformacji lub animacji używany do renderowania jednostki.

To, że sztuczna inteligencja nie może efektywnie uzyskać dostępu do transformacji danych liniowo, nie oznacza, że ​​żaden inny system nie może skutecznie korzystać z optymalizacji układu danych. Możesz użyć spakowanej tablicy do transformacji danych bez zatrzymywania działania systemów logiki gry w sposób ad hoc.

Zapominacie także o pamięci podręcznej kodu . Korzystając z systemowego podejścia ECS (w przeciwieństwie do bardziej naiwnej architektury komponentów), gwarantujesz, że uruchomisz tę samą małą pętlę kodu i nie będziesz przeskakiwał w przód iw tył przez tabele funkcji wirtualnych do zestawu losowych Updatefunkcji rozsianych po całym twój plik binarny. Tak więc w przypadku AI naprawdę chcesz zachować wszystkie różne elementy AI (ponieważ na pewno masz więcej niż jeden, abyś mógł komponować zachowania!) W osobnych segmentach i przetwarzać każdą listę osobno, aby uzyskać najlepsze wykorzystanie pamięci podręcznej kodu.

Dzięki kolejce opóźnionych zdarzeń (gdy system generuje listę zdarzeń, ale nie wywołuje ich, dopóki system nie zakończy przetwarzania wszystkich jednostek), możesz zapewnić, że pamięć podręczna kodu jest dobrze używana przy zachowaniu zdarzeń.

Stosując podejście, w którym każdy system wie, z których kolejek zdarzeń należy odczytać dla ramki, możesz nawet przyspieszyć czytanie zdarzeń. A przynajmniej szybciej niż bez.

Pamiętaj, że wydajność nie jest absolutna. Nie musisz eliminować wszystkich ostatnich braków pamięci podręcznej, aby zacząć widzieć korzyści płynące z dobrego projektowania zorientowanego na dane.

Nadal trwają badania nad poprawą działania wielu systemów gier z architekturą ECS i wzorcami projektowania zorientowanymi na dane. Podobnie jak niektóre niesamowite rzeczy, które widzieliśmy w SIMD w ostatnich latach (np. Parsery JSON), widzimy coraz więcej rzeczy wykonanych z architekturą ECS, która nie wydaje się intuicyjna dla klasycznych architektur gier, ale oferuje wiele korzyści (szybkość, wielowątkowość, testowalność itp.).

A może istnieje podejście hybrydowe, z którego wszyscy korzystają, ale o którym nikt nie mówi

Właśnie tego zalecałem w przeszłości, szczególnie osobom sceptycznie nastawionym do architektury ECS: stosuj dobre podejście do komponentów, w których wydajność ma kluczowe znaczenie. Używaj prostszej architektury, gdzie prostota skraca czas programowania. Nie klaksonuj każdego pojedynczego komponentu w ścisłej nadmiernej definicji komponentyzacji, jak proponuje ECS. Rozwijaj architekturę komponentów w taki sposób, abyś mógł łatwo stosować podejścia podobne do ECS tam, gdzie mają one sens, i stosować prostszą strukturę komponentów, w których podejście podobne do ECS nie ma sensu (lub ma mniej sensu niż struktura drzewa itp.) .

Osobiście jestem stosunkowo niedawno nawrócony na prawdziwą moc ECS. Chociaż dla mnie czynnikiem decydującym było coś rzadko wspominanego w ECS: sprawia, że ​​pisanie testów dla systemów gier i logiki jest prawie banalne w porównaniu do ściśle powiązanych projektów opartych na logice, z którymi pracowałem w przeszłości. Ponieważ architektury ECS wprowadzają całą logikę do Systemów, które po prostu zużywają Komponenty i produkują aktualizacje Komponentów, zbudowanie „próbnego” zestawu Komponentów do testowania zachowania Systemu jest dość łatwe; ponieważ większość logiki gier powinna znajdować się wyłącznie w systemach, co oznacza, że ​​testowanie wszystkich systemów zapewni dość wysoki zasięg kodu logiki gry. Systemy mogą używać próbnych zależności (np. Interfejsów GPU) do testów o znacznie mniejszym stopniu złożoności lub wpływie na wydajność niż „

Na marginesie, możesz zauważyć, że wiele osób mówi o ECS, nie rozumiejąc, co to w ogóle jest. Widzę klasyczną Unity zwaną ECS z przygnębiającą częstotliwością, co pokazuje, że zbyt wielu twórców gier utożsamia „ECS” z „Komponentami” i prawie całkowicie ignoruje część „Entity System”. Widzisz dużo miłości na ECS w Internecie, kiedy duża część ludzi tak naprawdę popiera projektowanie oparte na komponentach, a nie na faktycznym ECS. W tym momencie argumentowanie tego jest prawie bezcelowe; ECS został uszkodzony z pierwotnego znaczenia na ogólny termin i równie dobrze możesz zaakceptować, że „ECS” nie oznacza tego samego, co „ECS zorientowany na dane”. : /