Mikro-optimalizáció – van értelme?

Aki már pár hónapnál többet dolgozott együtt más programozókkal, vagy szokott szakmai cikkeket böngészni, találkozhatott tippekkel-trükkökkel, amelyek gyorsabb kódot eredményeznek. Kezdőknek szóló könyvekben például gyakran találkozni hasonlóval:

int x = 12;
Console.WriteLine("Az érték {0}", x); // Boxing, ilyet ne!
Console.WriteLine("Az érték {0}", x.ToString()); // Ezt így kell...

Számomra például nem teljesen egyértelmű, hogy melyik megoldás a jobb. Igen, a második elkerül egy memóriafoglalást, ezáltal egy egészen picit gyorsabb, ráadásul elképzelhető, hogy egy egészen picivel később indul el a GC, és lehet, hogy ennek köszönhetően így a program teljes futása alatt nem 318745 szemétgyűjtés fut le, hanem eggyel kevesebb. Wow!

Másik oldalról, az első megoldás könnyebben olvasható – nem mintha a második annyira megterhelné a programozó agyát. Számomra azonban a könnyen olvasható kód általában nagyobb prioritást élvez, és ha a kimutathatatlanul gyorsabb kód illetve a picikével átláthatóbb között kell választanom, inkább legyen átláthatóbb.

De nem a boxing-ról és a ToString()-ről szeretnék beszélni, teljesen mindegy mit használ a fenti esetben a programozó, mert jelentéktelen dologról van szó. Még csak abban sem szeretnék állást foglalni, hogy mikor van értelme mikro-optimalizációnak. Amit ebben a cikkben meg szeretnék mutatni, az az, hogy nem olyan könnyű ilyeneket csinálni, és könnyen előfordul, hogy a mikro-optimlaziációnk pont a teljesítmény rovására megy. Ez általában szintén nem gond, inkább csak nevetséges.

A feladat, amit nézni fogunk, már felbukkant korábban a mire optimalizálsz című cikk kommentjében, és Soci volt olyan kedves megosztani velünk. A példa azért tetszik különösen, mert ellene megy az intuíciónknak, és így nagyon jól modellezi azt, amiről beszélni szeretnék.

A feladat egyszerű, adott egy tömb, aminek végig kell iterálni az elemein. Ezt a feladatot első nekifutásra sokan így írnánk meg (ok, az összeadás miatt a LINQ fan-ok nem, én magam is a Sum-ot használnám, de most a ciklus a lényeg, az összeadás csak azért van ott, mert valamit csinálni kell):

var data = new int[1000000];
var result = 0;

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

Ennek a ciklusnak a futásideje mérhetetlen, de egy külső ciklusba beágyazva és 1000-szer lefuttatva az átlagos teljesítményű gépemen 750ms körüli eredményt kapunk. Mit lehet itt optimalizálni? Feltűnhet, hogy a Length property-t minden fordulóban újra lekérdezzük az i < data.Length kiértékeléséhez, ami rengeteg hívást okoz. Na jó, a művelt kollegák tudni vélik, hogy a rövid property gettereket a jitter beinline-olja, azaz nem lesz itt milliónyí függvényhívás. Másik oldalról, ha inline-ol is a jitter, ha mi kirakjuk ezt az értéket egy lokális változóba, akkor még az inline-olt kódot is meg lehet spórolni, jó esetben ez a változó bekerül egy regiszterbe, amivel gyorsan lehet majd hasonlítgatni. Írjuk át a kódot, és mérjük le:

var dataLength = data.Length;

for (var i = 0; i < dataLength; i++)
{
  result += data[i];
} // for i

Ha lemérjük mennyit gyorsult a ciklus, azt kapjuk, hogy most 2100ms felett produkál. Hát, nem ezt vártuk! Még ha olyan kitűnő is a jitter, akkor is rossz esetben egyformának kellene lenni az időknek, de semmiképpen nem háromszor lassabbnak! Mi történt?

Az a helyzet, hogy a jitter felismer néhány szemantikát, és ennek figyelembevételével tud optimalizálni. Tömbök indexelésekor például a CLR kínosan ügyel arra, hogy nehogy egy tömbből kicímezzen a program. Emiatt a tömb indexeléseket ellenőrzi, ami természetesen némi időbe kerül. Van néhány olyan helyzet, amikor előre meg lehet mondani, hogy az adott kódrész biztosan nem címez ki, és ezeknek a helyzeteknek némelyikét a jitter felismeri. Ha egy for ciklusban például a ciklusváltozó a conditional expression-ben kisebb, mint a tömb mérete, és a cikluson belül azt már nem piszkáljuk, és ezt használjuk indexelésre, akkor a ciklusmag nem fog kicímezni a tömbből, ezáltal felesleges az ellenőrzés is. Ezért az “alap” for ciklusban ez elmaradhatott.

A módosított verzióban a jitter nem ismerte fel a helyzetet, emiatt belegenerálta az ellenőrzést, ez lassította a kódot. Mondhatjuk, hogy buta a jitter, hiszen nekünk programozóknak azonnal szembetűnik, hogy ugyan olyan értelmű kódról van szó. Azonban ne felejtsük el, hogy a jitter futásidőben dolgozik, nem analizálgathat túl sokat, mert végül több idő megy el optimalizációra, mint amennyi időt az optimalizált kód megtakarít. Így is viszonylag okosan dolgozik, például egy ilyen még belefér:

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

Sőt, még ez is:

for (var i = 0; i < (data.Length - 2); i++)
{
  var k = i ;
  result += data[k];
} // for i

de ez például már sok, ez a ciklus be fog lassulni:

for (var i = 0; i < (data.Length - 2); i++)
{
  var k = i + 2;
  result += data[k];
} // for i

Konklúzió

A fentiekben láthattunk egy rosszul elsült mikro-optimalizációt. Nem az volt a célom ezzel, hogy megmutassam, a mikro-optimalizáció rossz. Ha valamiről ki kellene jelentenem, hogy rossz, azok az egymondatos bölcsességek. Ez a cikk egy sorozat első eleme, szeretnék a jövőben pár további példát bemutatni, amelyen keresztül árnyalni lehet a képet az optimalizációk értelméről.

Fontos megjegyezni azt is, hogy a fent vizsgált ciklus magja nagyon kicsi műveletigénnyel bírt, nem szerepelnek a tömbhasználaton kívül más sallangok, egymilliárdszor futtattuk le, és így okozott másfél másodperces különbséget. Ez egyben azt is jelenti, hogy iterációnként milliárdod másodpercekről beszélünk, ami azért ritkán számít, és főleg nem, ha a ciklusmagban egyéb dolgok is történnek. Ez a mikro-optimalizációk egyik közös tulajdonsága.

Megszállottaknak

Hogy biztosan a tömbhatár ellenőrzés okozza a teljesítmény különbséget, a következőkben megnézzük a jittel-t kódot. Vigyázni kell, hogy debuggerből indítva nem az alábbi eredményt kapjuk, mivel a jitter másképpen optimalizál, ha egy debugger attacholva van. Én azt szoktam csinálni, hogy egy Debugger.Break() hívást teszek a kérdéses rész felé, majd full optimalizációval elindítom a programot debuggeren kívül. Így amikor a debugger attach-ol, a jitter már elvégezte a dolgát, és így a szépen optimalizált kódot láthatjuk. Az alábbiak egyébként megtalálhatóak a korábban említett kommentben is.

A szimpla for ciklus a következőre fordul:

// korábban az edx-be belekerült a data.Length egy
// mov edx,dword ptr [esi+4] hívással. Látszik tehát, hogy
// a jitter nem csak inline-olja az Array.Length gettert, hanem 
// intim tudása van a tömbökről.
// Az alábbi kód az edi-be szummázik, esi pedig a data tömb.
// A tömb layoutjában a 8-ik byte-tól kezdődnek az elemek (4-en van
// a Length, 0-án metódus tábla pointer)
003400ee add edi,dword ptr [esi+ecx*4+8] // következő elem hozzáadása (result += data[i]
003400f2 inc ecx                         // i++
003400f3 cmp edx,ecx                     // i < data.Lenght
003400f5 jg 003400ee                     // következő iteráció

Az “optimalizált” kódunkból ez fordul:

// mire ideér a vezérlés, edx-et már kinullázta, ez lesz a
// ciklusváltozó. A dataLength változó már beolvasásra került egy
// ebx,dword ptr [esi+4] hívással.

// Az tömb index ellenőrzéshez a tömb méretének regiszterbe
// helyezése. Tehát hiába tettük ezt mi meg a dataLength-tel,
// a jitter ezt nem használja, hanem csinál egy ugyanolyan
// változót
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 lassabb,
// 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, a regiszterek másképp
// lettek "kisorsolva"
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ó
  1. #1 by Galder on 2011. August 23. - 19:45

    Helló!

    Klassz cikk! Várom a többit is!

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: