C# tömbök mesteri szinten (2) ~ Primusz Péter

Egy picit még elidőzünk a múlt héten felvetett téma mellett. Nyilvánvaló, hogy a tömbök, főleg ha ciklusokon belül használjuk őket néha igen komoly teljesítményproblémát jelenthetnek, melyek egy része magától értetődő, más része rejtett. Az alábbiakban egy-két jellemző példát lehet majd látni erre.
Tételezzük fel, hogy egy táblázatot alkotó "jagged" tömb minden egyes sora kb. 4000 bájt méretű (figyelem, a méret a lényeg!). Ha ez a táblázat túl sok sorból áll, akkor minden esetben, amikor egy eltérő sor adataihoz hozzá szeretnénk férni, akkor a tábla/tömb és az állandó memória lapméretek miatt (mondjuk 4 KB) az operációs rendszernek úgynevezett memória-lapváltást kell végrehajtania. Másképp mondva hozzá kell férnie a tömbelem másik lapon lévő adataihoz. Vagyis a lenti példa szerint a belső ciklus miatt, minden tömbelemhez való hozzáférés újabb és újabb plusz memóriaműveletet (a már említett lapváltást) generál. Példa:


for (int column = 0; column < MAX_COLUMNS; column++)
{
  for (int row = 0; row < MAX_ROWS; row++)
  {
    table[row][column] = BlankTableElement();
  }
}

A fenti példa szerint tehát MAX_COLUMNS * MAX_ROWS darab memória-lapváltás történik, melyet mindenképp jó lenne kiküszöbölni, és erre az alábbi lehetőség áll a rendelkezésünkre.


for (int row = 0; row < MAX_ROWS; row++)
{
  for (int column = 0; column < MAX_COLUMNS; column++)
  {
     table[row][column] = BlankTableElement();
  }
}

Egyszerűen megcserélődött a két ciklus, vagyis ami eddig kívül volt az belül lesz és fordítva. Ebben az esetben is lesz memória-lapváltás, de már csak MAX_ROWS és nem MAX_COLUMNS * MAX_ROWS esetben. A teljesítménynövekedés feladattól és környezettől függően változhat, de bizonyos esetben, pl.: a második példa ciklusa akár 1000x előbb is befejeződhet, mint az első. Ha már a tömböknél tartunk... Az alábbi példa igaz, hogy a kód olvashatóságát rontja egy kissé, de teljesítmény szempontból, bizonyos helyzetekben rendkívül hatékony tud lenni (ez az úgynevezett „unrolling” művelet). Példa:


i = 0;
while (i < count)
{
  a[i] = i;
  i = i + 1;
}

Ez egy egyszerű ciklus volt, ami egy „a” numerikus tömböt feltöltött az „i” index értékével. A fenti megoldás helyett, amennyiben lehetséges (nyilván nem mindig), legyen inkább egy másik megoldás…


i = 0;
while (i < count - 1)
{
  a[i] = i;
  a[i + 1] = i + 1;
  i = i + 2;
}
if (i == count)
{
  a[count - 1] = count - 1;
}

A lényeg az, hogy a tömbön belül nem egyesével, hanem fura módon kettesével léptetjük az „i” indexet, és minden iterációnál kitöltjük az aktuális, valamint az aktuális i + 1 tömbelemet (vagy más feladat esetén végrehajtunk valami más tömbműveletet). Páratlan számú iteráció esetén az utolsó elem kitöltésére csak a ciklus után, külön kerülhet sor. A teljesítménynövekedés környezettől függően változhat, ezért az alkalmazása előtt méréseket kell végezni. Ahol a teljesítmény különösen kritikus és fontos, ott a .NET menedzselt kód által nyújtott plusz szolgáltatások kikerülhetők, azaz elérhető, hogy a tömbök adata ne a referencia típusokra jellemző menedzselt halmon (heap), hanem az annál jóval gyorsabban hozzáférhető, és a szemégyűjtő Garbage Collector által nem inzultált vermen (stack) tárolódjon. Az imént említett tömbhasználat felturbozásához a stackalloc nevű C# utasítást kell használni (fordításkor a /unsafe opció szükséges). Ez a módszer csak egy dimenziós, 0 bázisú, érték típusú elemeket tartalmazó tömböknél működhet. Amikor a stackalloc használatban van, akkor a memória blokkok eléréséhez úgynevezett unsafe pointer-t alkalmaz a rendszer. Ezek a memóriaterületek az adott hatókör (pl.: egy metódus return utasítása) után automatikusan felszabadulnak. Példa:


class StackallocSample
{
    unsafe public static void ShowData(int* pArray)
    {
        for (int* ip = pArray; ip < (pArray+5); ip++)
        {
            Console.WriteLine("value {0} at address: {1}", *ip, (int)ip);
        }
    }
 
