Az eddigieket összefoglalva azt már tudjuk, hogy:

• jobb lefoglalni egy nagyobb memóriaterületet egyben (fragmentation)
• jobb egymás utáni címekről olvasni adatot a memóriából (cache)
• az std::vector biztosítja a memóriában a folytonosságot, cserébe nincs stabil iterátor/pointer
• az std::list elemei a memóriában szétszórva helyezked(het)nek el, cserébe az elemek címe stabil

A legjobb tehát az lenne, ha nagyobb memóriadarabokat allokálnánk, azokon a területeken placement new segítségével hoznánk létre az objektumokat. Persze azt is szeretnénk, hogy stabil címei legyenek az elemeknek, hogy a komponens címét tárolhassuk, de az is jó lenne, ha az elemek egymás után helyezkednének el a memóriában.

Véleményem szerint két különböző megközelítés van. Igazából az a felhasználási módnak a kérdése, hogy melyik a jobb választás, minden esetre az egyik könnyebb (és hibatűrőbb), mint a másik. Mostantól "pool"-nak fogom nevezni a saját tárolónkat a könnyebb megkülönböztethetőség miatt. Kezdem a nehezebbel:

Első verzió

Tegyük fel, hogy a fent felsoroltak közül mindent teljesíteni szeretnénk. Magyarán, ha egy elemet eltávolítunk (természetesen ténylegesen nem szabadítjuk fel a memóriát, csak meghívjuk a destruktorát), akkor a helyére rakni kell egy másikat. Ezt az std::vector úgy oldja meg, hogy az utána lévő elemeket átmozgatja "eggyel előrébb".

Linear on the number of elements erased (destructions) plus the number of elements after the last element deleted (moving).

Utolsó elemet eltávolítani nyilván nem kihívás. Azonban, mivel mi nem egy ennyire általános tárolót szeretnénk írni, és tudjuk, hogy az elemek sorrendje nem számít, úgy nem kell az összes utána lévő elemet átmásolni, csupán egy cserét végrehajtani az utolsó elemmel, és eggyel csökkenteni a pool logikai méretét. Igenám, de ezáltal változik a cserélt elemnek a címe, így valamit még ki kell találnunk.

Csinálhatunk például olyasmit, mint amit az std::shared_ptr csinál: nem a raw pointert tárolnánk el az entityben, hanem egy saját típust. Hasonlóan a shared_ptr-hez mélyen legbelül egy pointert tárolna csupán, amely ezáltal minden egyes másolat esetén ugyan oda mutat. Ez lehet például csak egy egyszerű int*, amely megmondja, hogy a poolnak hányadik eleme is ez igazából.

Amikor a poolhoz hozzáadunk egy elemet, akkor csak létre kell hozni egy újat, abban nincs nagy trükk. Amikor viszont a poolból kiszedünk egy elemet - tehát azt megcseréljük az utolsóval - úgy a mi kis pointerünket is frissíteni kell. Pseudo-kód-jelleggel valami ilyesmi:

void Remove(T* obj)
{
    const uint32 lastId = size - 1;
    const uint32 id = FindId(obj);

    (*ptrs[lastId]->id) = id;
    ptrs.erase(ptrs.begin() + id);

    obj->~T();
    Swap(id, lastId);
    --size;
}

Innentől kezdve az entity pedig nem raw pointert tárolna, hanem a saját pointer típusunkat, amin keresztül le tudja kérni az elemet. Így a memória folytonos marad, és van egy stabil pointerünk is. Mi akkor a probléma?

Először is ez egy bonyolultabb implementáció: több mindenre kell figyelni, managelni. Nem is beszélve arról, hogy ha csak simán létrehozzuk a mi kis stabil pointerünkhöz tartozó objektumokat, akkor ismét sikerült az egyik problémát előidéznünk (fragmentation). A másik gond pedig az, hogy amikor el szeretnénk érni az adott objektumhoz tartozó komponens(eke)t, akkor ismét egy extra memóriaolvasásunk van (mint a legeslegelső implenentációnál), hiszen először a pointerünk által tárolt adatot dereferáljuk (magyarán odaugrunk a memóriában, és kiolvassuk az adatot), majd utána ugrunk a pool tömbjének az adott elemére. Az pedig, hogy egy adott objektum komponensét elérjük nem feltétlen egy ritka esemény: gondoljunk például a Unity MonoBehaviour osztályára. Ez tulajdonképpen a user-defined script, amely többek között vezérli/módosítja a hozzá tartozó objektum többi komponensét.

