Autor Wątek: komponenty  (Przeczytany 7476 razy)

Offline albireo

  • Użytkownik

# Czerwiec 01, 2015, 15:58:59
@Xender - Hashmapa może też zamiast bezpośrednio dane trzymać indeks do tablicy z gęsto upakowanymi danymi (tylko jeśli występuje usuwanie to trzeba jakoś obsłużyć dziury).

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Xender

  • Użytkownik

# Czerwiec 01, 2015, 17:42:36
@up - może, aczkolwiek w tablicy z dziurami zawsze można zrobić recykling zwolnionych indeksów poprzez trzymanie tam linkedlisty wolnych indeksów.

Tylko, że to wszystko kombinowanie - hashmapa jest w std (unordered_map), a taką "tablicę z dziurami z linkedlistą wolnych miejsc w samych wolnych miejscach" trzeba by było pewnie napisać samemu (chyba, że Boost lub inna biblioteka ma takie coś, co byłoby na tyle generyczne, żeby dało się to zastosować).

Osobnym problemem jest usuwanie obiektów - trzeba pilnować, żeby ID do usuniętego obiektu nie żyły dłużej, niż wolne miejsce.
Przy przesyłaniu komunikatów z ID przez sieć może się to komplikować.

Gdy ID będzie wskazywać w wolne miejsce, zależnie od systemu, może da się to wykryć, natomiast, gdy miejsce zostanie przydzielone nowemu obiektowi, ID będzie błędnie wskazywać na nowy.
Jest to o wiele subtelniejsza odmiana klasycznego use-after-free.

Implementowanie ID jako "handle" z dodatkowymi bitami na np. informacje o typie obiektu i umieszczanie tam dodatkowych liczników może zmniejszyć prawdopodobieństwo kolizji, ale to może być też niedeterministyczne...

Offline kapustman

  • Użytkownik

# Czerwiec 01, 2015, 18:01:18
Chyba już ustaliliśmy, że OP to ciężki przypadek trolla optymalizacyjnego, który optymalizuje na ślepo bez profilera, bo coś mu się wydaje, i bardzo chce spierniczyć architekturę swojej aplikacji, przy okazji być może pogarszając wydajność, miast ją poprawić.

(/me na nadzieję, że OP się wkurzy i pójdzie po rozum do głowy, jak to przeczyta.)

Auć :)
Kajam się prochu i pyle i popiele. Nie mam zamiaru spierniczać architektury. Ani być trollem. Słucham, co robię źle.




Offline Oti

  • Użytkownik

  • +1
# Czerwiec 01, 2015, 19:18:09
Pisałem o tym o tu, może trochę rozszerzy horyzonty:
http://forum.warsztat.gd/index.php?topic=29928.msg337826#msg337826

Offline lethern

  • Użytkownik

# Czerwiec 01, 2015, 20:39:21
sidenote
To co Krzych zalinkował to bardzo zubożała wersja tego jak działają normalne wskaźniki (pewnie z bardziej kontrolowaną wydajnością gdy wykorzysta się prealokowania pamięci). Można powiedzieć że chodzi o coś podobnego, więc wersja z IDkami nie wydaje mi się tutaj w żadnym stopniu lepsza (oraz, dla problemu "dangling pointers", skoro "jakoś" musimy wiedzieć który ID jest martwy, to jednocześnie możemy tego użyć do wskaźników). Nie rozumiem co tu jest "rewolucyjnego"?
« Ostatnia zmiana: Czerwiec 01, 2015, 20:41:18 wysłana przez lethern »

Offline Xender

  • Użytkownik

  • +3
# Czerwiec 01, 2015, 20:44:14
Auć :)
Kajam się prochu i pyle i popiele. Nie mam zamiaru spierniczać architektury. Ani być trollem. Słucham, co robię źle.

Nie no, bez przesady z tym kajaniem.

Chodzi mi o to, że cache coherency jest fajne, optymalne użycie SSE jest fajnie, ale nie są to jedyne czynniki, które należy brać pod uwagę.

Jest jeszcze pamięć. Jeśli będziesz miał tablicę z dużą liczbą dziur, to może ucierpieć i zużycie pamięci, i cache coherency.

