Dynamiczne przydzielanie pamięci i zarządzanie pamięcią

W przeciętnej grze na scenie znajdują się setki, a może tysiące obiektów. Czy całkowicie poprawne jest przydzielanie pamięci dla wszystkich obiektów, w tym strzałów z pistoletu (pocisków), dynamicznie za pomocą domyślnego new () ?

Czy powinienem utworzyć pulę pamięci do alokacji dynamicznej , czy nie trzeba się tym przejmować? Co jeśli platforma docelowa to urządzenia mobilne?

Czy w grze mobilnej potrzebny jest menedżer pamięci ? Dziękuję Ci.

Używany język: C ++; Obecnie opracowywany pod Windows, ale planowany późniejszy port.

W przeciętnej grze na scenie są setki, a może tysiące osób. Czy całkowicie poprawne jest przydzielanie pamięci dla wszystkich obiektów, w tym strzałów z pistoletu (pocisków), dynamicznie za pomocą domyślnego nowego ()?

To naprawdę zależy od tego, co rozumiesz przez „poprawne”. Jeśli weźmiesz ten termin dosłownie (i zignorujesz jakąkolwiek koncepcję poprawności dorozumianego projektu), to tak, jest to całkowicie akceptowalne. Twój program się skompiluje i będzie działał poprawnie.

Może działać niezadowalająco, ale nadal może być na tyle dobry, że może być dostarczalną, zabawną grą.

Czy powinienem utworzyć pulę pamięci do alokacji dynamicznej, czy też nie trzeba się tym przejmować? Co jeśli platforma docelowa to urządzenia mobilne?

Profil i zobacz. Na przykład w C ++ alokacja dynamiczna na stercie jest zwykle operacją „powolną” (polegającą na przejściu przez stertę w poszukiwaniu bloku o odpowiedniej wielkości). W języku C # jest to zwykle bardzo szybka operacja, ponieważ wymaga niewiele więcej niż przyrostu. Różne implementacje językowe mają różne cechy wydajnościowe w odniesieniu do alokacji pamięci, fragmentacji po wydaniu i tak dalej.

Wdrożenie systemu pul pamięci może z pewnością przynieść wzrost wydajności - a ponieważ systemy mobilne są zwykle słabsze w porównaniu do systemów stacjonarnych, możesz zauważyć większy zysk na konkretnej platformie mobilnej niż na komputerze stacjonarnym. Ale znowu musisz się sprofilować i sprawdzić - jeśli obecnie gra jest wolna, ale alokacja / zwolnienie pamięci nie pojawia się w narzędziu do profilowania jako gorący punkt, wdrażanie infrastruktury w celu optymalizacji alokacji pamięci i dostępu prawdopodobnie wygra ” Tobie dużo huk za złotówki.

Czy w grze mobilnej potrzebny jest menedżer pamięci? Dziękuję Ci.

Znowu profil i zobacz. Czy Twoja gra działa teraz dobrze? Wtedy nie musisz się martwić.

Całe to ostrzeżenie - odkładanie na bok dynamicznego przydzielania wszystkiego nie jest absolutnie konieczne i dlatego warto go unikać - zarówno ze względu na potencjalny wzrost wydajności, jak i alokację pamięci, którą należy śledzić i ostatecznie zwolnić oznacza, że ​​musisz go śledzić i ostatecznie go zwolnić, co może komplikować kod.

W szczególności w swoim oryginalnym przykładzie zacytowałeś „pociski”, które są często tworzone i niszczone - ponieważ wiele gier wymaga dużej ilości pocisków, a pociski poruszają się szybko, a tym samym szybko kończą swoje życie (i często gwałtownie!). W związku z tym wdrożenie dla nich alokatora puli i podobnych obiektów (takich jak cząstki w układzie cząstek) może zwykle przynieść wzrost wydajności i prawdopodobnie byłby pierwszym miejscem, w którym można zacząć korzystać z alokacji puli.