Az pedig már csak hab a tortán, hogy nyitottabb a programozó tévedésre. Mivel a stabil pointerünknek lennie kell olyan operátorának, amelyen keresztül elérjük a tényleges adatot (magyarán visszaad egy T*-ot), így ez kijátszható. Persze a programozó más módon is tökön tudja magát lőni, ha akarja, ez inkább csak olyan apróbetűs megjegyzés. :)

// normál használat
StablePtr<Transform> ptr = object->GetComponent<Transform>();
// öntökönlövés
Transform* t = ptr.operator->();
// vagy
Transform* t = &ptr.operator*();

Tehát ezzel a megközelítéssel megkaptuk a várt folytonos elhelyezkedést a memóriában, de az egész megközelítés felvet néhány további problémát, amelyet meg kell(ene) oldanunk (újabb fragmentation, extra memória-hivatkozás). Személy szerint úgy döntöttem, hogy részben feladom a folytonosságot, és ezzel ki is küszöböltem a többi problémát, amelyet az előző módszer generált.

Második verzió

Ha nem kell, hogy az elemek között ne legyen lyuk, akkor nem kell túl sokat trükköznünk, csupán valahogy számon kell tartanunk azt, hogy hol vannak a szabad helyek. Ez azért is kell, hogy amikor végigiterálunk az elemeken, akkor a nem létező objektumokkal ne babráljunk, de főleg azért, hogy tudjuk, hogy hova hozhatunk létre újabb objektumokat.

Először csináltam egy vector+list ötvözetet, azaz az elemek egy mindkét irányban bejárható láncot (is) alkottak. Ezeket a prev és next pointereket természetesen új elem beszúrásakor és eltávolításakor is frissíteni kellett, viszont általuk a végigiterálás könnyű volt. Azt tapasztaltam a kezdeti mérések során, hogy ez az extra munka nem feltétlen éri meg, de természetesen részletesebb teszteket fogok futtatni, és újra át fogom gondolni ezt a megközelítést, mert a szívem még mindig ebbe az irányba húz. No persze azt is hozzá kell tenni, hogy az elemenként 2 extra pointer (lehetne mondjuk id is) minimum 8 byte-al növelik a memóriaszükségletet, persze ez talán elhanyagolható, ha nem olyan eszközre fejleszt az ember.

A következő (jelenleg aktív, de fejlesztés alatt álló) megoldás egy sokkal egyszerűbb megközelítést választott: szimplán van egy flag, amely jelzi, hogy az adott elem "él-e", vagy már megsemmisült. Továbbá a gyors beszúrás érdekében egy egyszerű "láncolt listát" is kezelek. Ehhez jelenleg a lehető legegyszerűbb megoldást választottam: van egy id, amely jelzi az "első" szabad elem helyét, továbbá minden egyes elem jelzi a "következő" szabad elem helyét. Azért tettem idézőjelbe ezeket a szavakat, mert a "következő" szabad nem feltétlen az "előző" után van a memóriában, mutatom miért:

Element& element = elements[id];
element.MarkEmpty();
element.nextEmpty = firstEmpty;
firstEmpty = id;

Tekintsük az alábbi példát egy 10 elemű pool esetén, ahol az x-ek jelölik a foglalt elemeket, a ^ pedig a "firstEmpty"-t. Először is távolítsunk el elemeket az adott indexeken:

xxxxxxxxxx
          ^

remove(3)
xxx-xxxxxx
   ^
   
remove(8)
xxx-xxxx-x
        ^
        
remove(5)
xxx-x-xx-x
     ^
     
remove(4)
xxx---xx-x
    ^

Ezek után a láncolás miatt, ha újra hozzáadunk elemeket, akkor azok a következő helyeken (ebben a sorrendben) fognak létrejönni (ezeket most "o"-vel jelölöm a megkülönböztethetőség miatt), mivel szimplán követjük a szabad elemek láncolatát:

add()
xxx-o-xx-x
    ^

add()
xxx-ooxx-x
     ^
     
add()
xxx-ooxxox
        ^
        
add()
xxxoooxxox
   ^

Látszik, hogy nagy elemszám esetén ez igencsak lyukacsossá teheti a poolt, ha az eltávolítás+hozzáadás egy megfelelően gyakori esemény. Javíthat rajta az, amelyet korábban már megcsináltam (de a vectorral való sebesség-összehasonlítás első fordulójára kiszedtem), hogy ha nem egy láncolt listát építünk a szabad elemekből, hanem egy külön vectorunk van, amely egy bizonyos sorrendben tárolja az elemeket.

