StackOverflow kivédése rekurziónál

Az előző cikkben rekurzióval oldottunk meg egy feladatot. Ennek keretében egy metódus folyamatosan hívta saját magát. Amikor egy metódus hív egy másikat, akkor annak adminisztrációs költsége van, ami memóriát igényel. Talán a legismertebb ebben az adminisztrációban, hogy amikor a metódus futása véget ért, a keretrendszernek/CPU-nak tudni kell, hogy melyik metódus melyik pontján kell folytatni a program futtatását (azaz honnan lett hívva a metódus). Ezt a “visszatérési címet” el kell tárolni. A két metódus kommunikációjához szintén szükség van egy közös memóriaterületre. Ez a kommunikáció foglalja magában a paraméterek átadását, visszatérési érték átadását.

Execution Stack

A mai implementációkban a szükséges memóriát a verem – más néven végrehajtási verem (execution stack) vagy hívási verem (call stack) szolgáltatja. Erről írtam korábban az értéktípusok-referenciatípusok kapcsán. Ez a verem viszont limitált méretű, főleg a teljes memóriához képest. Hogy pontosan mekkora a mérete, az sok mindentől függ – például egy új szálat indítva beállítható a Thread osztály konstruktorában. A jellemző méretek ennek ellenére viszonylag kicsik, 1-2Mb körül szóródva. Hogy ez mire elég, és mi történik, ha elfogy, próbáljuk ki egy példán.

Rekurzió és a verem határai

Tegyük fel, hogy a megoldandó feladat az, hogy számoljuk ki, hogy az 1-et, mint számot, hányszor kell összeadni, hogy megkapjuk n-et. Azonnal látszik, hogy ez egy rekurzív algoritmussal megvalósítandó feladat! A részproblémák, amit könnyen meg tudunk oldani:

  • ha n = 0, akkor az eredmény 0
  • ha n > 0, akkor már bonyolódik a helyzet. Ebben az esetben tudjuk, hogy biztosan 1-gyel többször kell összeadni, mint ha csak (n-1) lenne a célérték. Azaz például f(10) = 1 + f(9).

Erre felírhatjuk a megoldásunkat:

static uint f(uint n)
{
    if (n == 0)
        return 0;
    else
        return 1 + f(n - 1);
}

A metódust meghívva szépen meg is kapjuk az eredményt:

Console.WriteLine(f(5000));

Amire a válasz 5000.

Ha azonban erre vagyunk kíváncsiak:

Console.WriteLine(f(50000));

Akkor már a következő eredményt kapjuk:

Process is terminated due to StackOverflowException.

Látjuk tehát, hogy 50000 hívást már nem bír ki a verem. Az én konfigurációmon 37000 hívás körül fogy el a hely. Ez soknak tűnik, de a mi példánk elég speciális. Statikus metódusról van szó (nem kell adogatni a “this” paramétert), egyetlen paramétere van, amit a Jitter által fordított kód regiszterben ad át, nincsenek lokális változók. Mégis, a metódus működtetéséhez a CLR lefoglal 64 byte-ot, a szokásos regisztermentegetések felett:

push        ebp      ; 4 byte
mov         ebp,esp 
push        edi      ; 4 byte
push        esi      ; 4 byte
push        ebx      ; 4 byte
sub         esp,40h  ; 64 byte
...

A fenti kód összesen 64 + 16 byte-ot foglal a veremről, és ebben még nincs benne a visszatérési cím, ami most 32 bites módban futva 4 további byte. Így a 37000 híváshoz körülbelül 3Mb hely kellett.

Kicsit meg lehet növelni a híváslánc mélységét, ha egy szálnak nagyobb vermet adunk:

var thread = 
       new Thread( 
              _ => Console.WriteLine(f(50000)), 
              8000000); // kb 8MB verem

thread.Start();
thread.Join();

Ebben az esetben az algoritmus a végére ér.

Kapj el, ha tudsz…

További probléma a stack overlfow kivétellel kapcsolatban, hogy azt nem tudjuk elkapni. Ez a kód például nem tudja megakadályozni, hogy az alkalmazásunk kifagyjon:

try
{
    Console.WriteLine(f(300000));
}
catch
{
    Console.WriteLine("ooops..");
}

Hiába kapunk el elvileg minden exception-t, a StackOverflowException nem kapható el ilyen módon. Ez szomorú hír. Ha például egy szervizalkalmazást készítünk, aminek az API-ja rekurzív adatszerkezetet fogad a klienstől, akkor extrém esetben az input feldolgozása közben betelik a verem – és a szervíz meghal. Nem csak az adott kliens kiszolgálása, tehát adott szerviz osztály példány, hanem az egész szerviz alkalmazás, az összes éppen kapcsolatban lévő klienssel.

Ensure Sufficient Execution Stack

A szerviz példa nem véletlen, ugyanis az MVC4-es model bindereiben találtam megoldást a problémára. Az MVC4 model bindere képes rekurzív adatszerkezeteket felolvasni – és ki sem fagy, ha valaki vicces kedvében egy százezer egység mélységű családfát küld neki adatként. A trükk, amit használ, a .NET 4-gyel kibővített RuntimeHelpers osztály. Ez kapott egy EnsureSufficientExecutionStack() metódust, ami azt csinálja, amit a neve mond: ellenőrzi, hogy van-e elég hely egy átlagos metódus meghívására. Hogy pontosan mi az algoritmus, amit használ, azt nem tudom – a CLR C-ben implementált forráskódjában van az implementáció, viszont nekem csak a 2.0 rotator forráskódja van meg. Egy biztos, a következő metódussal – ami a szokásosnál jóval nagyobb mértékben falja a vermet – még biztonságosan működik:

static int f(int partialResult, int cntr, int n, 
             long a1, long a2, long a3, long a4, 
             long a5, long a6, long a7, long a8, 
             long a9, long a10, long a11, long a12, 
             long a13, long a14, long a15, long a16, 
             long a17, long a18, long a19, long a20, 
             long a21, long a22)

Hogy hogyan kell használni? Az EnsureSufficientExecutionStack() hívás, ha problémát észlel, egy saját exception-t dob el. Ez a szokásos módon elkapható. Bővítsük ki a példaprogramot a következő módon:

static uint f(uint n)
{
    if (n == 0)
    {
        return 0;
    }
    else
    {
        RuntimeHelpers.EnsureSufficientExecutionStack();
        return 1 + f(n - 1);
    }
}


static void Main(string[] args)
{
    try
    {
        Console.WriteLine(f(300000));
    }
    catch (InsufficientExecutionStackException)
    {
        Console.WriteLine("recursion failed");
    }
    catch
    {
        Console.WriteLine("ooops..");
    }
}    

Ekkor az alkalmazás már nem fagy ki, így lehetőség van a hibát kulturált módon lekezelni.

  1. #1 by Miklós Jánoska on 2013. May 17. - 13:34

    talán jobb megoldást kínál a trampoline vagy a nem igazán supportált tail recursion

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: