Brakuje pamięci podręcznej i użyteczność w systemach Entity Systems

Ostatnio badam i wdrażam System Entity dla moich ram. Myślę, że czytam większość artykułów, poprawek i pytań na ten temat, które mogłem znaleźć, i jak dotąd myślę, że wystarczająco dobrze rozumiem ten pomysł.

Pojawiły się jednak pytania dotyczące ogólnego zachowania C ++, języka, w którym implementuję system encji, a także niektórych problemów z użytecznością.

Tak więc jednym podejściem byłoby przechowywanie tablicy komponentów bezpośrednio w encji, czego nie zrobiłem, ponieważ rujnuje to miejsce w pamięci podręcznej podczas iteracji po danych. Z tego powodu postanowiłem mieć jedną tablicę dla każdego typu komponentu, więc wszystkie komponenty tego samego typu są ciągłe w pamięci, co powinno być optymalnym rozwiązaniem do szybkiej iteracji.

Ale kiedy mam do iteracji tablice komponentów, aby coś z nimi zrobić z systemu w rzeczywistej implementacji rozgrywki, zauważam, że prawie zawsze pracuję z dwoma lub więcej typami komponentów jednocześnie. Na przykład system renderowania używa razem komponentu Transform i Model do rzeczywistego wywołania renderowania. 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? Czy to problem, gdy iteruję w C ++ dwie różne ciągłe tablice i używam danych z obu w każdym cyklu?

Inną rzeczą, o którą chciałem zapytać, jest to, w jaki sposób należy zachować odniesienia do komponentów lub encji, ponieważ sama natura tego, jak komponenty są układane w pamięci, mogą łatwo zmieniać pozycje w tablicy lub tablica może zostać ponownie przydzielona do rozszerzenia lub kurczy się, pozostawiając niepoprawne wskaźniki lub uchwyty komponentów. Jak radzisz sobie z tymi przypadkami, ponieważ często zdarza mi się, że chcę operować na transformacjach i innych komponentach w każdej ramce, a jeśli moje uchwyty lub wskaźniki są nieprawidłowe, dość niechlujne jest wyszukiwanie każdej klatki.

Po pierwsze, nie powiedziałbym, że w tym przypadku optymalizujesz zbyt wcześnie, w zależności od przypadku użycia. W każdym razie zadałeś interesujące pytanie i ponieważ mam z tym doświadczenie, zważę się. Spróbuję wyjaśnić, jak skończyłem robić rzeczy i co znalazłem po drodze.

• Każda jednostka zawiera wektor ogólnych uchwytów komponentów, które mogą reprezentować dowolny typ.
• Każdy uchwyt komponentu można wyrenderować, aby uzyskać surowy wskaźnik T *. * Zobacz poniżej.
• Każdy typ komponentu ma własną pulę, ciągły blok pamięci (w moim przypadku stały rozmiar).

Należy zauważyć, że nie, nie zawsze będziesz mógł po prostu przejść przez pulę komponentów i zrobić idealną, czystą rzecz. Jak już powiedziano, istnieją nieuniknione połączenia między komponentami, w których naprawdę trzeba przetwarzać rzeczy encji naraz.

Są jednak przypadki (jak odkryłem), w których można dosłownie napisać pętlę for dla określonego typu komponentu i doskonale wykorzystać linie pamięci podręcznej procesora. Dla tych, którzy nie są świadomi lub chcą wiedzieć więcej, spójrz na https://en.wikipedia.org/wiki/Locality_of_reference . Z tej samej uwagi, jeśli to możliwe, staraj się, aby rozmiar komponentu był mniejszy lub równy rozmiarowi linii bufora procesora. Mój rozmiar linii to 64 bajty, co moim zdaniem jest powszechne.

W moim przypadku wysiłek wdrożenia systemu był tego wart. Widziałem widoczne wzrosty wydajności (oczywiście profilowane). Musisz sam zdecydować, czy to dobry pomysł. Największy wzrost wydajności widziałem w ponad 1000 podmiotów.

Inną rzeczą, o którą chciałem zapytać, jest to, w jaki sposób należy zachować odniesienia do komponentów lub encji, ponieważ sama natura tego, jak komponenty są układane w pamięci, mogą łatwo zmieniać pozycje w tablicy lub tablica może zostać ponownie przydzielona do rozszerzenia lub kurczy się, pozostawiając niepoprawne wskaźniki lub uchwyty komponentów. Jak radzisz sobie z tymi przypadkami, ponieważ często zdarza mi się, że chcę operować na transformacjach i innych komponentach w każdej ramce, a jeśli moje uchwyty lub wskaźniki są nieprawidłowe, dość niechlujne jest wyszukiwanie każdej klatki.

