Blue Moon Games

Stable pointer dynamic array - part 2

2016. november 03.

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... :)

A bejegyzés trackback címe:

https://bluemoongames.blog.hu/api/trackback/id/tr2811927197

Kommentek:

A hozzászólások a vonatkozó jogszabályok  értelmében felhasználói tartalomnak minősülnek, értük a szolgáltatás technikai  üzemeltetője semmilyen felelősséget nem vállal, azokat nem ellenőrzi. Kifogás esetén forduljon a blog szerkesztőjéhez. Részletek a  Felhasználási feltételekben és az adatvédelmi tájékoztatóban.

Nincsenek hozzászólások.
süti beállítások módosítása