Nie jestem pewien, czy uważasz, że implementacja puli pamięci różni się od „menedżera pamięci” - pula pamięci jest stosunkowo dobrze zdefiniowaną koncepcją, więc mogę z całą pewnością stwierdzić, że może ona być korzystna, jeśli ją zaimplementujesz . „Menedżer pamięci” jest nieco bardziej niejasny pod względem odpowiedzialności, więc muszę powiedzieć, że to, czy ktoś jest wymagany, zależy od tego, co według niego zrobiłby „menedżer pamięci”.

Na przykład, jeśli uważasz menedżera pamięci za coś, co po prostu przechwytuje połączenia do nowego / usuń / wolny / malloc / cokolwiek i zapewnia diagnostykę, ile pamięci przydzielasz, co przeciekasz itp. - to może być przydatne narzędzie do gry, która jest w fazie rozwoju, aby pomóc w debugowaniu wycieków i dostrojeniu optymalnych rozmiarów puli pamięci itd.

Nie mam wiele do dodania do doskonałej odpowiedzi Josha, ale skomentuję to:

Czy powinienem utworzyć pulę pamięci do alokacji dynamicznej, czy też nie trzeba się tym przejmować?

Między pulami pamięci a wywołaniem newkażdej alokacji znajduje się środek . Na przykład możesz przydzielić określoną liczbę obiektów w tablicy, a następnie ustawić na nich flagę, aby później je „zniszczyć”. Gdy musisz przydzielić więcej, możesz zastąpić te zestawem zniszczonej flagi. Tego rodzaju rzecz jest tylko nieco bardziej złożona w użyciu niż nowa / usuń (ponieważ w tym celu byłyby 2 nowe funkcje), ale jest łatwa do napisania i może dać duże korzyści.

Czy całkowicie poprawne jest przydzielanie pamięci dla wszystkich obiektów, w tym strzałów z pistoletu (pocisków), dynamicznie za pomocą domyślnego new ()?

Nie, oczywiście nie. Brak alokacji pamięci jest poprawny dla wszystkich obiektów. operator new () służy do alokacji dynamicznej , to znaczy, że jest odpowiedni tylko wtedy, gdy potrzebujesz alokacji, aby była dynamiczna, ponieważ czas życia obiektu jest dynamiczny lub ponieważ typ obiektu jest dynamiczny. Jeśli typ i czas życia obiektu są znane statycznie, należy przydzielić go statycznie.

Oczywiście im więcej informacji na temat wzorców alokacji, tym szybciej można dokonać alokacji za pośrednictwem specjalistycznych alokatorów, takich jak pule obiektów. Są to jednak optymalizacje i powinieneś je robić tylko wtedy, gdy są niezbędne.

Coś w rodzaju powtórzenia sugestii Kylotana, ale zaleciłbym rozwiązanie tego na poziomie struktury danych, jeśli to możliwe, a nie na niższym poziomie alokatora, jeśli możesz pomóc.

Oto prosty przykład tego, jak można uniknąć Fooswielokrotnego przydzielania i zwalniania za pomocą tablicy z dziurami z połączonymi ze sobą elementami (rozwiązywanie tego na poziomie „kontenera” zamiast na poziomie „alokatora”):

struct FooNode
{
    explicit FooNode(const Foo& ielement): element(ielement), next(-1) {}

    // Stores a 'Foo'.
    Foo element;

    // Points to the next foo available; either the
    // next used foo or the next deleted foo. Can
    // use SoA and hoist this out if Foo doesn't 
    // have 32-bit alignment.
    int next;
};

struct Foos
{
    // Stores all the Foo nodes.
    vector<FooNode> nodes;

    // Points to the first used node.
    int first_node;

    // Points to the first free node.
    int free_node;

    Foos(): first_node(-1), free_node(-1)
    {
    }

    const FooNode& operator[](int n) const
    {
         return data[n];
    }

    void insert(const Foo& element)
    {
         int index = free_node;
         if (index != -1)
         {
              // If there's a free node available,
              // pop it from the free list, overwrite it,
              // and push it to the used list.
              free_node = data[index].next;
              data[index].next = first_node;
              data[index].element = element;
              first_node = index;
         }
         else
         {
              // If there's no free node available, add a 
              // new node and push it to the used list.
              FooNode new_node(element);
              new_node.next = first_node;
              first_node = data.size() - 1;
              data.push_back(new_node);
         }
    }

    void erase(int n)
    {
         // If the node being removed is the first used
         // node, pop it from the used list.
         if (first_node == n)
              first_node = data[n].next;

         // Push the node to the free list.
         data[n].next = free_node;
         free_node = n;
    }
};

Coś w tym celu: pojedynczo połączona lista indeksów z darmową listą. Łącza indeksu umożliwiają pomijanie usuniętych elementów, usuwanie elementów w stałym czasie, a także odzyskiwanie / ponowne wykorzystywanie / zastępowanie wolnych elementów z wstawianiem w stałym czasie. Aby wykonać iterację w strukturze, wykonaj następujące czynności:

for (int index = foos.first_node; index != -1; index = foos[index].next)
    // do something with foos[index]

I możesz uogólnić powyższy rodzaj struktury danych „połączonej tablicy otworów” za pomocą szablonów, umieszczenia nowego i ręcznego wywołania dtor, aby uniknąć wymogu przypisania kopii, sprawić, by wywoływał destruktory po usunięciu elementów, zapewnia iterator do przodu itp. I postanowiłem zachować przykład bardzo podobny do C, aby jaśniej zilustrować tę koncepcję, a także dlatego, że jestem bardzo leniwy.

To powiedziawszy, ta struktura ma tendencję do degradacji w lokalizacji przestrzennej po usunięciu i wstawieniu wielu rzeczy do / od środka. W tym momencie nextlinki mogą sprawić, że będziesz chodzić tam i z powrotem wzdłuż wektora, ponownie ładując dane wcześniej eksmitowane z linii pamięci podręcznej w ramach tego samego sekwencyjnego przechodzenia (jest to nieuniknione w przypadku dowolnej struktury danych lub alokatora, który umożliwia ciągłe usuwanie bez tasowania elementów podczas odzyskiwania odstępy od środka ze wstawianiem w czasie stałym i bez użycia czegoś takiego jak równoległy zestaw bitów lub removedflaga). Aby przywrócić łatwość obsługi pamięci podręcznej, możesz zaimplementować metodę kopiowania ctor i zamiany w następujący sposób:

Foos(const Foos& other)
{
    for (int index = other.first_node; index != -1; index = other[index].next)
        insert(foos[index].element);
}

void Foos::swap(Foos& other)
{
     nodes.swap(other.nodes):
     std::swap(first_node, other.first_node);
     std::swap(free_node, other.free_node);
}

// ... then just copy and swap:
Foos(foos).swap(foos);

Teraz nowa wersja jest znów przyjazna dla pamięci podręcznej, aby przejść. Inną metodą jest przechowywanie osobnej listy indeksów w strukturze i okresowe sortowanie. Innym jest użycie zestawu bitów do wskazania, jakie indeksy są używane. To zawsze będzie wymagać przejścia zestawu bitów w kolejności sekwencyjnej (aby to zrobić skutecznie, sprawdzaj 64 bity na raz, np. Przy użyciu FFS / FFZ). Zestaw bitów jest najbardziej wydajny i nieinwazyjny, wymagając tylko równoległego bitu na element, aby wskazać, które z nich są używane, a które są usuwane zamiast wymagać nextindeksów 32-bitowych , ale najbardziej czasochłonne, aby pisać dobrze (nie będzie bądź szybki na przejście, jeśli sprawdzasz jeden bit na raz - potrzebujesz FFS / FFZ, aby natychmiast znaleźć ustawiony lub nieuzbrojony bit wśród 32+ bitów, aby szybko określić zakres zajętych indeksów).

To połączone rozwiązanie jest na ogół najłatwiejsze do wdrożenia i nieinwazyjne (nie wymaga modyfikacji w Foocelu przechowywania niektórych removedflag), co jest pomocne, jeśli chcesz uogólnić ten kontener do pracy z dowolnym typem danych, jeśli nie przeszkadza ci to 32-bitowe narzut na element.

Czy powinienem utworzyć pulę pamięci do alokacji dynamicznej, czy też nie trzeba się tym przejmować? Co jeśli platforma docelowa to urządzenia mobilne?

potrzeba jest silnym słowem i jestem stronniczy w pracy w obszarach krytycznych pod względem wydajności, takich jak raytracing, przetwarzanie obrazu, symulacje cząstek i przetwarzanie siatki, ale przydzielanie i uwalnianie drobnych obiektów używanych do bardzo lekkiego przetwarzania, takich jak pociski, jest stosunkowo bardzo drogie. oraz cząstki indywidualnie w stosunku do ogólnego przeznaczenia, zmiennej wielkości alokatora pamięci. Biorąc pod uwagę, że powinieneś być w stanie uogólnić powyższą strukturę danych w ciągu jednego lub dwóch dni, aby przechowywać wszystko, co chcesz, myślę, że warto byłoby wymienić takie rozwiązanie, aby całkowicie wyeliminować takie koszty alokacji / dezalokacji stosu za każdą drobną rzecz. Oprócz zmniejszenia kosztów alokacji / dezalokacji, uzyskuje się lepszą lokalizację referencji w porównaniu z wynikami (mniej błędów pamięci podręcznej i błędów strony, tj.).

Jeśli chodzi o to, co Josh wspomniał o GC, nie badałem implementacji GC w C # tak dokładnie jak Java, ale alokatory GC często mają wstępny przydziałto bardzo szybko, ponieważ używa sekwencyjnego alokatora, który nie może zwolnić pamięci od środka (prawie jak stos, nie można usunąć rzeczy ze środka). Następnie opłaca się za drogie koszty faktyczne umożliwienie usuwania pojedynczych obiektów w osobnym wątku poprzez kopiowanie pamięci i czyszczenie poprzednio przydzielonej pamięci jako całości (jak zniszczenie całego stosu jednocześnie podczas kopiowania danych do czegoś bardziej podobnego do struktury powiązanej), ale ponieważ odbywa się to w osobnym wątku, niekoniecznie tak bardzo blokuje wątki aplikacji. Niesie to jednak bardzo znaczący ukryty koszt dodatkowego poziomu pośredniego i ogólnej utraty LOR po początkowym cyklu GC. Jest to kolejna strategia przyspieszenia alokacji - obniż koszt w wątku wywołującym, a następnie wykonaj kosztowną pracę w innym. W tym celu potrzebujesz dwóch poziomów pośrednich, aby odwoływać się do twoich obiektów zamiast jednego, ponieważ w końcu zostaną one potasowane w pamięci między czasem początkowo przydzielonym a po pierwszym cyklu.

Inną strategią w podobnym stylu, która jest nieco łatwiejsza do zastosowania w C ++, jest po prostu nie zawracaj sobie głowy uwalnianiem obiektów w głównych wątkach. Po prostu dodawanie i dodawanie i dodawanie na końcu struktury danych, co nie pozwala na usuwanie rzeczy ze środka. Zaznacz jednak rzeczy, które należy usunąć. Wówczas osobny wątek mógłby zająć się kosztowną pracą tworzenia nowej struktury danych bez usuniętych elementów, a następnie atomową zamianą nowej na starą, np. Znaczną część kosztów zarówno alokacji, jak i zwolnienia elementów można przenieść na oddzielny wątek, jeśli możesz założyć, że żądanie usunięcia elementu nie musi być natychmiast spełnione. To nie tylko sprawia, że ​​uwolnienie jest tańsze, jeśli chodzi o twoje wątki, ale także sprawia, że ​​alokacja jest tańsza, ponieważ możesz użyć znacznie prostszej i głupszej struktury danych, która nigdy nie musi obsługiwać przypadków usuwania od środka. To jest jak pojemnik, który potrzebuje tylkopush_backfunkcja wstawiania, clearfunkcja usuwania wszystkich elementów i swapzamiany zawartości na nowy, kompaktowy pojemnik z wyłączeniem usuniętych elementów; to tyle, jeśli chodzi o mutowanie.