Jeśli zrobisz ściśnięte tablice i dodatkową tablicę lookupową dla handle/indexów per komponent, to dla każdego komponentu musisz robić osobny lookup. Lookupy odbijają się na dostępach do pamięci, czyli... cache coherency, o które właśnie próbujesz walczyć.

Ponadto, jak trzymasz tę nieszczęsną prędkość i przyspieszenie oddzielnie, to nie dość, że masz 2 lookupy zamiast jednego, to masz jeszcze ifa i 2 przypadki - na ruch jednostajny (bez przyspieszenia) i przyspieszony.
Tu wchodzi branch prediction.

I każdy z tych czynników można rozważać i pod niego optymalizować.
Problem jest taki, że optymalizacja 100% pod którykolwiek spowoduje raczej problemy w innych.

Więc trzeba optymalizować system jako całość, a nie tylko jeden jego aspekt.
A nie da się optymalizować systemu jako całości, nie mając istniejącego systemu i danych z profilera (już mniejsza o to, jakiego).

Fajnie byłoby mieć od razu sprawnie działający system, żeby nie trzeba go było potem optymalizować.
Niestety, dobre praktyki są albo ogólne (przeważnie dają dobre efekty, więc pewnie warto domyślnie się do nich stosować, ale nie dadzą konkretnej gwarancji wydajności), albo szczególne - do rozwiązywania konkretnych problemów (z cache coherency, szybkością samych obliczeń, branch prediction, synchronizacją wątków/zadań itp.).
Ciężko mówić o rozwiązywaniu konkretnych problemów, jak jeszcze nie wystąpiły, bo jest się dopiero w fazie projektowania systemu.


A gdzieś z boku patrzy na to wszystko czytelność/architektura kodu.
Kod optymalizowany pod szczególne przypadki przeważnie jest mniej generyczny i przeważnie mniej jasny.

A jeszcze do tego dochodzi identyfikacja wąskich gardeł (znów z profilerem), ale nie na poziomie mikro (cache, obliczenia czy branche), tylko makro (który system się dławi, procesor czy może GPU, a może jakaś funkcja robi mnóstwo operacji na stringach, które można by zastąpić albo zoptymalizować).

Żeby nie było, że sobie to ze stringami wymyśliłem:
https://fgiesen.wordpress.com/2013/02/17/optimizing-sw-occlusion-culling-index/
Ogólnie fajna historia optymalizacyjna, dobre do poczytania.


Tylko znowu, od czytania historii optymalizacyjnych gra się sama nie napisze. O tym też pamiętaj. :P

Offline ArekBal

  • Użytkownik

  • +1
# Czerwiec 01, 2015, 21:56:26
Ja nie mierzyłem, nie sprawdzałem...
Ale najprostszym i w imię DOD podejściem wydaje mi się trzymanie składników komponentów przez wartość wraz z id w vectorach.
Jeśli zależy nam na sprawnym wyszukiwaniu to trzymałbym(pilnował sortowania przy insertach i removach) jeszcze je posortowane po id i wybierał z pomocą binary search.
Starałbym się też nie ubijać bytów, elementów, tylko bym je deaktywował, a potem liniowo szukał pierwszej "dziury", bez listy łączonej bo to trochę słabe, chyba że upchamy do elementu jakieś metadane i potem z id czy z czegoś innego wyłowimy wskaźniki, ale to już hacki które bym sobie na koniec zostawił - czytaj: darował.
Oczywiście wszystko się skomplikuje przy np. dynamicznych komponentach, ale podstawowe wymagania toto spełni i potraktowałbym to jako punkt wyjścia.
« Ostatnia zmiana: Czerwiec 01, 2015, 22:05:03 wysłana przez ArekBal »

Offline kapustman

  • Użytkownik

# Czerwiec 02, 2015, 22:31:04
Cóż, ostatecznie raczej znowu skorzystam z hybrydy. Zamiast kilku tablic komponentów dla wszystkich obiektów, tworzę dla każdego obiektu oddzielne komponenty :
struct foo
{
     position* pos;
     velocity* vel;
};

struct bar
{
     position* pos;
     velocity* vel;
     AI* ai;
     aabb* box;
};

//itd.