Magyarán, ha van egy rendezett tömbünk, amelyben az utolsó elem a legkisebb olyan index, amely egy szabad helyre mutat, akkor újabb elemek hozzáadásakor mindig sorban "betömködjük" a lyukakat, és nem össze-vissza (pontosabban az eltávolítás sorrendjével ellentétesen) dobálnánk bele az elemeket a poolba. Ez annyira nem vészes megközelítés, hiszen feltehetjük, hogy az eltávolítás lehet egy lassabb művelet, amely még így is csak O(log n) lenne, hiszen rendezett tömbben lehet bináris keresést csinálni.

void Remove(...)
{
    id = FindId(...);
    
    // ...
    
    // szeretnénk a megfelelő pozícióra tenni az indexet
    // így a "freeList" fordított sorrendben tárolja a szabad elemek indexeit

    // O(log n)
    FreeList::iterator it = std::lower_bound(freeList.begin(), freeList.end(), id,
        [](const uint16 lhs, const uint16 rhs) { return (rhs < lhs); });
    freeList.insert(it, id);
}

void Add(...)
{
    // ilyenkor pedig egy O(1) idejű művelet szükséges csupán

    firstFree = freeList.back();
    freeList.pop_back();
    
    // ...
}

Természetesen mindennek ára van: sosem lesz olyan gyors, mint egy vector, de speciálisabb is annál, hiszen stabil pointereket biztosít, amely a jelenlegi designban elengedhetetlen. Amennyiben félre tudjuk tenni a stabilitást, úgy a legjobb választás (nagyjából minden esetben) a vector, még ha az elemek másolásával is jár.

Az előző bejegyzésben kiderült, hogy már majdnem jó az, ha a komponenseket a system, vagy a system manager hozza létre, és tárolja, de a memory fragmentation problémája (továbbra is) fennáll. Emellett érdemes megemlíteni a cache-friendly kód fogalmát.

A memória elérése alapvetően lassú, így hiába írnánk gyors algoritmust, ha a processzoridő nagy része idle, mert az adatra várunk, hogy megérkezzen. Tudjuk, hogy a processzornak vannak regiszterei, de ezek alapvetően drágák, és igen kicsik, cserébe piszok gyorsak. Egy jó ideje már van ún. cache memory, ami árban és sebességben is a register és a main memory között van. A cache-ből nagyságrendekkel gyorsabb a kiolvasás, mint a fő memóriából, így egy cache-friendly megközelítés sokat gyorsíthat a kódon.

Tehát az össze-vissza dinamikus memóriafoglalás nem csak a "töredezettség" miatt problémás, hanem a cache szempontjából sem túl előnyös. Általában egy memóriaolvasáskor nem csak az adott méretű területet olvassa ki, hanem annál többet, így közvetlen a (cím+méret) utáni memóriaelérés "ingyen" van. Tehát, ha az adataink a memóriában egymást követik, az azokon való "végigiterálás" gyorsabb, mintha össze-vissza ugrálnánk a memóriában. Azaz az sem mindegy, hogy milyen adatszerkezetben tároljuk az adatainkat.

Tipikus példaként az std::vector vs std::list párost szokták felhozni.

A vector tulajdonképpen egy tömb, amelynek dinamikusan változhat a mérete. Azonban, ha növekszik a szükséges méret (például eddig maximum 4 elemet tudott tárolni, de hozzá szeretnénk adni egy újabbat), akkor újra kell foglalni a tömböt, és átmásolni az adatokat az új tömbbe. Hasonlóan, ha egy elemet eltávolítunk a vector közepéről, akkor az azt követő elemeket át kell helyezni/másolni eggyel "előrébb", ezzel biztosítva a folytonosságot a memóriában.

Ezzel szemben a listába való beszúrás és törlés bármely pozícióban konstans idejű, hiszen csak néhány pointert kell beállítani. Cserébe a listának az elemei a memóriában "random helyeken" lesznek, így a listán való végigiterálás kevésbé hatékony (sok cache miss).

Ezen szempontok mellett egy harmadik igen fontos különbség is van a kettő között, mégpedig a pointer/reference/iterator stabilitás.

Ha egy listába beszúrunk egy elemet, akkor annak a címe érvényes marad egészen addig, amíg az adott elemet el nem távolítjuk a listából, függetlenül attól, hogy másik elemet hozzáadtunk vagy eltávolítottunk. Ez pedig nyilván abból adódik, hogy a lista elemei egymástól függetlenek.

