Moje pytanie brzmi: skoro nie powtarzam liniowo jednej ciągłej tablicy w tych przypadkach, czy od razu poświęcam przyrost wydajności dzięki alokacji komponentów w ten sposób?
Szanse są takie, że otrzymacie mniej braków pamięci podręcznej z osobnymi „pionowymi” tablicami dla każdego typu komponentu niż przeplatanie komponentów dołączonych do bytu w „poziomym” bloku o zmiennej wielkości, że tak powiem.
Powodem jest to, że po pierwsze reprezentacja „pionowa” zużywa mniej pamięci. Nie musisz martwić się o wyrównanie dla jednorodnych tablic przydzielonych sąsiadująco. Z niejednorodnymi typami przydzielonymi do puli pamięci, musisz się martwić o wyrównanie, ponieważ pierwszy element w tablicy może mieć zupełnie inne wymagania co do wielkości i wyrównania niż drugi. W rezultacie często trzeba dodać wypełnienie, tak jak w prostym przykładzie:
// Assuming 8-bit chars and 64-bit doubles.
struct Foo
{
// 1 byte
char a;
// 1 byte
char b;
};
struct Bar
{
// 8 bytes
double opacity;
// 8 bytes
double radius;
};
Powiedzmy, że chcemy przeplatać Fooi Barprzechowywać je obok siebie w pamięci:
// Assuming 8-bit chars and 64-bit doubles.
struct FooBar
{
// 1 byte
char a;
// 1 byte
char b;
// 6 bytes padding for 64-bit alignment of 'opacity'
// 8 bytes
double opacity;
// 8 bytes
double radius;
};
Teraz zamiast zajmować 18 bajtów do przechowywania Foo i Bar w osobnych regionach pamięci, potrzeba 24 bajtów na ich połączenie. Nie ma znaczenia, czy zamienisz zamówienie:
// Assuming 8-bit chars and 64-bit doubles.
struct BarFoo
{
// 8 bytes
double opacity;
// 8 bytes
double radius;
// 1 byte
char a;
// 1 byte
char b;
// 6 bytes padding for 64-bit alignment of 'opacity'
};
Jeśli zajmiesz więcej pamięci w kontekście dostępu sekwencyjnego bez znaczącej poprawy wzorców dostępu, zazwyczaj poniesiesz więcej braków pamięci podręcznej. Ponadto krok do przejścia od jednej encji do następnej wzrasta i do zmiennej wielkości, co powoduje, że musisz wykonać skoki pamięci o zmiennej wielkości, aby przejść od jednej encji do drugiej, aby zobaczyć, które zawierają komponenty, które „ jestem zainteresowany.
Tak więc użycie „pionowej” reprezentacji przechowywania typów komponentów jest w rzeczywistości bardziej optymalne niż alternatywy „poziome”. To powiedziawszy, problem z brakami pamięci podręcznej z reprezentacją pionową można zilustrować tutaj:
Gdzie strzałki wskazują po prostu, że jednostka „jest właścicielem” komponentu. Widzimy, że gdybyśmy spróbowali uzyskać dostęp do wszystkich elementów ruchu i renderowania bytów, które mają oba, skończylibyśmy w całym miejscu w pamięci. Ten rodzaj sporadycznego wzorca dostępu może powodować ładowanie danych do linii pamięci podręcznej w celu uzyskania dostępu do, powiedzmy, komponentu ruchu, a następnie dostępu do większej liczby komponentów i wyrzucenia wcześniejszych danych, tylko w celu ponownego załadowania tego samego obszaru pamięci, który został już eksmitowany dla innego ruchu składnik. Może to być bardzo marnotrawne ładowanie dokładnie tych samych obszarów pamięci więcej niż raz do linii pamięci podręcznej tylko po to, aby przejść przez pętlę i uzyskać dostęp do listy komponentów.
Wyczyśćmy trochę ten bałagan, abyśmy mogli lepiej widzieć:
Pamiętaj, że jeśli spotkasz się z takim scenariuszem, zwykle trwa to długo po uruchomieniu gry, po dodaniu i usunięciu wielu komponentów i elementów. Ogólnie rzecz biorąc, kiedy gra się rozpoczyna, możesz dodać wszystkie byty i odpowiednie komponenty razem, w którym to momencie mogą mieć bardzo uporządkowany, sekwencyjny wzór dostępu z dobrą lokalizacją przestrzenną. Po wielu usunięciach i wstawieniach możesz dostać coś takiego jak powyższy bałagan.
Bardzo łatwym sposobem na poprawienie tej sytuacji jest proste posortowanie składników na podstawie identyfikatora / indeksu podmiotu, który jest ich właścicielem. W tym momencie dostajesz coś takiego:
I to jest znacznie bardziej przyjazny dla pamięci podręcznej wzorzec dostępu. To nie jest idealne, ponieważ widzimy, że musimy pomijać niektóre elementy renderowania i ruchu tu i tam, ponieważ nasz system jest zainteresowany tylko jednostkami, które mają oba z nich, a niektóre jednostki mają tylko komponent ruchu, a niektóre tylko komponent renderowania , ale przynajmniej będziesz w stanie przetwarzać niektóre ciągłe komponenty (zwykle w praktyce, zazwyczaj, ponieważ często dołączasz odpowiednie komponenty będące przedmiotem zainteresowania, na przykład może więcej elementów w twoim systemie, które mają komponent ruchu, będą miały komponent renderujący niż nie).
Co najważniejsze, po ich posortowaniu nie będzie ładować danych regionu pamięci do linii pamięci podręcznej, tylko po to, aby ponownie załadować go w jednej pętli.
I to nie wymaga wyjątkowo skomplikowanego projektu, od czasu do czasu przechodzi tylko sortowanie liniowe w czasie, być może po wstawieniu i usunięciu wiązki składników dla określonego typu elementu, w którym to momencie można oznaczyć go jako wymagające sortowania. Racjonalnie zaimplementowane sortowanie radix (możesz nawet zrównoleglić, co robię) może posortować milion elementów w około 6ms na moim czterordzeniowym i7, jak pokazano tutaj:
Sorting 1000000 elements 32 times...
mt_sort_int: {0.203000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]
mt_sort: {1.248000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]
mt_radix_sort: {0.202000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]
std::sort: {1.810000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]
qsort: {2.777000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]
Powyższe polega na posortowaniu miliona elementów 32 razy (w tym czasu na memcpywyniki przed i po sortowaniu). I zakładam, że przez większość czasu nie będziesz mieć więcej niż miliona komponentów do sortowania, więc bardzo łatwo powinieneś to podkraść, nie powodując zauważalnego zacinania się klatek.