Rozwiązałem również ten problem osobiście. Skończyło się na tym, że mam system, w którym:

• Każdy uchwyt komponentu zawiera odniesienie do indeksu puli
• Kiedy składnik jest „usuwany” lub „usuwany” z puli, ostatni komponent w tej puli jest przenoszony (dosłownie za pomocą std :: move) do wolnej lokalizacji lub żaden, jeśli właśnie usunięto ostatni komponent.
• Kiedy następuje „zamiana”, mam wywołanie zwrotne, które powiadamia wszystkich słuchaczy, aby mogli zaktualizować dowolne konkretne wskaźniki (np. T *).

* Odkryłem, że próba zawsze wyłączania uchwytów komponentu w czasie wykonywania w niektórych sekcjach kodu o dużym użyciu z liczbą podmiotów, z którymi miałem do czynienia, była problemem wydajności. Z tego powodu utrzymuję teraz niektóre surowe wskaźniki T w kluczowych częściach wydajności mojego projektu, ale poza tym używam ogólnych uchwytów komponentów, które powinny być używane tam, gdzie to możliwe. Utrzymuję je ważne, jak wspomniano powyżej, dzięki systemowi oddzwaniania. Być może nie musisz iść tak daleko.

Przede wszystkim jednak po prostu spróbuj. Dopóki nie pojawi się scenariusz z prawdziwego świata, wszystko, co ktoś tu powie, jest tylko jednym ze sposobów robienia rzeczy, co może nie być dla ciebie odpowiednie.

To pomaga? Spróbuję wyjaśnić wszystko, co jest niejasne. Doceniane są również wszelkie poprawki.

Aby odpowiedzieć tylko na to:

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? Czy to problem, gdy iteruję w C ++ dwie różne ciągłe tablice i używam danych z obu w każdym cyklu?

Nie (przynajmniej niekoniecznie). Kontroler pamięci podręcznej powinien w większości przypadków być w stanie efektywnie radzić sobie z odczytem z więcej niż jednej ciągłej tablicy. Ważne jest, aby w miarę możliwości starać się uzyskać dostęp do każdej tablicy liniowo.

Aby to zademonstrować, napisałem mały test porównawczy (obowiązują zwykłe zastrzeżenia testowe).

Zaczynając od prostej struktury wektorowej:

struct float3 { float x, y, z; };

Odkryłem, że pętla sumująca każdy element z dwóch oddzielnych tablic i przechowująca wynik w trzecim działała dokładnie tak samo jak wersja, w której dane źródłowe były przeplatane w jednej tablicy, a wynik przechowywany w trzeciej. Stwierdziłem jednak, że jeśli przeplatałem wynik ze źródłem, wydajność ucierpiała (około 2 razy).

Jeśli uzyskałem dostęp do danych losowo, wydajność spadła 10–20.

Czasy (10 000 000 elementów)

dostęp liniowy

• osobne tablice 0,21 s
• przeplecione źródło 0,21s
• przeplecione źródło i wynik 0,48s

dostęp losowy (uncomment random_shuffle)

• osobne tablice 2.42s
• przeplecione źródło 4.43s
• przeplecione źródło i wynik 4.00s

Źródło (skompilowane z Visual Studio 2013):

#include <Windows.h>
#include <vector>
#include <algorithm>
#include <iostream>

struct float3 { float x, y, z; };

float3 operator+( float3 const &a, float3 const &b )
{
    return float3{ a.x + b.x, a.y + b.y, a.z + b.z };
}

struct Both { float3 a, b; };

struct All { float3 a, b, res; };


// A version without any indirection
void sum( float3 *a, float3 *b, float3 *res, int n )
{
    for( int i = 0; i < n; ++i )
        *res++ = *a++ + *b++;
}

void sum( float3 *a, float3 *b, float3 *res, int *index, int n )
{
    for( int i = 0; i < n; ++i, ++index )
        res[*index] = a[*index] + b[*index];
}

void sum( Both *both, float3 *res, int *index, int n )
{
    for( int i = 0; i < n; ++i, ++index )
        res[*index] = both[*index].a + both[*index].b;
}