Azonban a vector ezt nem tudja, hiszen a belső tömb újrafoglalásakor is és egy adott elem eltávolításakor (azaz a többi mozgatásakor) is változik az eddigi elemeknek a címe. A következő egyszerű mintakódban a "belső tömbre" többször hivatkozok, ezalatt a vectornak a saját belső adatszerkezetére gondolok (ami tulajdonképpen egy tömb):

std::vector<int> vec;
// lekérjük, hogy a belső tömb maximum hány elemet tud tárolni
size_t currMax = vec.capacity();
// átméretezzük a vectort, hogy maximálisan kitöltse a belső tömböt
vec.resize(currMax);

// eltároljuk az első elemre mutató pointert
int* p = &vec[0];

// ezek után, ha beszúrunk egy elemet, akkor biztos,
// hogy újra kell allokálnia a belső tömböt
vec.push_back(0);

// a vector első elemének a címe nem egyezik meg az eltárolt címmel: &vec[0] != p
// emellett az előző belső tömb már fel lett szabadítva
// tehát, ha megpróbáljuk dereferálni  a pointert, simán crashelhet a program
std::cout << *p;

Ezeket az információkat egyébként megtudhatjuk a megfelelő oldalt böngészve. Ha megnézzük például a vectornak a push_back és erase függvényeit, és kicsit lentebb tekerünk, akkor láthatjuk a Complexity, Iterator validity és Data races részeket, amelyek általában igen pontosan ismertetik ezeket a tényezőket. A push_backnél például azt írják, hogy realloc esetén (amely például a belső tömb növekedésekor történik) az iterátorok és pointerek invaliddá válnak.

If a reallocation happens, all iterators, pointers and references related to the container are invalidated.

Tehát vagy feladjuk a pointer stabilitást (azaz a GameObject osztályunk nem tud simán pointereket tárolni a komponensekre), vagy a memória-folytonosságot.

Vagy trükközünk egy picit. Folytatás később... :)

Egy ECS-ben fontos, hogy hol és hogyan tároljuk a komponenseket, főleg, ha játékokról van szó, ahol fontos a sebesség.

Az első megközelítés

Az entity-component kapcsolat nagy vonalakban nézve annyit mond, hogy egy entitást a komponensei határoznak meg, azaz maga az entity egy buta objektum, ami a komponenseit "tárolja". Gondoljunk a Unity GameObject osztályára: adott egy objektum, le tudjuk kérni a hozzá tartozó komponenseket - többek között - a GetComponent függvényével.

Tekintsük általánosságban a következő, nagyon egyszerű komponens osztály(oka)t:

class Component
{
public:
	Component(GameObject* obj) : object(obj) { }
	virtual ~Component() { }
	
protected:
	GameObject* const object;
};

class Transform : public Component { /* ... */ }
class Renderer : public Component { /* ... */ }
// ...

 Ekkor, ha azt mondjuk, hogy az entity tárolja a komponenseket, akkor az valahogy így néz ki:

class GameObject
{
public:
	template <class T, typename... Args>
	T* Add(Args&&... args)
	{
		// static_assert: base_of<Component, T>

		T* result = new T(this, std::forward<Args>(args)...);
		components.push_back(result);
		return result;
	}

private:
	typedef std::vector<Component*> Components;
	
	Components components;
};

Mi is a probléma ezzel? Az objektumtól le tudjuk kérni a hozzá tartozó komponenseket, szóval mindenki boldog. Pontosabban csak egy valaki boldog, mégpedig a komponenst lekérdező fél, sajnos senki más nem igazán.

A komponenseken való végigiterálás egy igen gyakori jelenség futás közben: a mozgó objektumoknak ki kell számolni a world mátrixát, ütközést kell számolni a fizikai komponensekkel, stb. Azonban, ha az entitás tárolja a komponenseket (főleg ilyen általános módon), akkor az iterálás igen problémás. Minden objektumon végig kell iterálni, le kell kérdezni az adott típusú komponensét (pl. Transform), és azon elvégezni a műveleteket.

Egy kicsivel jobb, ha az objektumok néhány előre definiált, jól ismert komponenst külön tárolnak, és csak a user-defined komponenseket tárolják egy ilyen általános tárolóban, valahogy így:

Transform* transform;
Renderer* renderer;
Components otherComponents;

Ekkor az adott típusú built-in komponens elérése már gyorsabb, de továbbra is végig kell iterálni az összes objektumon, és azon keresztül lekérni az adott komponenst. Magyarul a memóriában oda kell ugrani az objektum címére, kiolvasni a komponens címét, majd odaugrani a memóriában. Ráadásul le kell ellenőriznünk, hogy van-e ilyen komponense az adott objektumnak. Ez úgy nem tűnik annyira hatékonynak.

