Mire optimalizálsz?

A Linq-val kapot Enumerable osztály sok hasznos extension metódust tartalmaz, amelyet szívesen használ az ember. Én magam is szoktam használni, akár Linq-val, akár csak magában. Néha előfordul, hogy sehogy nem sikerül praktikusan kijátszani a szükséges műveleteket, és egy randa for ciklust kell a kódba leírni.

Az Enumerable extension metódusaihoz képest egy for ciklus használata rontja a kód olvashatóságát. Persze lehet, hogy csak az én szemem kényelmesedett el. Ugyanakkor sokszor látszik, hogy egy ronda ciklussal műveletszám szempontjából hatékonyabb kódot lehet készítni.

Nemrég kipróbáltam, hogy egy Enumerable.Sum() milyen teljesítményt nyújt egy for ciklushoz képest. Az eredmény sokkoló volt, a sum tizedakkora teljesítményt sem nyújt, mint egy for ciklus. Hogy miért, ennek járunk utána a következőkben.

Tegyük fel, hogy adva van egy Int32 elemeket tartalmazó tömb. Az ebben található számok összegét szeretnénk megkapni. Mivel a tesztben az Enumerable.Sum() extension metódust szeretnénk használni, figyelni kell rá, hogy a Sum OverflowException-t dob, ha az összeg túlcsordúl. Emiatt a tesztben a következő tömböt használjuk:

int[] data = new int[1024];
for (int i = 0; i < data.Length; i++)
{
  data[i] = (i % 31) - 15;
} // for

A tömb úgy van feltöltve, hogy egy összegzés ne csoduljon túl rajta. Emiatt -15 és +15 közötti értékek egyenletesen szerepelnek a tömbben. A kicsi tömböt persze mérhetetlen gyorsan feldolgozza a függvény. Emiatt milliónyiszor kell lefuttatni az összegzéseket. Alternatívaként lehetne egy hatalmas, többszáz megás tömböt használni, de ott inkább csak azt tudnánk mérni, hogy a memóriából milyen gyorsan jönnek az adatok, a folyamatos cache miss miatt a processzor sokszor várakozásra lenne kényszerítve. Helyette egy kicsi, cache-elt tömb a számítások erejét mutatja. Az összegzést három módszer szerint végezzük el.

Első módszer, a legtömörebb és legkifejezőbb:

int result = data.Sum();

Második módszer, ez nekem már mezítlábasnak tűnik:

int result = 0;
foreach (int i in data)
{
  result += i;
} // foreach

Harmadik, a full fapados módszer:

int result = 0;
for (int i = 0; i < data.Length; i++)
{
  result += data[i];
} // for

Az eredmények pedig a következők:

Sum: 21554 ms
foreach : 1860 ms
for: 1347 ms

A Sum metódus tehát brutálisan lassú a mezei ciklusok mellett. A két ciklus között viszont nincs túlzottan nagy különbség. Első dolgom a tesztek láttán az volt, hogy kipróbáljam, egyáltalán mit lehet kihozni a processzorból. Írhattam volna gépikódban egy ciklust, de már 15 éve lealázott a Microsoft C fordító, amikor egy napokig optimalizált, gépikódú mátrix invertáló függvényemre 30%-kal rávert sebességben, egy naívan megírt C kóddal. Emiatt készítettem inkább egy egyszerű C programot:

int iResult = 0;
int* pIterator = pData;
int* pEndAddr = pData + 1024;
while (pIterator < pEndAddr)
{
  iResult += *(pIterator++);
} // while

Ennek a ciklusnak a futásideje (2.5 milliószor lefuttatva) 936 ms, tehát 40%-kal gyorsabb, mint a C#-os kód. Nézzük meg, mit fordított a C fordító.

A kódnak van egy elő is utótagja, de a számítás ezen az öt soron dolgozik:

010D1080  add         edi,dword ptr [esi]
010D1082  add         ebx,dword ptr [esi+4]
010D1085  add         esi,8
010D1088  cmp         esi,eax
010D108A  jl          wmain+80h (10D1080h)

Az értelmezéshez tudni kell, hogy az eax-be a kód kb a pEndAddr-t rakta (hogy miért csak kb, majd később kiderül). Az esi pedig a pData-tól indul. Az edi és az ebx ki lett nullázva. Mi történik a ciklusban? Az edi-be összegzésre kerül minden páros (itt 0 az páros) indexen levő érték, és ebx-be minden páratlan indexen levő. Azaz a ciklus két értéket görget egymás mellett. Miért?

A Pentium processzoroktól kezdődően (1993-tól) két integer aritmetikai egység található meg a sorozat processzoraiban. Ez lehetővé teszi, hogy amennyiben nincs függőség két számítás között, azokat párhuzamosan el tudja végezni a processzor. Amit a fenti ciklus csinál tehát, hogy párhuzamosan hozzáadja edi-hez az esi által mutatott értéket, ebx-hez pedig az esi+4 által mutatott értéket. Ezután ugrik két integer-nyit a memóriában, és kezdi elölről. A ciklust megelőzően (nem látszik az ábrán) van egy kód, amely az aex- értékét úgy módosítja, hogy az esi+4 soha ne mutasson túl a célon (tehát páratlan esetben az utolsó értéket már nem ebben a ciklusban adja a göngyölt értékekhez), a ciklus után pedig ha maradt még egy kósza érték, azt hozzáadja az eredményhez, illetve összegzi edi-t és ebx-et.

Nehéz elképzelni, hogy ennél gyorsabban ez a feladat megoldható, de kíváncsi lettem, hogy mit generál a fordító a sima for ciklusra:

for (int i = 0; i < 1024; i++)
{
  iResult += pData[i];
} // for i

Ez lényegében megegyezik a C# kódjával, a futásideje pedig megegyezik a pointeres megoldással. Azért érdemes egy pillantást vetni a generált gépikódra:

0118106A  mov         eax,ebp
0118106C  mov         ebx,100h
01181071  add         edi,dword ptr [eax-8]
01181074  add         ecx,dword ptr [eax-4]
01181077  add         edx,dword ptr [eax]
01181079  add         esi,dword ptr [eax+4]
0118107C  add         eax,10h
0118107F  sub         ebx,1
01181082  jne         wmain+71h (1181071h)
01181084  add         esi,edx
01181086  add         esi,ecx
01181088  add         edi,esi

Varázslatos, nem? Elsőként veszi pData címét, és az eax-be teszi. Ezután felvesz ciklusszámlálónak 256-ot, ami az eredeti ciklusfeltételben megadott érték negyede. Ezután négyesével elkezdi összeadogatni az értékeket, legvégül pedig összegzi a négy értéket. Ennek eredményeképpen egy teljes ciklust összeadásokkal, ciklusváltozó karbantartással és feltételes ugrással a processzor megcsinált 4 lépésből (első lépés 2 darab add, második lépés megint 2 add, harmadik lépés az add és a sub, negyedik lépés jne). Emiatt, ha kiszámoljuk, hogy számunkra egy hasznos összeadás mennyibe kerül (a ciklusváltozó karbantartás számunkra nem hasznos művelet), ez a ciklus egy lépés (vagy a processzor 1 üteme) alatt megcsinál egy hasznos összeadást. Ezt a fokú optimalizálást az tette lehetővé, hogy a fordító észrevette, hogy az i változó értékére egyébként nincs szükség, csak az adateléréshez. Emiatt az i nek megfelelő eax-et nem kell egyesével növelni, ráadásul a ciklusfeltételt is kicserélte, hogy ne kelljen cmp-t használni minden körben. Nem az i-nek “megfelelő” aex-et használja, hanem egy másik irányba számláló ebx-et.

A pointeres ciklusnál jóval szerencsétlenebbül jönnek ki a lépések, mert bár a két érték göngyölése megoldható egy lépésben, utána függőségek vannak, mivel a [cmp esi, eax] függ az [add esi, 8]-tól, a jl pedig a cmp-től. Emiatt egy teljes ciklus 4 lépést igényel (ugyanannyit, mint a jóval hosszabb, négyesével összeadó kód), egy hasznos számítás így 2 ütemet. Elvileg ennek a ciklusnak fele olyan gyorsan kellene lennie, mint az előzőnek. Hogy miért nem ez a helyzet, arra nem tudtam rájönni. Elvileg a processzor belül át tudja rendezni az utasítások sorrendjét, így ha az adatot már megszerezte esi-ről és esi+4-ről, akkor az add esi, 8-at meg tudja csinálni párhuzamosan az egyik összeadással, a cmp esi, eax-ot pedig a második add-dal. Ekkor 1.5 ütem kell egy hasznos összeadásnak.

Ezek után nézzük, mint találunk a C# által fordított és a jittelt kódokban. Először jöjjenek az IL kódok. A leggyorsabbra sikerült for ciklus kódja a következő:

// V_5 = 0
  IL_00ac:  ldc.i4.0            // 0 (int32) a veremre
  IL_00ad:  stloc.s    V_5      // verem teteje V_5-be
// Ugrás a 00be címre
  IL_00af:  br.s       IL_00be
// result = result + data[V_5]
  IL_00b1:  ldloc.2              // result változó értéke a veremre
  IL_00b2:  ldloc.0              // data referencia a veremre
  IL_00b3:  ldloc.s    V_5       // V_5 értéke a veremre
  IL_00b5:  ldelem.i4            // data, V_5 helyett data[V_5] a veremre
  IL_00b6:  add                  // result, data[V_5] helyett result + data[V_5] a veremre
  IL_00b7:  stloc.2              // vermen lévő érték tárolása result változóban
// V_5 = V_5 + 1
  IL_00b8:  ldloc.s    V_5       // V_5 értéke a veremre
  IL_00ba:  ldc.i4.1             // 1 (int32) a veremre
  IL_00bb:  add                  // V_5, 1 helyett V_5 + 1 a veremre
  IL_00bc:  stloc.s    V_5       // vermen lévő érték tárolása a V_5 változóban
// if (V_5 < data.Length) goto IL_00b1
  IL_00be:  ldloc.s    V_5       // V_5 értéke a veremre
  IL_00c0:  ldloc.0              // data referencia a veremre
  IL_00c1:  ldlen                // data helyett a data.Length a veremre
  IL_00c2:  conv.i4              // unsigned data.Length -> int32
  IL_00c3:  blt.s      IL_00b1   // V_5 < data.Length, ugrás IL_00b1

