Czy warto używać puli cząstek w zarządzanych językach?

Zamierzałem zaimplementować pulę obiektów dla mojego systemu cząstek w Javie, a potem znalazłem to na Wikipedii. Mówiąc inaczej, mówi się, że pule obiektów nie są warte używania w językach zarządzanych, takich jak Java i C #, ponieważ przydziały zajmują zaledwie kilkadziesiąt operacji w porównaniu z setkami w językach niezarządzanych, takich jak C ++.

Ale jak wszyscy wiemy, każda instrukcja może zaszkodzić wydajności gry. Na przykład pula klientów w MMO: klienci nie będą wchodzić i wychodzić z puli zbyt szybko. Ale cząsteczki mogą się odnawiać dziesiątki razy w ciągu sekundy.

Pytanie brzmi: czy warto używać puli obiektów dla cząstek (szczególnie tych, które giną i szybko się odtwarzają) w zarządzanym języku?

Tak to jest.

Czas przydziału nie jest jedynym czynnikiem. Alokacja może mieć skutki uboczne, takie jak wywołanie przepustki do wyrzucania elementów bezużytecznych, co może nie tylko negatywnie wpłynąć na wydajność, ale może również wpłynąć nieprzewidywalnie na wydajność. Szczegóły tego będą zależeć od Twojego języka i wyboru platformy.

Pula również ogólnie poprawia lokalizację odniesienia dla obiektów w puli, na przykład poprzez trzymanie ich wszystkich w ciągłych tablicach. Może to poprawić wydajność podczas iteracji zawartości puli (lub przynajmniej jej części aktywnej), ponieważ następny obiekt w iteracji będzie zwykle znajdował się już w pamięci podręcznej danych.

Konwencjonalna mądrość polegająca na unikaniu przydziałów w najbardziej wewnętrznych pętlach gry nadal obowiązuje nawet w zarządzanych językach (szczególnie na przykład na 360, gdy używa się XNA). Przyczyny tego są nieco inne.

W przypadku Javy nie jest tak pomocne łączenie obiektów *, ponieważ pierwszy cykl GC dla obiektów, które wciąż istnieją, przetasuje je w pamięci, przenosząc je z przestrzeni „Eden” i potencjalnie tracąc lokalizację przestrzenną.

• W każdym języku zawsze przydatne jest łączenie złożonych zasobów, których zniszczenie i tworzenie podobnych wątków jest bardzo drogie. Można je połączyć, ponieważ koszty ich tworzenia i niszczenia nie mają prawie nic wspólnego z pamięcią związaną z uchwytem obiektu do zasobu. Cząstki nie pasują jednak do tej kategorii.

Java oferuje szybką alokację serii przy użyciu sekwencyjnego alokatora, gdy szybko alokujesz obiekty w przestrzeń Eden. Ta sekwencyjna strategia alokacji jest super szybka, szybsza niż mallocw C, ponieważ po prostu łączy pamięć już przydzieloną w prosty sekwencyjny sposób, ale ma tę wadę, że nie można zwolnić poszczególnych fragmentów pamięci. Jest to również przydatna sztuczka w C, jeśli chcesz po prostu szybko przydzielić rzeczy do, powiedzmy, struktury danych, w której nie musisz niczego z niej usuwać, po prostu dodaj wszystko, a następnie użyj go i wyrzuć to później.

Z powodu tego, że nie można uwolnić poszczególnych obiektów, Java GC, po pierwszym cyklu, skopiuje całą pamięć przydzieloną z przestrzeni Eden do nowych regionów pamięci za pomocą wolniejszego, bardziej ogólnego przeznaczenia, który pozwala pamięci na być uwolnionym w poszczególnych częściach w innym wątku. Następnie może odrzucić pamięć przydzieloną w przestrzeni Eden jako całości, nie zawracając sobie głowy pojedynczymi przedmiotami, które zostały skopiowane i żyją gdzie indziej w pamięci. Po pierwszym cyklu GC twoje obiekty mogą zostać rozproszone w pamięci.

Ponieważ obiekty mogą zostać sfragmentowane po pierwszym cyklu GC, korzyści płynące z łączenia obiektów, gdy jest to przede wszystkim ze względu na poprawę wzorców dostępu do pamięci (lokalizacja odniesienia) i zmniejszenie narzutu alokacji / dezalokacji, są w dużej mierze utracone ... tak bardzo że można uzyskać lepszą lokalizację odniesienia, zwykle przez cały czas przydzielając nowe cząstki i wykorzystując je, dopóki są jeszcze świeże w przestrzeni Edenu i zanim staną się „stare” i potencjalnie rozproszone w pamięci. Jednak to, co może być niezwykle pomocne (jak uzyskanie wydajności konkurującej z C w Javie), to unikanie używania obiektów dla cząstek i gromadzenie zwykłych, prymitywnych danych. Dla prostego przykładu zamiast:

class Particle
{
    public float x;
    public float y;
    public boolean alive;
}

Zrób coś takiego:

class Particles
{
    // X positions of all particles. Resize on demand using
    // 'java.util.Arrays.copyOf'. We do not use an ArrayList
    // since we want to work directly with contiguously arranged
    // primitive types for optimal memory access patterns instead 
    // of objects managed by GC.
    public float x[];

    // Y positions of all particles.
    public float y[];

    // Alive/dead status of all particles.
    public bool alive[];
}

Teraz, aby ponownie wykorzystać pamięć dla istniejących cząstek, możesz to zrobić:

class Particles
{
    // X positions of all particles.
    public float x[];

    // Y positions of all particles.
    public float y[];

    // Alive/dead status of all particles.
    public bool alive[];

    // Next free position of all particles.
    public int next_free[];

    // Index to first free particle available to reclaim
    // for insertion. A value of -1 means the list is empty.
    public int first_free;
}

Teraz, gdy nthcząstka umiera, aby umożliwić jej ponowne użycie, wypchnij ją na bezpłatną listę w następujący sposób:

alive[n] = false;
next_free[n] = first_free;
first_free = n;

Podczas dodawania nowej cząstki sprawdź, czy możesz otworzyć indeks z bezpłatnej listy:

if (first_free != -1)
{
     int index = first_free;

     // Pop the particle from the free list.
     first_free = next_free[first_free];

     // Overwrite the particle data:
     x[index] = px;
     y[index] = py;
     alive[index] = true;
     next_free[index] = -1;
}
else
{
     // If there are no particles in the free list
     // to overwrite, add new particle data to the arrays,
     // resizing them if needed.
}

Nie jest to najprzyjemniejszy kod do pracy, ale dzięki temu powinieneś być w stanie uzyskać bardzo szybkie symulacje cząstek z sekwencyjnym przetwarzaniem cząstek zawsze bardzo przyjaznym dla pamięci podręcznej, ponieważ wszystkie dane cząstek będą zawsze przechowywane w sposób ciągły. Ten typ repozytorium SoA zmniejsza również zużycie pamięci, ponieważ nie musimy się martwić o wypełnienie, metadane obiektu dla odbicia / dynamicznej wysyłki i dzieli gorące pola z dala od zimnych pól (na przykład niekoniecznie zajmujemy się danymi pola takie jak kolor cząsteczki podczas przejścia fizyki, więc marnowanie jej do linii pamięci podręcznej byłoby marnotrawstwem tylko po to, aby jej nie używać i eksmitować).

Aby ułatwić obsługę kodu, warto napisać własne podstawowe pojemniki o zmiennym rozmiarze, które przechowują tablice liczb zmiennoprzecinkowych, tablice liczb całkowitych i tablice logiczne. Znowu nie możesz używać ogólnych i ArrayListtutaj (przynajmniej od ostatniego sprawdzania), ponieważ wymaga to obiektów zarządzanych przez GC, a nie ciągłych prymitywnych danych. Chcemy użyć ciągłej tablicy int, np. Tablic nie zarządzanych przez GC, Integerktórych niekoniecznie będą ciągłe po opuszczeniu przestrzeni Eden.

W przypadku tablic typów pierwotnych zawsze gwarantuje się , że są one ciągłe, dzięki czemu uzyskuje się niezwykle pożądaną lokalizację odniesienia (w przypadku sekwencyjnego przetwarzania cząstek robi to różnicę) i wszystkie korzyści, jakie ma zapewnić pula obiektów. W przypadku tablicy obiektów jest ona w pewnym sensie analogiczna do tablicy wskaźników, które zaczynają wskazywać na obiekty w sposób ciągły, zakładając, że wszystkie zostały przydzielone naraz w przestrzeń Eden, ale po cyklu GC mogą wskazywać w całym miejsce w pamięci.