Nemrég egy blog kommentjében utalást láttam arra, hogy bizonyos szint felett illik az embernek a for-ciklusát a következő formában leírni:
for (int i = 0; i < ..; ++i)
A hangsúly a ++i részen van. Miért jó ez így? A programozók jelentős része az “i++”t használja, meg nem tudom mondani miért. Én is az “i++” használom, pedig Übermensch hardcore C++ programozó koromban egyszer már átszoktam “++i”-re, pusztán a sznobizmus miatt. Mivel a “++i” szemet szúr, van esély, hogy megkérdezik mért azt írtam, és az ember fellengzősen elmondhatja a következőket:
Az “i++” azért nem jó ilyen helyzetben, mert a kifejezés értéke az i eredeti értéke. Emiatt a fordítónak olyan kódot kell generálni, ami az eredeti értéket elmenti, hogy utána megcsinálhassa az értéknövelést vagy amilyen műveletet takar az operátor. Ez főleg problémás, ha az i valami komplexebb típusú, mert akkor a komplex típust kell másolgatni – feleslegesen. Ez a felesleg pedig teljesítményromlásban jelentkezik.
Az elmélet azon bukik meg, hogy a másolás felesleges mivoltát a compilerek is észreveszik, és emiatt nem is csinálják. Ezt fogjuk megnézni a következőkben.
Nézzük az alábbi kódot:
static void Main(string[] args) { for (int i = 0; i < 100; i++) { Console.WriteLine(i); } // for i } // Main()
Most pedig azt, hogy mit generált belőle a C# fordító:
.method private hidebysig static void Main(string[] args) cil managed { .entrypoint // Code size 20 (0x14) .maxstack 2 .locals init ([0] int32 i) // i = 0 IL_0000: ldc.i4.0 // 32 bites 0 érték az evaluatuion stack-ra IL_0001: stloc.0 // Tárolás a Local Variable Array (LVA) 0-ik elemébe (i változóba) // A for ciklus lefutásából most a ciklusfeltétel jön, // ezt a kódot a fordító alulra tette. Ugrás oda IL_0002: br.s IL_000e // (27-es sortól nézd) // Console::WriteLine(i) IL_0004: ldloc.0 // LVA 0. eleme (i változó) az evaluatuion stack-ra IL_0005: call void [mscorlib]System.Console::WriteLine(int32) // i++ IL_000a: ldloc.0 // LVA 0. eleme (i változó) az evaluatuion stack-ra IL_000b: ldc.i4.1 // 32 bites 1 érték az evaluatuion stack-ra IL_000c: add // verem két felső értékének összeadása, eredmény a veremre IL_000d: stloc.0 // eredmény elmentése a veremről i-be (LVA 0. elem) // i < 100 IL_000e: ldloc.0 // LVA 0. eleme (i változó) az evaluatuion stack-ra IL_000f: ldc.i4.s 100 // 32 bites 100-as érték az evaluatuion stack-ra IL_0011: blt.s IL_0004 // Ugrás a 4-es címre (17-es sor), ha az két veremre tett // érték közül az első kisebb (a két érték lekerül a veremről) IL_0013: ret } // end of method Program::Main
A lényeges sorok az 20-24 soroknál találhatóak. Elvileg itt kellene olyan kódnak állni, ami elmenti az i eredeti értékét – de ennek nyomát sem látjuk. Olyan kódot kellene látnunk, ami valahová átmásolja az LVA 0. elemét (mondjuk LVA 1-be), aztán nem csinál vele semmit. Ha a for ciklust “++i”-t használva írnánk le, teljesen ugyanzet a kódot kapnánk (igen, kipróbáltam).
A fenti kódot a jitter még tovább tudja optimalizálni, nézzük meg azt is:
00000000 push ebp // Veremre dolgozik a függvény, az állapot 00000001 mov ebp,esp // mentése (verem tetejének mentése) // A Main függvény egy paramétert vár referencia típussal, illetve a // függvényhez tartozó Local Variable Array egy 32 bites értéket hordoz. // Ezeknek kell 8 byte. Azt szoktuk meg, hogy a paraméterek a vermen adódnak át, // de a CLR az első paramétert mindig az ecx regiszterbe hozza. Ez amúgy általában // a this pointer, de a Main statikus függvény, így ilyen most nincs. Az ecx most // az args paramétert hordozza. A lényeg, hogy 8 byte munkaterület kell a vermen: 00000003 sub esp,8 // Mivel az ecx kell a függvény implementációban, mint munkaváltozó // az értékét el kell menteni (ha esetleg használnánk az args-ot): 00000006 mov dword ptr [ebp-4],ecx // Erre nem jöttem rá mi, csak akkor generálja a jitter, ha egy debugger // attacholva van. Az SSCLI implementációjából úgy tűnik, hogy a jitter // egy "Just My Code" callback-nek nevezett kódot generál ide, de nem jöttem // rá, hogy működik. A mi szempontunkból ez most nem is érdekes. 00000009 cmp dword ptr ds:[00252E28h],0 00000010 je 00000017 00000012 call 65C1B701 // Mivel a Main függvényen be van kapcsolva az a flag, ami a CLR-től kéri // a lokális változók nullázását (lásd előző, értéktípus konstruktorokról szóló cikk), // nullázni kell a lokális változókat. Az egyetlen lokális változó az i, ez van az ebp-8-on: 00000017 xor edx,edx // a művelet eredménye 0 00000019 mov dword ptr [ebp-8],edx // tárolás az i változó helyén // Itt kezdődik a for ciklus kódja, a logika ugyanaz, mint az IL // kódnál // Nem, nem ilyen buta a jitter, ha nincs debugger attacholva, // akkor ez a kód nem lenne itt. Most az i = 0 miatt láthatjuk // megismételve az előző két utasítást, a debugger miatt nem // lett kioptimalizálva: 0000001c xor edx,edx 0000001e mov dword ptr [ebp-8],edx 00000021 nop // A ciklusfeltétel kódja az IL-hez hasonlóan itt is alulra került, ugrás oda 00000022 jmp 00000030 // Ez a Console.WriteLine(i) kódja. Mint mindig, a CLR az első paramétert // az ecx-ben adja át. Statikus függvényt hívunk, ezért nem kell a this, // szóval az int32 megy az exc-ben. // Érdekes megnézni, hogy a call milyen furcsán néz ki. Ez a következők miatt // van így: Amikor a jitter elkezd fordítani egy metódust, akkor a metódusból // hivott további metódusok vagy le vannak már fordítva a jitter által, vagy nem. // Ha le vannak fordítva, akkor a címük meghatározható a memóriában, és a call // erre a címre hívna közvetlenül. // Ha a függvényt még nem hívták soha, akkor a jitter azt még nem fordította le. // Természetesen nem fogja most azért lefordítani, hogy meglegyen a cím, mivel az // a metódus további másikakat hívhat, amit ilyen logika alapján megint jittelni // kellene, és végül az egész program egy lépésben le lenne fordítva. // Ehelyett a jitter foglal egy slotot a memóriában ahova egy függvény címét tudja // rakni. Ezt ráállítja egy területre, ami amúgy magát a jittert hívja, hogy fordítsa // le a Console.WriteLine-t. miután ezt megtette, a lefordított függvény címét visszaírja // az említett slotba. Így első hiváskora jitter fog lefutni (az ő címe van a slotban) a // további hivásokkor már a Console.WriteLine. Az indirekció egy kicsit lassítja a futtatást. // Ha a program más részein majd hívják a WriteLine-t, ott már "szép" call lesz. // Az alábbi call tehát a slot-ban tárolt címre hív, a slot címe pedig 0x0084E080 00000024 mov ecx,dword ptr [ebp-8] 00000027 call dword ptr ds:[0084E080h] // Az i++ implementációja. Látható, hogy nem örzi meg az eredeti // értéket, közvetlenül növeli az i-t. Ennél optimálisabb már csak // regiszter használattal lehet, ha nincs debugger attacholva, akkor // a jitter olyan kódot fordít. 0000002d inc dword ptr [ebp-8] // Ha i < 100, ugorjon vissza 24-re 00000030 cmp dword ptr [ebp-8],64h 00000034 jl 00000024 // Verem helyreállítása, és vissza a hívóhoz. 00000036 nop 00000037 mov esp,ebp 00000039 pop ebp 0000003a ret
Na de mi van a koncepcióval?
A bizonyos szint felett levő kollegák elképzelhető, hogy úgy tartják, a ++i nem csak a teljesítmény miatt jobb, hanem jobban kifejezi a fejlesztő szándékát. A ++i vagy az i++ az egy loop-expression, igéret szerint ez a kifejezés minden alkalommal ki lesz értékelve, még a conditional-expression kiértékelése előtt. Magának a loop-expression kifejezés értékének nincs hatása, mivel a runtime ezt nem használja semmire, a conditional-expression-nel ellentétben, aminek az értékétől függ, hogy lesz-e következő iteráció.
A fentiek miatt a loop-expression esetében a kifejezés kiértékelésének a mellékhatásai fontosak, nem pedig az értéke. A tipikus mellékhatás egyébként az, hogy a ciklusváltozó értékét megváltoztatják, mondjuk megnövelik eggyel. Ezt a mellékhatást pedig többféleképpen el lehet érni, és szerintem nem kell bizonyos szint felett lenni ahhoz, hogy mindenki egyformának lássa a ++i, i++, esetleg i = i + 1 mellékhatását.
#1 by Morzel on 2011. June 22. - 19:18
Uhh, mióta van foreach meg linq, nem sűrűn használtam for ciklust…
#2 by Janka János on 2011. June 22. - 23:45
A foreach-nek megis van a maga overheadje. Én meg épp ellenkezőleg, ahol lehet sima for-t használok. Persze ez attól is függ, hogy milyen lista típust használsz, mert pl. egy LinkedList esetében épp ellenkező hatást váltanál ki egy indexer használatával. Mindenesetre amikor leteszteltem a for és foreach közötti különbséget egy sima tömbön több ezer iteráció esetén, akkor meglepő eltérések jöttek ki. De ez még hagyján ahhoz képest, amit a Linq To Objects-el el lehet követni, ha nem figyel oda valaki és azt hiszi, hogy az Linq To SQL. 🙂
#3 by Janka János on 2011. June 22. - 23:58
Itt volt egy ilyen teszt egyébként: http://diditwith.net/2006/10/05/PerformanceOfForeachVsListForEach.aspx . Jól látszik, hogy még azon is lehet nyerni egy keveset, ha az iterációnkénti List.Count hívást megspórolod. Nálam mondjuk lényegesen eltérőbb eredmények jöttek ki, de a lényegen nem változtat. Szeretem az ilyen mikro optimalizációkat.
#4 by Bukta Máté on 2012. March 7. - 15:44
Ezek az eredmények érdekesek. Én megnéztem Stopwatch-al, hogy a for vagy a foreach gyorsabb-e és egy sima int[1000000] tömböt a for 450 ms, a foreach pedig 5 ms alatt járja be. Mellesleg korábban is csináltam ilyen teszteket és végeredményben az jött ki hogy akkor a leggyorsabb egy bejárás ha:
-2x járjuk be a tömböt. Először foreach-al, másodszor for-ral. (2. a konkrét bejárás)
-referencia típusok a tömb elemei és osztályból kezdeményezzük a bejárásokat.
Röviden ennyi. A lényeg, hogy a foreach 100x gyorsabb. Nem tudom miért van, hogy a for ciklust mindenki gyorsabbnak mondja.?
#5 by Tóth Viktor on 2012. March 7. - 17:14
ezt a témát körbejártam ebben a cikkben:
Nekem a for ciklus a gyorsabb.
Ha elküldöd a teszt programot, amivel az eredményeidet kaptad, szívesen megvizsgálom:
toth.viktor kukac hotmail.com
#6 by Chapell on 2011. June 24. - 14:48
Én megbízok a Microsoft arcokban, ha már VS-ben a for-nak a code snippetje i++ -t ír, akkor miért szóljak bele? ;D
#7 by Török Attila on 2011. June 24. - 22:04
Eléggé jó 🙂
#8 by Tóth Viktor on 2011. June 25. - 09:12
Kössz! A vicces az, hogy ebbe a bejegyzésbe egy óránál is kevesebbet fektettem (a többiben kutakodással együtt benne van 30-40-50 óra), mégis ez az első, ami három nap alatt több, mint 400 kattintást hozott 😀 Lehet stratégiát kellene váltanom…
#9 by Török Attila on 2011. June 29. - 14:00
Mert ezt könnyű volt megérteni, a többinek meg neki kell futni többször 🙂