Egy kicsit jobb

Tegyük félre, hogy az entitás hozza létre a komponenseket, szimplán csak tároljon egy pointert. De akkor ki hozza létre és tárolja magát a komponenst? Egyszerű a válasz: az adott system, vagy akár még egy szinttel feljebb, a systemeket vezérlő manager/system.

A system egy olyan osztály, amely egy adott tevékenységet végez, általában egy típusú komponenshez tartozik. Például a TransformSystem az objektumok transzformálásáért (térbeli elhelyezéséért) felel, és a Transform típusú komponenseket használja. A PhysicSystem a fizikához használatos komponens(eke)t, és így tovább. Természetesen vannak olyan esetek is, amikor egy systemnek többféle komponensre is szüksége van, például a RendererSystem: szüksége van az objektumok térbeli elhelyezkedésére (world mátrix) és magára a Renderer komponensre, amely a kirajzolandó dolgokat tárolja.

Tehát a komponensek létrehozása egy másik szintre kerül. Személy szerint azt a megközelítést választottam, hogy a Scene tárolja a komponenseket, a System pedig csak egy referenciát kap a megfelelő komponens listára/listákra.

class GameObject
{
public:
	void StoreComponent(Component* component) { components.push_back(component); }

private:
	typedef std::vector<Component*> Components;
	Components components;
};

class Scene
{
public:
	template <class T, typename... Args>
	T* AddComponent(GameObject* object, Args&&... args)
	{
		// static_assert...

		T* result = new T(object, std::forward<Args>(args)...);

		object->StoreComponent(result);
		AddToPool<T>(result);

		return result;
	}
	
	void Update()
	{
		transformSystem->DoJob(transforms);
		// ...
	}

private:
	template <class T>
	using ComponentPool = std::vector<T>;
	
	ComponentPool<Transform*> transforms;
	ComponentPool<Renderer*> renderers;
	ComponentPool<Component*> otherComponents;
	// ...
	
	TransformSystem* transformSystem;
	RendererSystem* rendererSystem;
	// ...
	
	template <class T>
	void AddToPool(T* component) { otherComponents.push_back(component); }
	
	// specializations....

	template <>
	void AddToPool<Transform>(Transform* component) { transforms.push_back(component); }
	
	// ...
};

Mit is nyertünk ezzel? Komponensenként eggyel kevesebb memória-ugrást, nomeg ellenőriznünk sem kell, hogy van-e ilyen komponens vagy sem, hiszen ott van a listában, és kész. Mindezt azzal értük el, hogy nem az objektumokon kell végigiterálni, hanem az adott komponens listán.

Most már örülhetnénk, mert minden jó. Alapvetően igen, kivéve a szegény memóriát. Mivel heap alloc történik, így nem tudjuk pontosan, hogy a memóriában hol kapnak helyet a létrehozott komponensek. Ráadásul alapvetően a komponensek viszonylag kicsik, így könnyen előfordulhat, hogy a memóriában össze-vissza helyeken lesznek a komponenseink (ahol éppen helyet talált nekik az oprendszer). Miután a komponenseket felszabadítjuk, az általuk lefoglalt memória szabaddá válik. Azonban, ha sok ilyen kicsi memóriaterületet foglaltunk le "össze-vissza", akkor előfordulhat, hogy egy nagyobb allokáció nem fog sikerülni, mert nem maradt egyetlen egybefüggő memóriaterület.

Érdemes utánanézni a "memory fragmentation" fogalomnak. A linken található ábrán látható az előbbiekben tárgyalt probléma, amikor egy "közbezárt" memóriaterület felszabadul, a helyére nem foglalható egy annál nagyobb objektum.

Freed block B. Notice that the memory that B used cannot be included for an allocation larger than B's size.

PC-n ez nem okoz túl nagy gondot, ott a virtuális memória, meg eleve viszonylag nagy az elérhető RAM, de gondoljunk egy zárt platformra, bármely konzol, telefon vagy tablet. Ezeknek a memóriája véges, ráadásul abban sem vagyok biztos, hogy lenne (például) az xbox-nak virtuális memória-kezelése, hiszen - tudtommal - a HDD nem szükséges tartozéka. No persze PC-n sem elhanyagolható a probléma, az erőforrás-pazarlás sosem jó ötlet.

Mi a megoldás?

Saját memóriakezelés: foglaljunk le egy nagyobb egybefüggő területet előre, és placement new segítségével hozzuk létre az objektumokat. Bővebben később... :)