Przy dezaktywowaniu "obiektu" zamieniam ostatni aktywny z dezaktywowanym, przez co nie ma żadnych dziur w tablicy.

Offline Xender

  • Użytkownik

# Czerwiec 03, 2015, 10:23:13
Jakoś trzymanie komponentów przez wskaźnik dziwnie wygląda.
W ECS AFAIK chodzi też o to, że jest to wszystko trzymane przez id i można dodawać komponenty do obiektu bez tworzenia nowych structów.

Jeśli same komponenty chcesz trzymać w vectorze, to odradzam wskaźniki, lepiej trzymać indeksy.
Deque może też być niegłupim kontenerem.

Offline Kos

  • Użytkownik
    • kos.gd

# Czerwiec 03, 2015, 10:26:28
Rozwińcie ECS?

Offline Xirdus

  • Redaktor

# Czerwiec 03, 2015, 12:34:26
struct foo
{
     position* pos;
     velocity* vel;
};

struct bar
{
     position* pos;
     velocity* vel;
     AI* ai;
     aabb* box;
};

//itd.
Masz osobny komponent na pozycję + prędkość i osobny na pozycję + prędkość + kolizje + AI? Będziesz robił osobne struktury na każdy zestaw danych które chcesz? To jest dokładne zaprzeczenie idei komponentów.

Rozwińcie ECS?
Entity Component System. Każdy ma własną definicję tego zwrotu.

Offline kapustman

  • Użytkownik

# Czerwiec 03, 2015, 15:03:21
To nie są komponenty, ani wskaźniki na komponenty. To jest SoA (structure of arrays). Dla każdego obiektu oddzielne struktura. Podam nieco uproszczony model:

const unsigned MAX_B = 5000;
const unsigned MAX_E = 100;

struct bullet
{
     position pos[MAX_B];
     velocity vel[MAX_B];
     aabb box[MAX_B];
};

struct enemy
{
     position pos[MAX_E];
     velocity vel[MAX_E];
     AI ai[MAX_E];
     aabb box[MAX_E];
};
//itd.

To hybryda DOD i OOP. Nie ma już uniwersalnych komponentów, każda grupa obiektów ma swoje oddzielne tablice komponentów. Nie ma problemów z dziurawą tablicą komponentów,ani szukaniem tych dziur. Nie potrzeba też żadnego mapowania indeksów.

Jak tworzę np. enemy, to zwracam indeks, który jest wspólny dla wszystkich komponentów.
« Ostatnia zmiana: Czerwiec 03, 2015, 18:27:26 wysłana przez kapustman »

Offline Xirdus

  • Redaktor

# Czerwiec 03, 2015, 18:36:43
To hybryda DOD i OOP.
Brzmi strasznie.

Nie ma już uniwersalnych komponentów, każda grupa obiektów ma swoje oddzielne tablice komponentów. Nie ma problemów z dziurawą tablicą komponentów,ani szukaniem tych dziur. Nie potrzeba też żadnego mapowania indeksów.
Ale jest problem z dodawaniem nowych typów. Musisz teraz mieć osobny kod przemieszczania kul, osobny kod przemieszczania gracza, osobny przeciwników, osobny obiektów otoczenia itd. I tak z każdą jedną pierdołą. Nie mówiąc już jak się namachasz z kolizjami... Bardzo złe rozwiązanie.

Offline kapustman

  • Użytkownik

# Czerwiec 03, 2015, 18:52:13
Ale jest problem z dodawaniem nowych typów. Musisz teraz mieć osobny kod przemieszczania kul, osobny kod przemieszczania gracza, osobny przeciwników, osobny obiektów otoczenia itd. I tak z każdą jedną pierdołą. Nie mówiąc już jak się namachasz z kolizjami... Bardzo złe rozwiązanie.

Jaki osobny kod? Jakie kolizje?
Kod pozostaje bez zmian, ja tylko odrobinę inaczej poukładałem dane. Zamiast przekazywania jednej wielkiej tablicy, przekazuję kilka mniejszych.


Offline Xirdus

  • Redaktor

# Czerwiec 03, 2015, 20:26:54
Jaki osobny kod? Jakie kolizje?
Wnioskując po tym, że masz typy "bullet" i "aabb", założyłem, że chcesz zrobić jakieś kolizje w swojej grze.