Rekursion und StackOverflow

[Scamas]

ich implementiere gerade einen rekursiven region growing algorithmus. allerdings wird bereits nach ~5000 offenen methoden aufrufen ein StackOverflowError geworfen. ich habe sowas früher schon mal mit c++ und visual studio gemacht... dort hatte man die möglichkeit einen größeren stack für die applikation zu verwenden. geht das in java auch? bzw. welche möglichkeiten habe ich, um dieses problem zu lösen?

debian linux / java 6 / eclipse

 

[Marco13]

http://java.sun.com/j2se/1.3/docs/tooldocs/solaris/java.html#options

java -Xms6m TheProgram

Du solltest das ganze aber besser iterativ machen....

 

[Scamas]

kommt noch ^^ ... ich implementiere sowohl rekursion als auch iterativ und führe einige vergleiche durch

danke für die schnell antwort

 

[Scamas]

hmm... auf den ersten blick ganz toll, auf den zweiten hats aber nahezu nichts gebracht... nun sind immerhin schon ~6000 aufrufe nötig bis die exception fliegt... scheinbar ist rekursion im bereich bildverarbeitung mit java nicht optimal/unbrauchbar

 

[maki]

Rekursion ist Rekursion, egal um was es geht.

Das Rekursion zwar im Code viel aussagen kann ist bekannt, aber auch das die Stackframes begrenzt sind, auf jeder Plattform und Programmiersprache.

Das allseits bekannte Gegenmittel: Iteration anstatt Rekursion.
Läuft auch schneller 😉

 

[Marco13]

Ja, du kannst ja auch
java -Xms600m TheProgram
machen, aber irgendwann wird's sinnlos - insbesondere, weil das so klingt, als ob der Speicherplatzbedarf nicht linear, sondern polynomial (oder sogar exponentiell?) ist....

 

[Scamas]

ich nochmal...

ich habe mittlerweise zwar einen iterativen algorithmus als alternative, jedoch kann ich mir absolut nicht vorstellen, das java bei rekursion derart versagt.

das java kommando -Xms6m bewirkt rein gar nichts in bezug auf eine mögliche rekursionstiefe. der kurzzeitige eindruck dies würde ewas bringen erwies sich recht schnell als falsch.

hab ich irgendwas elementares übersehen?

für weitere ideen bin ich dankbar...

 

[maki]

jedoch kann ich mir absolut nicht vorstellen, das java bei rekursion derart versagt.

Natürlich kannst du dir das nicht vorstellen, ist ja auch absoluter quatsch, dachte ich hätte das schon erklärt...

Schau doch mal hier rein: http://www.java-forum.org/de/viewtopic.php?t=67967&highlight=xss

 

[SlaterB]

warum tust du das so als Quatsch ab, hast du das schon getestet?
also ich kann diese Optionen auch nicht wirklich nachvollziehen,

java -Xss999 läuft bei mir nicht,
java -Xss1000 bis zu 262M läuft, hat aber anscheinend keine Auswirkung auf den Stack,
mit anderen Parametern verschieben sich die Grenzen etwas (z.B. kann ich nachvollziehen, dass bei
-Xmx1024m Xss nur bis 110m geht, wie im anderen Thread angegeben),
ein Sinn oder wenigstens eine Auswirkung ist aber nicht zu erkennen,

mein Programm läuft immer bis x= 5128

public class Test
{

    public static void main(String[] args)
        throws Exception
    {
        try
        {
            doSomething(0);
        }
        catch (Throwable t)
        {
            // sonst Spam der Fehlermeldung
        }
    }

    static void doSomething(int x)
    {
        System.out.println("x: " + x);
        doSomething(x + 1);
    }
}

 

[maki]

Quatsch deswegen, weil die Aussage das "Java keine Rekursion kann" imho nix anderes ist 😉

Nach ein bisschen Nachforschen kam heraus, das Java unter Windows einen "Bug" hat, der dafür sorgt, dass der Xss Parameter nur bei neuen Threads zieht.

http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4689767

So geht's auch unter Windows:

package test;

public class RekursionsTest implements Runnable{


	public static void main(String[] args)
	throws Exception
	{
		try
		{    	  
			(new Thread(new RekursionsTest())).start();
		}
		catch (Throwable t)
		{
			System.out.println(t);
		}
	}


	void doSomething(int x)
	{
		System.out.println("x: " + x);
		doSomething(x + 1);
	}

	public void run() {
		doSomething(0);
	}

}

Hab ich bei ca. 1.5 Millionen manuell abgebrochen, da es funzt.

 

[SlaterB]

ah, sehr interessante Info, danke

 

[maki]

Muss zugeben, dass ich mich auch sehr gewundert habe, aber erst als ich es ausprobiert habe... (schäm)