Megoldás

Szóval ott tartottam hogy Scala és Java programkódokat hasonlítgatok össze, ami egy tömbben egy adott karakter előfordulásait számolja meg. Egy szerény 30 millió karakteres tömbön próbálgattam a négyféle programkódot, amit az előző post-ban fabrikáltam össze tegnapelőtt: Volt sima for ciklusos és rekurzív algoritmus Java-ban és Scala-ban is.

Nézzük hogyan muzsikáltak:

Az első sima Java megoldás (1.) kb 160 ezredmásodperc alatt birkózik meg a feladattal. A Scala program, amibe a Java imperativizmusát másoltam le (2.), 1200 ezredmásodpercig dolgozik ugyanezen. Ez egyáltalán nem elhanyagolható különbség, de mégegyszer hangsúlyoznám, hogy ész nélkül írtam át a Java kódot Scala-ba: Egyszer talán majd pörgök egy post-ot ezen a különbségen is, de alapvetően "nem érdekel ez most engem".

Következőnek a (4.) Java programkódot tárgyalom ki, amit kvázi funkcionálisan írtam meg, rekurziót használva, viccből. Na ez már hatezer karakteres bemeneti karaktertömbnél is csúnyán elcsattan StackOverflowError-ral. Ha ismerjük a rekurzió működését, -azaz hogy a program minden egyes függvényhívásnál felépít egy stack frame-et- ez nem is túl meglepő. Ahány karakter, annyi stackframe: a verem hamar felzabálja a memóriát.

Végül jöjjön a (3.) funkcionális Scala program, ami a 4.-eshez hasonlóan rekurziót használ. Ez viszont nem száll el StackOverFlowError-ral, sőt egész jó időt hoz, kb. 160 ezredmásodpercet. Csak kicsivel lassabb mint a legelső kód. Hogyan lehet ez?

A megoldás kulcsa a farokrekurzió és annak kioptimalizálása. A dolog lényege, hogy a rekurzív függvény legutolsó művelete saját magának a meghívása. Még általánosabban, ha egy függvény utolsó művelete egy másik függvény meghívása (Tail Call). Ilyenkor levezethető, hogy a legutolsó stackframe újrafelhasználható, vagy legalábbis eldobható a következő függvény meghívása előtt. A jelenlegi Java-t futtató JVM implementáció nem támogatja ezt a feature-t. Vannak rá törekvések, ami talán új bájtkód prefixet is szükségessé tenne, de ez nem a közeljövőben fog megvalósulni. Biztonsági kérdések is felmerülnek, mert a Java nem optimalizálhatja ki csak úgy a stack frame-eket. Kivétel dobásánál vagy hozzáférési jogosultság ellenőrzésnél nem szerencsés ha hiányoznak frame-ek. A ScalaByExample.pdf -ami külön fejezetet szán ennek a magyarázatára- megemlíti hogy a Scala esetében farokrekurzió optimalizására lehet építeni, de a stackoverflow-n találtam még két kitételt ezen felül: Csak lokális vagy final függvények esetében.

Aki arra is kíváncsi hogy a Scala (valószínűleg) hogyan oldja meg, illetve hogyan oldható ez meg magas szinten egy nyelv meglévő elemeivel a program átírásával de az algoritmus jellegének megtartásával, az itt találhat egy kimerítő leírást róla. Elég messziről indul és körmönfont példát hoz, de egyébként nem egy bonyolult dolog. Hasonlít a Command Pattern-re.

Egyébként ezzel az egésszel csak arra akartam megnyugtató választ kapni, hogy a Scala-ban előszeretettel használt tail rekurzió megállja-e a helyét gyári környezetben. A válasz: igen.