    static void Main(string[] args)
    {
        unsafe
        {
            int* pArray= stackalloc int[5];
            pArray[0] = 12;
            pArray[1] = 34;
            pArray[2] = 56;
            pArray[3] = 78;
            pArray[4] = 90;
            ShowData(pArray);
        }
    }
}

Minden téma végén megjegyzem, hogy ezeket a megoldások és példák természetesen nem az én fejemben születtek. Ahhoz, hogy az ember hozzájusson a fenti okosságokhoz, egyszerűen csak olvasni kell, méghozzá sokat. "Mert olvasni nem gyíkság..."

Iteráció teljesítménynövelés

A múltkori témák adták az ötletet arra nézve, hogy néhány további, teljesítménynövelésre buzdító javaslatot tegyek, de most inkább csak az iterációkra (ciklusokra) vonatkoztatva. A korábbi példákhoz nagyon hasonló eset az, amikor az egymásba ágyazott ciklusok önmagában álló teljesítményét vizsgáljuk. Az utasítások működési jellemzőjéből adódóan, a belső ciklus minden egyes iterációjának alkalmával a ciklusváltozót inicializálni kell, az összehasonlító logikai kifejezést értékelni kell, valamint ciklusváltozót is növelni kell.


for (int column = 0; column < 100; column++)
{
  for (int row = 0; row < 5; row++ )
  {
    …
  }
}

A fenti példában kívül van a több, belül pedig a kevesebb iterációt végrehajtó ciklus. Ezesetben a ciklusváltozók menedzselése egészen pontosan 100 + (100 * 5) = 600 alkalommal hajtódik végre, ami kiélezett helyzetben tetemes időt vehet igénybe. Ilyenkor nincs más teendő, mint a külső, többször iteráló, illetve a belső, kevesebbszer iteráló ciklust egyszerűen felcserélni egymással.


for (int row = 0; row < 5; row++ )
{
  for (int column = 0; column < 100; column++)
  {
    …
  }
}

A javított változatban a ciklusváltozók menedzselése 5 + (5 * 100) = 505 alkalommal hajtódik végre, ami a 16%-kal kevesebb feladatot ró a működtető környezetre (ez utóbbi példa javára). Természetesen .NET esetén ez a példa picit erőltetett, mivel a JIT fordító számos optimalizálást már előre végre tud hajtani. A végső megvalósítás előtt ezesetben is érdemes méréseket végezni.
Szintén ciklusok esetén jellemző az, amikor mondjuk egy metóduson belül lévő ciklusban végre kell hajtani bizonyos műveleteket, aztán később ugyanilyen cikluson belül egy másik műveletet. Ezesetben érdemes megvizsgálni annak a lehetőségét, hogy a két azonos feltételekkel rendelkező ciklust nem lehetne-e összevonni (ezek az úgynevezett „jamming” vagy „fusion” műveletek).


for (int i = 0; i <= 100; i++)
{
  employeeName[i] = "";
}
// Itt most különféle egyéb utasításokat, műveleteket kell elképzelni…
for (int i = 0; i <= 100; i++)
{
  employeeEarnings[i] = 0;
}

A fenti megoldás helyett, amennyiben ez lehetséges, legyen inkább összevonás…


for (int i = 0; i <= 100; i++)
{
  employeeName[i] = "";
  employeeEarnings[i] = 0;
}

A ciklusokon belüli összetett műveletek mértékét a lehető legkisebbre kell venni. Ez azt jelenti, hogy minden idő és erőforrásigényes utasítás esetén meg kell vizsgálni, hogy nem lehet-e azt kiemelni a cikluson kívülre.


for (int i = 0; i < rateCount; i++)
{
  netRate[i] = baseRate[i] * rates.CalculateDiscounts();
}

Ha a „rates” objektum „CalculateDiscounts()” metódusa mondjuk adatbázis, vagy más erőforrásigényes műveletet hajt végre, aminek a végeredménye az adott időben ugyanaz, akkor érdemes kiemelni azért, hogy csak egyszer hajtódjon végre (tudom, hogy ezek elemi dolgok, de hátha olyasvalaki is olvassa, aki csak most kezdi a programozói pályáját). Tudom-tudom... ezek primitív dolgok, de akkor is.


quantityDiscount = rates.CalculateDiscounts();
for (int i = 0; i < rateCount; i++)
{
  netRate[i] = baseRate[i] * quantityDiscount;
}

Amennyiben egy cikluson belül már nincs értelme a további iterációnak, akkor gondoskodni kell az iteráció azonnali, vagy legalábbis a lehető leghamarabb történő befejezéséről. Minden további felesleges műveletet teljesítmény és erőforrás gazdálkodási okokból kerülni kell.

Put About