Néhanapján szükségünk lehet arra, hogy megnézzük, pontosan milyen kód is generálódik a kódunkból. Ez egyrészt hasznos tud lenni hibák felderítéséhez is, de amihez még inkább hasznos, az a feltételezések tisztázása. C++ esetén régóta létezik a Compiler Explorer (https://godbolt.org/), ami assembly kód szinten mutatja meg, hogy mit is generálnak különböző C++ fordítók a kódból.
C# esetén viszont nem igen volt lehetőségünk eddig hasonlóra, mivel a köztes kódból JIT fordítással keletkezik natív kód. Köztes kód visszafejtésére, megtekintésére eszköznek ott van a korábban ismertetett IL Spy. Viszont a nemrég elindult https://sharplab.io/ oldalon megnézhetjük, hogy a C# kódunkból milyen köztes kód keletkezik és azt, hogy ez natív assembly szinten milyen kód formájában realizálódik. Mindemellett megnézhetjük, hogy a C# újabb nyelvi verzióiban található szolgáltatások/újdonságok (Pl. Record típusok) milyen C# kódot generálnak fordítás előtt valójában.
Ahogy említettem, az ilyen oldalak azért hasznosak, mert feltételezések tisztázásra nagyon jók. Nézzünk is egy ilyent meg. A rekurzió kapcsán említésre került, hogy nem igen ajánlatosak sok iteráció esetén, mert hajlamosak teleszemetelni a stack-et és ennek StackOverflowException kivétel lehet az eredménye. Fontos megjegyezni, hogy csak lehet, de nem biztos.
A könyv olvasásának ezen pontján már azt is tudjuk, hogy amit rekurzióval meg lehet írni, azt meg lehet írni ciklusokkal is. Jogosan felmerülhet ekkor a kérdés, hogy akkor a fordító miért nem generál nekünk a rekurzív kódból ciklusokat? A válasz biztosan nem az, amire számítunk, mert valójában ciklusokat eredményez a rekurzív kód is, ha lehetséges az átalakítása.
Ezt az optimalizációt tail call elimination-nek nevezi a szakirodalom és a legtöbb modern fordító támogatja. A .NET JIT fordítója a Core 3.0 óta rendelkezik ezzel az optimalizációval. Ennek a lényege, hogy a metódus hívás CALL assembly utasítását kicseréljük egy szimpla ugró (JMP) vagy feltételes (JNZ vagy JZ) utasításra, ami a metódus elejére ugratja a végrehajtást. Így lényegében egy ciklus lesz a rekurzív hívásunkból.
Nézzünk egy klasszikus rekurzív példát, ami a Fibonacci sorozat i. elemét határozza meg. Rekurzívan valami hasonló implementációt tudunk készíteni:
public class Example
{
public int Fibonacci(int i)
{
if (i == 0)
return 0;
else if (i == 1)
return 1;
else
return Fibonacci(i - 1) + Fibonacci(i + 1);
}
}
Ez a Sharplab segítségével visszafejtve az alábbi x64 Assembly kódban fog realizálódni:
Example.Fibonacci(Int32)
L0000: push rdi
L0001: push rsi
L0002: push rbx
L0003: sub rsp, 0x20
L0007: mov rdi, rcx
L000a: mov esi, edx
L000c: test esi, esi
L000e: jne short L001a
L0010: xor eax, eax
L0012: add rsp, 0x20
L0016: pop rbx
L0017: pop rsi
L0018: pop rdi
L0019: ret
L001a: cmp esi, 1
L001d: jne short L002c
L001f: mov eax, 1
L0024: add rsp, 0x20
L0028: pop rbx
L0029: pop rsi
L002a: pop rdi
L002b: ret
L002c: lea edx, [rsi-1]
L002f: mov rcx, rdi
L0032: call 0x00007ffcbd0c0018
L0037: mov ebx, eax
L0039: lea edx, [rsi+1]
L003c: mov rcx, rdi
L003f: call 0x00007ffcbd0c0018
L0044: add eax, ebx
L0046: add rsp, 0x20
L004a: pop rbx
L004b: pop rsi
L004c: pop rdi
L004d: ret
A kódban jól látható kettő darab call 0x00007ffcbd0c0018 utasítás, ami a rekurzív hívásunk és az is szépen látható, hogy a kód tele van push és pop stack kezelő utasításokkal. Könnyű belátni, hogy a fenti kód elég nagy szám esetén (pl. int.MaxValue) StackOverflowException kivétellel jutalmaz minket eredmény helyett.
A Tail call elimination optimalizációhoz módosítsuk kicsit a metódusunkat, méghozzá úgy, hogy a rekurzív hívások számítására bevezetünk egy változót, ami a példában az accumlator nevet kapja és 0 alapértelmezett értékkel indul. Ennek a számlálónak az értéke növekszik, ha a FibonacciTail metódus saját magát hívja rekurzívan, és értéke pedig csökken, ha a metódus értéket ad vissza:
public class Example
{
public int FibonacciTail(int i, int accumlator = 0)
{
if (i == 0)
return accumlator;
else if (i % 2 == 0)
return FibonacciTail(i - 1, accumlator + i);
else
return FibonacciTail(i - 1, accumlator);
}
}
A kód ezen a szinten ugyanúgy rekurzívnak tűnik, de nézzük meg, hogy milyen kód is generálódik:
Example.FibonacciTail(Int32, Int32)
L0000: test edx, edx
L0002: je short L0014
L0004: test dl, 1
L0007: jne short L0010
L0009: add r8d, edx
L000c: dec edx
L000e: jmp short L0000
L0010: dec edx
L0012: jmp short L0000
L0014: mov eax, r8d
L0017: ret
Ami elsőre feltűnhet, hogy a metódus jóval kompaktabb assembly kódban realizálódott, ami azt jelenti, hogy kevesebb utasítás kell a lefuttatásához, tehát gyorsabb, mint amiből kiindultunk. További érdekesség, hogy a generált kódban sehol nincs call utasítás, helyettük kettő jmp utasítás található, ami azt jelenti, hogy a rekurzív metódusunkból lett egy ciklikusan futó kód.
A tanulság
A tanulság az, hogy néha hasznos lehet megtekinteni a generált natív kódot, mivel sok érdekességet lehet benne felfedezni és tanulásnak sem rossz. A másik fontos tanulság, hogy a rekurzió nem mindig jelent rosszat. Bár ennek kapcsán megjegyezném, hogy nem minden rekurzív metódust lehet átalakítani hasonló módon, illetve mindig érdemes gondolni az olvashatóságra. Az olvashatóság és megérthetőség különösen fontos lehet, ha többen dolgoznak egy projekten. Ilyen szituációkban könnyen lehet, hogy más fogja a kódunkat karbantartani és ő nem biztos, hogy tisztában lesz az ilyen trükkökkel. Éppen ezért a látottak ellenére igyekezzünk nem rekurzív megoldásokban gondolkodni, ha lehet, vagy legalább kommentáljuk a kódunknak az ilyen egzotikus részeit.