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.