void sum( All *all, int *index, int n )
{
    for( int i = 0; i < n; ++i, ++index )
        all[*index].res = all[*index].a + all[*index].b;
}

class PerformanceTimer
{
public:
    PerformanceTimer() { QueryPerformanceCounter( &start ); }
    double time()
    {
        LARGE_INTEGER now, freq;
        QueryPerformanceCounter( &now );
        QueryPerformanceFrequency( &freq );
        return double( now.QuadPart - start.QuadPart ) / double( freq.QuadPart );
    }
private:
    LARGE_INTEGER start;
};

int main( int argc, char* argv[] )
{
    const int count = 10000000;

    std::vector< float3 > a( count, float3{ 1.f, 2.f, 3.f } );
    std::vector< float3 > b( count, float3{ 1.f, 2.f, 3.f } );
    std::vector< float3 > res( count );

    std::vector< All > all( count, All{ { 1.f, 2.f, 3.f }, { 1.f, 2.f, 3.f }, { 1.f, 2.f, 3.f } } );
    std::vector< Both > both( count, Both{ { 1.f, 2.f, 3.f }, { 1.f, 2.f, 3.f } } );

    std::vector< int > index( count );
    int n = 0;
    std::generate( index.begin(), index.end(), [&]{ return n++; } );
    //std::random_shuffle( index.begin(), index.end() );

    PerformanceTimer timer;
    // uncomment version to test
    //sum( &a[0], &b[0], &res[0], &index[0], count );
    //sum( &both[0], &res[0], &index[0], count );
    //sum( &all[0], &index[0], count );
    std::cout << timer.time();
    return 0;
}

Krótka odpowiedź: profil następnie zoptymalizuj.

Długa odpowiedź:

Ale kiedy mam do iteracji tablice komponentów, aby coś z nimi zrobić z systemu w rzeczywistej implementacji rozgrywki, zauważam, że prawie zawsze pracuję z dwoma lub więcej typami komponentów jednocześnie.

Czy to problem, gdy iteruję w C ++ dwie różne ciągłe tablice i używam danych z obu w każdym cyklu?

C ++ nie ponosi odpowiedzialności za pomyłki w pamięci podręcznej, ponieważ dotyczy dowolnego języka programowania. Ma to związek z tym, jak działa nowoczesna architektura procesora.

Twój problem może być dobrym przykładem tego, co można nazwać optymalizacją przedwczesną .

Moim zdaniem zbyt wcześnie zoptymalizowałeś się pod kątem lokalizacji pamięci podręcznej, nie patrząc na wzorce dostępu do pamięci programu. Ale większe pytanie brzmi, czy naprawdę potrzebujesz tego rodzaju (lokalizacji odniesienia) optymalizacji?

Agner's Fog sugeruje, że nie należy optymalizować przed profilowaniem aplikacji i / lub wiedzieć na pewno, gdzie są wąskie gardła. (To wszystko wspomniano w jego doskonałym przewodniku. Link poniżej)

Warto wiedzieć, jak zorganizowana jest pamięć podręczna, jeśli tworzysz programy, które mają struktury dużych danych z niesekwencyjnym dostępem i chcesz zapobiec rywalizacji o pamięć podręczną. Możesz pominąć tę sekcję, jeśli jesteś zadowolony z bardziej heurystycznych wskazówek.

Niestety, to, co zrobiłeś, faktycznie zakładało, że przydzielenie jednego typu komponentu na tablicę zapewni lepszą wydajność, podczas gdy w rzeczywistości mogłeś spowodować więcej braków pamięci podręcznej, a nawet rywalizacji o pamięć podręczną.

Zdecydowanie powinieneś spojrzeć na jego doskonały przewodnik po optymalizacji C ++ .

Inną rzeczą, o którą chciałem zapytać, jest to, w jaki sposób należy zachować odniesienia do komponentów lub jednostek, ponieważ sama natura tego, w jaki sposób komponenty są przechowywane w pamięci.

Osobiście przydzielę większość używanych komponentów razem w jednym bloku pamięci, więc mają one adresy „bliskie”. Na przykład tablica będzie wyglądać tak:

[{ID0 Transform Model PhysicsComp }{ID10 Transform Model PhysicsComp }{ID2 Transform Model PhysicsComp }..] a następnie zacznij optymalizację od tego miejsca, jeśli wydajność nie była „wystarczająco dobra”.

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.