A kód nagyjából megfelel annak, amit a ciklus alapján várnánk. Először egy a compiler által generált V_5 változó, ami a ciklusváltozó lesz, nulla értéket kap, ez a for (int i = 0; párja. Ezután egy ugrás következik a kód aljára, ahol a ciklusfeltétel található. Ha ez teljesül, a kód visszaugrik a kód közepére, ami a ciklusmag. Végül a for ciklus i++ nak megfelelő kód fut le. Maga az IL kód tehát közel sem tűnik olyan hatékonynak, mint a C-s párja.

Nézzük meg, mitől lassabb a foreach kódja a sima for ciklusnál:

// CS$6 = data; CS$7 = 0
  IL_0061:  ldloc.0              // data referencia a veremre
  IL_0062:  stloc.s    CS$6$0000 // verem teteje CS$6-ba
  IL_0064:  ldc.i4.0             // 0 (int32) a veremre
  IL_0065:  stloc.s    CS$7$0001 // verem teteje CS$7-be
// Ugrás a 007b címre
  IL_0067:  br.s       IL_007b
// V_4 = CS$6[CS$7]
  IL_0069:  ldloc.s    CS$6$0000 // CS$6 értéke a veremre
  IL_006b:  ldloc.s    CS$7$0001 // CS$7 értéke a veremre
  IL_006d:  ldelem.i4            // CS$6, CS$7 helyett CS$6[CS$7] a veremre
  IL_006e:  stloc.s    V_4       // a vermen lévő érték tárolása V_4-ben
// result = result + V_4
  IL_0070:  ldloc.2              // result értéke a veremre
  IL_0071:  ldloc.s    V_4       // V_4 értéke a veremre
  IL_0073:  add                  // result, V_4 helyett result + V_4 a veremre
  IL_0074:  stloc.2              // eredmény tárolása result változóban
// CS$7 = CS$7 + 1
  IL_0075:  ldloc.s    CS$7$0001 // CS$7 értéke a veremre
  IL_0077:  ldc.i4.1             // 1 (int32) a veremre
  IL_0078:  add                  // V_5, 1 helyett V_5 + 1 a veremre
  IL_0079:  stloc.s    CS$7$0001 // vermen lévő érték tárolása a CS$7 változóban
// if (CS$7 < CS$6.Length) goto IL_0069
  IL_007b:  ldloc.s    CS$7$0001 // CS$7 értéke a veremre
  IL_007d:  ldloc.s    CS$6$0000 // CS$6 referencia a veremre
  IL_007f:  ldlen                // CS$6 helyett a CS$6.Length a veremre
  IL_0080:  conv.i4              // unsigned CS$6.Length -> int32
  IL_0081:  blt.s      IL_0069   // CS$7 < CS$6.Length, ugrás IL_0069

A kód majdnem teljesen megegyezik a for ciklus kódjával. Két különbség van, amiből az egyik, hogy itt a data referenciája átkerül egy a fordító által generált változóba, a CS$6-ba. Erre azért van szükség, mert a ciklusnak akkor is az eredeti tömbön kell végigfutni, ha közben a data referencia értéke megváltozik. A for ciklusnál, ha a data referenciát a programozó átállítja egy másik tömb-re, akkor az az elvárt viselkedés, hogy az összegzés a másik tömbön folytatódik. Emiatt ott nem volt szükség a data referencia értékét elmenteni. A másik különbség, hogy a data[i] (illetve az ideiglenes változók miatt a CS$6[CS$7]-ik) elem értéke egy ideiglenes változóba, a V_4-be másolódik. Erre megint a foreach ciklus tulajdonságai miatt van szükség. Értéktípusok esetén a foreach ciklusban a ciklusváltozó a tömbnek csak az értékeit veszi sorra, nem pedig a tömb elemeit. Ez világossá válik a következő példán:

foreach (int i in data)
{
  i = 0;
} // foreach

Mit várunk el ettől a ciklustól? Azt, hogy nem történik semmi. A data tömb elemei változatlanok maradnak. Persze a működés nem a fenti eset miatt lett így kitalálva, hanem inkább egy ilyesmi miatt:

foreach (int i in data)
{
  DoSomething(i);
  i = i * 2;
  DoSomething(i);
} // foreach

Szóval a ciklusváltozót fel lehet használni a számításokban munkaváltozónak, mint ahogy egy függvény paramétereit is. Ebben az esetben sem akarjuk, hogy a tömb elemei változzanak. A for ciklus esetében viszont a

for (int i = 0; i < data.Length; i++)
{
  data[i] = 0;
} // for

kód pont azt akarja elérni, hogy a tömb elemei változzanak. Emiatt itt nincs szükség ideiglenes változókra, sőt, nem is lehetne használni. Az ideiglenes változó szükségessége a foreach ciklusnál az érték másolgatása miatt tehát egy kis teljesítmény veszteséggel jár. Észre kell venni azonban valamit. Nem triviális dolog, hogy a foreach áttranszformálható egy for ciklus jellegű formába. A foreach ugyanis eredendően minden IEnumerable interfészt megvalósító típuson tud működni, ezért azt várná az ember, hogy egy enumerátort használ az elemek megszerzéséhez. Látszik, hogy a C# fordító számításba veszi, hogy tömbök esetén sokkal hatékonyabb kódot tud generálni.

A legutolsó kód az Enumerable.Sum:

// if source == null, exception
  IL_0000:  ldarg.0              // source paraméter a veremre
  IL_0001:  brtrue.s   IL_000e   // ha nem null, ugrás IL_000e
  IL_0003:  ldstr      "source"  // string a veremre
  IL_0008:  call                 // exception a string alapján
    class [mscorlib]System.Exception
    System.Linq.Error::ArgumentNull(string)
  IL_000d:  throw                // exception dobása
// V_0 = 0
  IL_000e:  ldc.i4.0             // 0 (int32) a veremre
  IL_000f:  stloc.0              // verem teteje V_0-ba
// V_2 = source.GetEnumerator<int32>()
  IL_0010:  ldarg.0              // source paraméter a veremre
  IL_0011:  callvirt             // Az IEnumerable<int32>.GetEnumerator() hívása
    instance class [...]IEnumerator`1<!0>
    class [...]IEnumerable`1<int32>::GetEnumerator()
  IL_0016:  stloc.2              // Enumerator a V_2-be
  .try
  {
// while (V_2.MoveNext() == true) V_0 = V_0 + V_2.Current
    IL_0017:  br.s       IL_0024 // ugrás IL_0024-re
  //  V_1 = V_2.Current
    IL_0019:  ldloc.2            // enumerátor a veremre (V_2 ből)
    IL_001a:  callvirt           // enumerátor Current-propery gettere
      instance !0 class [...].IEnumerator`1<int32>::get_Current()
    IL_001f:  stloc.1            // Current propery értéke a V_1-be.
  // V_0 = V_0 + V_1
    IL_0020:  ldloc.0            // V_0 a veremre
    IL_0021:  ldloc.1            // V_1 a veremre
    IL_0022:  add.ovf            // összeadás overflow védelemmel
    IL_0023:  stloc.0            // összeg a V_0-ba
  // while (V_2.MoveNext() == true)
    IL_0024:  ldloc.2            // V_2 (enumerátor) a veremre
    IL_0025:  callvirt           // az IEnumerable<int32>.MoveNext() hívása
      instance bool [...]IEnumerator::MoveNext()
    IL_002a:  brtrue.s   IL_0019 // ha true van a vermen, ugrás IL_0019
    IL_002c:  leave.s    IL_0038 // Kilépés a try-ból, finally-t végrehajt
  }  // end .try
  finally
  {
    IL_002e:  ldloc.2
    IL_002f:  brfalse.s  IL_0037
    IL_0031:  ldloc.2
    IL_0032:  callvirt   instance void [mscorlib]System.IDisposable::Dispose()
    IL_0037:  endfinally
  }  // end handler
  IL_0038:  ldloc.0
  IL_0039:  ret

A kód első része csak ellenőrzést (source == null), és a majdan összeget tartalmazó változó inicializálását (V_0 = 0) tartalmazza. Később az IEnumerable-t megvalósító source paramétertől megszerzi az enumerátort, amit a V_2-ben tárol. Ezután egy ciklus megvalósítása következik, amely az iterátor segítségével megszerzi az IEnumerable összes értékét, és összegzi egy változóban.

Nem nehéz észrevenni, hogy a ciklus két függvényhívást tartalmaz, és nyilván ez okozza a lassúságot. De a gond itt nagyobb, mint elsőre látszik: mind a két hívás az IEnumerator interfész függvénye, és az interfészfüggvények hívása nagyon-nagyon erőforrás igényes, jóval lassabb még egy közönséges virtuális függvényhívásánál is.

Az értéktípusokról szóló cikkben láthattuk, hogy hogyan hívódnak a virtuális függvények, és miért hívódnak úgy. Amikor egy osztály bevezet egy függvényt, akkor a függvény a metódus táblában megkapja a soron következő szabad slot-ot. Ezután minden leszármazottnál, ha felül is írja a függvényt, az adott sloton keresztül a függvény meghívható. Ennek köszönhetően, ha van egy leszármazott példány, és egy alaposztály típusának megfelelő referencia, a leszármazott osztály függvényimplementációja elérhető az adott slot számmal.

Az interfész függvények hívásával az a gond, hogy egy interfészt több típus is megvalósíthat, illetve egy típust megvalósíthat több interfészt is. Ezek miatt nem lehet kiosztani minden metódustáblában például az IEnumerable interfész GetEnumerator függvényének az ötödik slotot, mert lehet, hogy egy olyan osztály valósítja meg az interfészt, aminek már eleve örökölt 30 függvényt, feltöltve ezzel a metódus tábla slot-jait 30-ig. De ha ki is lenne osztva az ötödik slot a GetEnumerator-nak, és azt mondanánk, hogy bármely típus, amelyiket az IEnumerable referencián érünk el, az ötödik slotban tartja a GetEnumerator-t, mit mondanánk az IEquatable Equals függvényére? Ennek nyílván nem lehet az ötödik slot-ot adni, mert egy típus megvalósíthatja az IEnumerable-t és az IEquatable-t egyszerre. Kapja meg a 6-os slotot? Az ICloneable Clone-ja meg a 7-eset? Mivel az interfészek száma korlátlan, fix slot-ra rendelni a függvényeit járhatatlan útnak látszik. Viszont akkor hogy lehet megtalálni adott típusnál az IEnumerable GetEnumerator()-t?

A .NET karbantart egy nagy táblázatot. Ebben a táblázatban megtalálható minden, az adott application domain-be betöltött típushoz egy táblázat szekció. Ez a szekció tartalmazza minden, a típus által megvalósított interfészhez, hogy a típus metódustáblájában hol található az interfész “mini” metódus táblája. A nagy táblázatot Interface Offset Table-nek (IOT) (más forrásokban Interface VTable Map-nek) hívják. Azt, hogy egy típushoz hol található az IOT-ban a saját része, az a típus metódustáblájában megtalálható, egy fix címen. A következő ábra alapján világosabban látható az egész.

Adottak a következő interfészek, és az azokat megvalósító típus:

interface ITeleport
{
  void Transmit(...);
  void Clone(...);
}
interface IDuplicator
{
  void Clone(...);
  void CloneMany(...);
}
class QuantumBlaster : ITeleport, IDuplicator
{
  public void Transmit(...) {...}
  public void Clone(...) {...}
  public void CloneMany(...) {...}
}

Ekkor a táblázatok a következő módon néznek ki:

Ha van egy IDuplicator referencia egy QuantumBlaster példányra, és azon meghívásra kerül egy Clone() függvény, a következő folyamat játszódik le:

Az IDuplicator referencián keresztül el lehet érni a QuantumBlaster példányt (1). Minden referencia típusú példány tartalmaz egy mutatót a metódus táblára (2). Ez a metódus tábla tartalmaz egy mutatót egy másik táblázatra, az IOT-ra (3).

Még korábban, amikor egy interfész betöltésre került, a CLR generált neki egy azonosítót. Ezután, amikor egy típus betöltésre kerül, a CLR megnézi, hogy az milyen interfészeket valósít meg. Összeszámolja a megvalósított interfészeket, felvesz egy szekciót a típusnak az IOT-ba, ennek a szekciónak a mutatóját eltárolja a metódus táblában (mindig a fix, 12-ik byte-tól kezdődően) illetve azt is eltárolja, hogy hány interfészt valósít meg a típus (16-ik byte). Ezen felül a metódus táblában kitölt minden megvalósított interfészhez egy területet, amely megmutatja, hogy az interfészhez hol találhatóak az implementált függvények.

Egy interfészfüggvény hívásánál az IOT-ból egy szekvenciális kereséssel (4) most meg kell keresni az IDuplicator-hoz tartozó bejegyzést. Ez a példában a második bejegyzés lesz. Ez a bejegyzés visszamutat a QuantumBlaster típus metódustáblájára, egy olyan részhez, ahol az IDuplicator-hoz tartozó slot-ok vannak (5). A CLR tudja (egy másik, fel nem rajzolt táblázatból), hogy a Clone metódus az első slotban van, így a slot-on keresztül már eléri az IDuplicator.Clone-t (6). Az ábrából látszik, hogy az ITeleport.Clone ugyanarra a területre mutat, hisz az implementáció közös az IDuplicator.Clone-nal. Ezenkívül a metódus tábla (bár az ábrán nem szerepel) tartalmaz egy harmadik slotot a Clone függvényre, ami akkor kerül használatra, ha a függvény nem interfész referencián keresztül kerül meghívásra, hanem QuantumBlaster típusú referencián keresztül. Ez utóbbi hívás egyébként nem igényli az IOT bevonását, hanem a közönséges virtuális függvényeknek megfelelően a CLR mindig adott sorszámú sloton keresi a függvény implementációját.

Bár egy szem hívásnál a fenti hosszadalmas folyamatot végig kell játszani, a jitter tud némileg optimalizálni. Ha kódrészleten belül egy interfészen több függvényt kell meghívni, vagy ugyanazt a függvényt többször, akkor olyan kódot generál a jitter, ami a függvények címeit eltárolja a vermen, így nem kell minden hívásnál végigjátszani a lassú keresési folyamatot. A sum függvény ciklusban hívja a MoveNext metódust és Current property gettert, de a cikluson belül ez már nem okoz akkora teljesítményveszteséget, mint amekkora a fenti leírásból következne.

Ha tud is a jitter optimalizálni az interfész függvények hívásán, maga az IEnumerator interfész Current property és MoveNext függvény belseje jóval több utasításból áll, mint a C-s verziónál az elemre címzés és az add vagy sub gépikódú utasítás. Emiatt érthető, hogy a kód végrehajtása lassabb. Valójában az a furcsa, hogy a sokkal bonyolultabb kódja ellenére csak ennyivel lassabb az Enumerable.Sum(). Látszik, hogy a processzor utolsó mentsvárként még megtesz mindent a teljesítmény fokozása érdekében, legyen az az utasítások átrendezése a párhuzamosság érdekében, vagy bármi más trükk.

A sum jittelt kódját felesleges idemásolni, mert hosszú, a metódushívások miatt több részből áll, és egyébként nagyon nehezen érthető. A summal ellentétben viszont érdemes összehasonlítani, a C# for ciklus jitter által generált kódját a C-s verzióval:

003400ee  add     edi,dword ptr [esi+ecx*4+8]
003400f2  inc     ecx
003400f3  cmp     edx,ecx
003400f5  jg      003400ee

Bár az IL kódot a jitter nagyon szépen feldolgozta, és tömörré tette, a C fordító megoldásához képest hiányoznak a dupla aritmetikai egységre épülő optimalizációk. A jitter mentségére szóljon, hogy a jitternek közel sincs annyi ideje optimalizálni, mint a C fordítónak. A jitter egy metódus első hívásakor fut le, és nem akaszthatja be túl sok időre a program futását. Egy nagyobb programban rengeteg olyan metódus van, ami csak egy-két alkalommal fut le, egy erős optimalizálás több időbe kerülne, mint amennyi időt az optimalizációval nyerni lehet. Valószínű ezért van ember számára könnyen kiszúrható felesleges művelet a foreach jittel kódjában is:

003800e6 mov     eax,dword ptr [esi+edx*4+8]
003800ea add     edi,eax
003800ec inc     edx
003800ed cmp     ecx,edx
003800ef jg      003800e6

Itt a tömb adott eleme ugyanúgy egy ideiglenes területre másolódik (eax) mint az IL kódban, pedig ez a lépés ebben a helyzetben teljesen felesleges, bár ez már az IL kódnál is kioptimalizálásra kerülhetett volna. Ez a felesleges másolás negyedével növeli a végrehajtandó utasítások számát, és így a futásidőt is. Érdekes, hogy a két C-s kód között (lásd a cikk elején) sokkal nagyobb különbség van, mint a két C# kód között. A C-s kódok között viszont nem jött elő sebesség különbség, itt pedig egy plusz regiszterbe mozgatás észrevehetően növeli a futásidőt.

Konklúzió

Az optimalizációnak sok lépcsője került bemutatásra. Lehet optimalizálni programozóként, optimalizálhat a C# fordító, a jitter és maga a processzor is. Programozóként viszont sokszor nehéz kiszámítani, melyik eset a gyorsabb. Én a cikk elején a C kód esetében a pointeres összegzést gondoltam volna gyorsabbnak, azért is próbálkoztam azzal először. Ezután a generált gépikód alapján a for ciklus megoldása nézett ki jobb megoldásnak. Végül, legalábbis az én számítógépemen a két kód ugyanolyan gyorsan futott le.

Az is látszik, hogy a compilerek a tipikus „kód-fordulatokra” fel van készítve. Ha esetleg okoskodunk, pont azt érhetjük el, hogy a compiler nem fogja felismerni a trükkjeink miatt a szemantikát, emiatt nem tud hatékonyan optimalizálni, és a próbálkozásaink a visszájára fordulnak.

Harmadrészt, bár néha abba a szerencsés helyzetbe kerül a programozó, hogy valami izgalmas feladatot minél profibb módon kell implementálni, legtöbben kódgyárakban dolgozunk. Itt inkább a rövid határidő és hónapok, évek múltán mások számára is jól érthető kód a lényeg. A for ciklus ugyan többször gyorsabb, ha önmagában nézzük, a kódnak feltehetőleg igen kis százalékát teszi ki. Emiatt a teljes kód valószínűleg észrevehetetlen mértékben gyorsul csak.

A fentiek alapján ezért úgy gondolom, az esetek 95%-ban az Enumerable.Sum, és társai a jó választás.

  1. #1 by Zsolt Soczo on 2011. June 23. - 01:28

    Az unsafe se gyorsabb, mivel az értékhatár-ellenőrzést a safenél kioptimalizálja a jitter. Kivéve, ha kirakjuk lokális változóba a tömb hosszát, akkor egyből lassabb lesz.

    using System;
    using System.Diagnostics;

    unsafe class Program
    {
    static void Main()
    {
    int[] data = new int[1024];
    for (int i = 0; i < data.Length; i++)
    {
    data[i] = (i % 31) – 15;
    } // for

    Stopwatch w = Stopwatch.StartNew();

    int iter = 5000000;
    for (int j = 0; j < iter; j++)
    {
    int result = 0;
    for (int i = 0; i < data.Length; i++)
    {
    result += data[i];
    } // for
    }

    w.Stop();
    Console.WriteLine(" Safe: {0}", w.Elapsed);

    w.Restart();

    for (int j = 0; j < iter; j++)
    {
    int result = 0;

    fixed (int* p = data)
    {
    int* lastItem = p + data.Length;
    for (int* i = p; i < lastItem; i++)
    {
    result += *i;
    }
    }
    }

    w.Stop();
    Console.WriteLine("Unsafe: {0}", w.Elapsed);

    }
    }

  2. #2 by Tóth Viktor on 2011. June 23. - 10:53

    Igen, nagyon jó észrevétel! Ugye ha a ciklusfeltételben a data.Length van, akkor ilyen kódot generált a jitter:

    Ez a C# kód:

    int result = 0;
    for (int i = 0; i < data.Length; i++)
    {
    result += data[i];
    } // for

    Ezt fordítja:

    // korábban az edx-be belekerült a data.Length.
    // az edi-be szummázik.
    003400ee add edi,dword ptr [esi+ecx*4+8] // következő elem hozzáadása
    003400f2 inc ecx // i++
    003400f3 cmp edx,ecx // i < data.Lenght
    003400f5 jg 003400ee // következő iteráció

    Ha viszont kirakjuk lokális változóba a hosszt (mondjuk a length-be), akkor úgy látszik, a jitter már nem fogja azt vizsgálgatni, hogy amíg beér a ciklusba a vezérlés, a length értéke változik-e, illetve a cikluson belül változik-e, és ennek az információnak a hiányában kénytelen újra és újra ellenőrizni:

    a C# kód:

    int result = 0;
    int length = data.Length;
    for (int i = 0; i < length; i++)
    {
    result += data[i];
    } // for

    Amit fordít:

    // mire ideér a vezérlés, edx-et már kinullázta, ez lesz a
    // ciklusváltozó

    // Megjegyzi a tömb méretét, hogy tudjon ellenőrizgeti.
    // Itt most ecx-be lesz a data.Length, amit pedig közvetlen
    // a tömb layoutjábol olvas ki.
    00000041 mov ecx,dword ptr [edi+4]

    // Itt jön az ellenőrzés a tömb értékhatárra. emiatt a kód miatt lasabb,
    // ha nem közvetlen data.Length-et használunk:
    00000044 cmp edx,ecx // i < data.Length
    00000046 jae 00000074 // ugrás a kódra, ami majd dobja az exceptiont

    // innen a kód már ugyanaz, mint korábban:
    00000048 add esi,dword ptr [edi+edx*4+8] // következő elem hozzáadása
    0000004c inc edx // i++
    0000004d cmp edx,ebx // i < length
    0000004f jl 00000044 // következő iteráció

    Persze, meg lehetne csinálni a jittert, hogy figyeljen ezekre is, csak hát ha túl sok mindenre kell figyelnie, olyan lassú lenne, hogy több veszne el az ellenőrzéseken, mint amit az optimalizálással nyer.

  3. #3 by isten on 2012. April 6. - 13:42

    Szia!

    “(itt 0 az páros)”
    Miért, hol nem páros a 0?

    • #4 by Tóth Viktor on 2012. April 6. - 14:10

      Rulett táblán példul?😉

      • #5 by isten on 2012. April 6. - 16:56

        Igaz. Azt hittem, tudsz valami egzotikus platformot vagy nyelvet🙂

  1. Mikro-optimalizáció – van értelme? - pro C# tology - devPortal
  2. Megoldás – Minifeladatok II. - pro C# tology - devPortal

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: