Sposób myślenia zorientowany na dane
Projektowanie zorientowane na dane nie oznacza stosowania SoAs wszędzie. Oznacza to po prostu projektowanie architektur z dominującym naciskiem na reprezentację danych - szczególnie z naciskiem na efektywny układ pamięci i dostęp do pamięci.
Może to prowadzić do powtórzeń SoA, gdy będzie to właściwe:
struct BallSoa
{
vector<float> x; // size n
vector<float> y; // size n
vector<float> z; // size n
vector<float> r; // size n
};
... jest to często odpowiednie dla logiki pętli pionowej, która nie przetwarza jednocześnie elementów wektora środka kuli i promienia (cztery pola nie są jednocześnie gorące), ale zamiast tego pojedynczo (pętla przez promień, kolejne 3 pętle przez poszczególne składniki centrów kuli).
W innych przypadkach bardziej odpowiednie może być użycie AoS, jeśli pola są często dostępne razem (jeśli Twoja logika pętli iteruje wszystkie pola piłek zamiast pojedynczo) i / lub jeśli potrzebny jest losowy dostęp do piłki:
struct BallAoS
{
float x;
float y;
float z;
float r;
};
vector<BallAoS> balls; // size n
... w innych przypadkach może być właściwe zastosowanie hybrydy, która równoważy obie korzyści:
struct BallAoSoA
{
float x[8];
float y[8];
float z[8];
float r[8];
};
vector<BallAoSoA> balls; // size n/8
... możesz nawet skompresować rozmiar piłki do połowy za pomocą półpławików, aby dopasować więcej pól do linii / strony pamięci podręcznej.
struct BallAoSoA16
{
Float16 x2[16];
Float16 y2[16];
Float16 z2[16];
Float16 r2[16];
};
vector<BallAoSoA16> balls; // size n/16
... może nawet promień nie jest dostępny prawie tak często, jak środek kuli (być może twoja baza kodu często traktuje je jak punkty, a rzadko jak sfery, np.). W takim przypadku możesz dodatkowo zastosować technikę podziału pola na ciepło / zimno.
struct BallAoSoA16Hot
{
Float16 x2[16];
Float16 y2[16];
Float16 z2[16];
};
vector<BallAoSoA16Hot> balls; // size n/16: hot fields
vector<Float16> ball_radiuses; // size n: cold fields
Kluczem do projektowania zorientowanego na dane jest rozważenie wszystkich tego rodzaju reprezentacji na wczesnym etapie przy podejmowaniu decyzji projektowych, aby nie uwięzić się w nieoptymalnej reprezentacji z publicznym interfejsem.
Zwraca uwagę na wzorce dostępu do pamięci i towarzyszące mu układy, co sprawia, że są one znacznie silniejsze niż zwykle. W pewnym sensie może nawet nieco zburzyć abstrakcje. Odkryłem, że stosując ten sposób myślenia, na który już nie patrzę std::deque, np. Pod względem wymagań algorytmicznych w takim samym stopniu, jak zagregowana ciągła reprezentacja bloków, jaką posiada, oraz sposób, w jaki działa losowy dostęp na poziomie pamięci. W pewnym stopniu koncentruje się na szczegółach implementacji, ale szczegóły implementacji, które mają taki sam lub większy wpływ na wydajność, jak złożoność algorytmiczna opisująca skalowalność.
Przedwczesna optymalizacja
Wiele z głównych zagadnień projektowania zorientowanego na dane będzie, przynajmniej na pierwszy rzut oka, niebezpiecznie bliskie przedwczesnej optymalizacji. Doświadczenie często uczy nas, że takie mikrooptymalizacje najlepiej stosować z perspektywy czasu i przy użyciu profilera w ręku.
Być może jednak silnym przesłaniem przy projektowaniu zorientowanym na dane jest pozostawienie miejsca na takie optymalizacje. Właśnie to podejście zorientowane na dane może pomóc:
Projektowanie zorientowane na dane może pozostawić tchnienie, by eksplorować bardziej efektywne reprezentacje. Niekoniecznie chodzi o osiągnięcie doskonałości układu pamięci za jednym razem, ale o wcześniejsze rozważenie odpowiednich kwestii, aby umożliwić coraz bardziej optymalne odwzorowanie.
Szczegółowy projekt obiektowy
Wiele dyskusji na temat projektowania zorientowanych na dane zmierzy się z klasycznymi pojęciami programowania obiektowego. Chciałbym jednak spojrzeć na to, co nie jest tak hardkorowe, jak całkowite odrzucenie OOP.
Trudność z projektowaniem obiektowym polega na tym, że często kusi nas do modelowania interfejsów na bardzo szczegółowym poziomie, pozostawiając nas uwięzionym w skalarnym, indywidualnym sposobie myślenia zamiast równoległego, masowego sposobu myślenia.
Jako przesadny przykład, wyobraź sobie ukierunkowane obiektowo podejście do pojedynczego piksela obrazu.
class Pixel
{
public:
// Pixel operations to blend, multiply, add, blur, etc.
private:
Image* image; // back pointer to access adjacent pixels
unsigned char rgba[4];
};
Mam nadzieję, że nikt tego nie robi. Aby ten przykład był naprawdę obrzydliwy, zapisałem wskaźnik wstecz do obrazu zawierającego piksel, aby mógł on uzyskać dostęp do sąsiednich pikseli w celu zastosowania algorytmów przetwarzania obrazu, takich jak rozmycie.
Wskaźnik cofania obrazu natychmiast dodaje rażący narzut, ale nawet jeśli go wykluczyliśmy (dzięki czemu tylko publiczny interfejs piksela zapewnia operacje, które dotyczą jednego piksela), otrzymujemy klasę reprezentującą piksel.
Teraz nie ma nic złego w klasie w bezpośrednim sensie narzutowym w kontekście C ++ oprócz tego wskaźnika wstecz. Optymalizacja kompilatorów C ++ jest świetna w usuwaniu całej zbudowanej przez nas struktury i niszczeniu jej do drobnych ekranów.
Trudność polega na tym, że modelujemy enkapsulowany interfejs na zbyt szczegółowym poziomie pikseli. To nas uwięziło w tego rodzaju szczegółowym projekcie i danych, a potencjalnie ogromna liczba zależności klientów Pixelłączy je z tym interfejsem.
Rozwiązanie: usuń zorientowaną obiektowo strukturę ziarnistego piksela i rozpocznij modelowanie interfejsów na bardziej zgrubnym poziomie, zajmując się dużą liczbą pikseli (na poziomie obrazu).
Dzięki modelowaniu na poziomie obrazu zbiorczego mamy znacznie więcej miejsca na optymalizację. Możemy na przykład przedstawiać duże obrazy jako zlepione kafelki o wymiarach 16 x 16 pikseli, które idealnie pasują do 64-bajtowej linii pamięci podręcznej, ale umożliwiają efektywny dostęp sąsiednich pikseli w pionie z typowo małym krokiem (jeśli mamy wiele algorytmów przetwarzania obrazu, które trzeba uzyskać dostęp do sąsiednich pikseli w sposób pionowy) jako hardkorowy przykład zorientowany na dane.
Projektowanie na grubszym poziomie
Powyższy przykład interfejsów do modelowania na poziomie obrazu jest rodzajem oczywistego przykładu, ponieważ przetwarzanie obrazu jest bardzo dojrzałym obszarem, który został zbadany i zoptymalizowany pod kątem śmierci. Jednak mniej oczywista może być cząstka w emiterze cząstek, duszek kontra zbiór duszek, krawędź na wykresie krawędzi, a nawet osoba kontra zbiór ludzi.
Kluczem do umożliwienia optymalizacji zorientowanej na dane (w ramach foresightu lub retrospekcji) często jest sprowadzenie się do projektowania interfejsów na znacznie bardziej zgrubnym poziomie, masowo. Idea projektowania interfejsów dla pojedynczych encji zostaje zastąpiona projektowaniem dla kolekcji encji z dużymi operacjami, które przetwarzają je masowo. Dotyczy to zwłaszcza i natychmiastowego ukierunkowania sekwencyjnych pętli dostępu, które muszą uzyskać dostęp do wszystkiego i nie mogą pomóc, ale mają złożoność liniową.
Projektowanie zorientowane na dane często zaczyna się od pomysłu koalescencji danych w celu masowego tworzenia agregatów modelujących dane. Podobny sposób myślenia przypomina towarzyszące mu projekty interfejsów.
Jest to najcenniejsza lekcja, jaką wyciągnąłem z projektowania zorientowanego na dane, ponieważ nie jestem wystarczająco doświadczony w architekturze komputerowej, aby często znaleźć najbardziej optymalny układ pamięci dla czegoś przy pierwszej próbie. Staje się to czymś, co iteruję z profilerem w dłoni (a czasem z kilkoma brakami po drodze, gdy nie przyspieszyłem rzeczy). Jednak aspekt projektowania interfejsu zorientowanego na dane pozostawia mi miejsce na szukanie coraz wydajniejszych reprezentacji danych.
Kluczem jest zaprojektowanie interfejsów na bardziej zgrubnym poziomie, niż zwykle kusi. Ma to również często zalety uboczne, takie jak łagodzenie narzutu dynamicznej wysyłki związanej z funkcjami wirtualnymi, wywołania wskaźnika funkcji, wywołania dylib oraz niemożność wstawienia tych. Głównym pomysłem na usunięcie tego wszystkiego jest spojrzenie na przetwarzanie masowe (jeśli dotyczy).
ball->do_something();porównaniuball_table.do_something(ball)), chyba że chcesz podrobić spójną całość za pomocą pseudo-wskaźnika(&ball_table, index).Krótka odpowiedź: masz całkowitą rację, a artykułom takim jak ten całkowicie brakuje tego punktu.
Pełna odpowiedź brzmi: podejście „struktura tablic” w twoich przykładach może mieć przewagę wydajności w przypadku niektórych rodzajów operacji („operacje na kolumnach”), a „tablice struktur” w przypadku innych operacji („operacji na wierszach” ”, jak te wspomniane powyżej). Ta sama zasada wpłynęła na architektury baz danych, istnieją bazy danych zorientowane na kolumny w porównaniu z klasycznymi bazami zorientowanymi na wiersze
Tak więc druga sprawa do rozważenia przy wyborze projektu, jaki rodzaj operacji trzeba najbardziej w swoim programie, a jeśli te będą korzystać z innego układu pamięci. Jednak pierwszą rzeczą do rozważenia jest to, czy naprawdę potrzebujesz tej wydajności (myślę, że w programowaniu gier, gdzie powyższy artykuł pochodzi od ciebie, często masz ten wymóg).
Większość obecnych języków OO używa układu pamięci „Array-Of-Struct” dla obiektów i klas. Uzyskiwanie korzyści z OO (takich jak tworzenie abstrakcji dla danych, enkapsulacja i bardziej lokalny zakres podstawowych funkcji) jest zazwyczaj związane z tego rodzaju układem pamięci. Tak długo, jak nie wykonujesz obliczeń o wysokiej wydajności, nie uważam SoA za podstawowe podejście.
źródło
Balls równie dobrze jak mogą być indywidualnefloats lubvec3s (które same będą podlegać transformacji SOA).