[JAVA] java.lang.StackOverflowError

[xplorer87]

ciao ragazzi, mi sto cimentando con un pochettino di java e dopo un po' di mesi di inattivita' ho riaperto il buon eclipse... ma veniamo al dunque: sto scrivendo un programmino da runnare da console che opera su uno stack di oggetti, i quali ho definito io in un'apposita classe tramite una coppia (stringa, intero). ho quindi scritto una classe con un metodo che prende in ingresso una stringa in input, che ricorsivamente pusha/poppa elementi nello stack.

il codice di per se e' corretto, sia sintatticamente che semanticamente (ho verificato con successo per svariati input fino a una decina di caratteri), ma ottengo uno java.lang.StackOverflowError per input di dimensioni superiori, "come se" la jvm non ce la facesse ad eseguire tutta quella mole di calcoli (maledetta ricorsione!). c'e' un modo per ovviare a cio', magari runnando il mio codice "stand alone" (ma in java si puo'?), anziche' da dentro eclipse o facendo qualche altra cosa? ciao e grazie ^^

[cionci]

Fai troppe ricorsioni, il problema è proprio lì...e vai a pienare lo stack...

Questa è l'opzione per controllare lo stack da riga di comando: http://www.caucho.com/resin-3.0/perf...xtp#stack-size

In alternativa cerca di ridurre il numero di ricorsioni...magari posta e ci proviamo...

[xplorer87]

dunque andiamo per gradi: io provo a eseguire questo comando da console: java -Xss100m Main e ottengo nuovamente uno stack overflow, il che mi pare abbastanza impossibile se ho un input di 12 righe (e con 11, risposta istantanea senza problemi) e uno stack di 100 mega, come dovrei averlo settato. quindi probabilmente sbaglio qualcosa.

dal lato proprio algoritmico, proviamo a postare qualcosa e a commentare quello che diavolo ho combinato. il programma dovrebbe eseguire essere un parser universale per grammatiche di tipo 1. premettiamo un po' di oggetti che io ho definito ad-hoc:

Production, fatto di una coppia di stringhe (leftSide, rightSide)
Grammar, fatto di un vector di production (productionSet) e una stringa (startSymbol)
Ancestor, fatto di una coppia stringa (sententialForm) e intero (productionIndexUsedToUnfold)


poi ho definito un sententialFormStack, che e' uno Stack<Ancestor>, che e' lo stack delle sentential forms che devo controllare per verificare se una data stringa (stringToCheck) appartiene o no alla grammatica.

il metodo check prende in unput un int (scanIndex), che e' il puntatore al productionSet che mi dice da dove devo cominciare a trovare a trovare delle produzioni "buone" per unfoldare.
io faccio questo se lo stack e' vuoto cerco nel productionSet
una produzione del tipostartSymbol => sententialForm, where |sententialForm| <= |stringToCheck| (perche' sappiamo che le grammatiche di tipo uno "non si accorciano"). appena trovo una produzione "buona"
pusho nello stack l'Ancestor(startSymbol, i),
dove i ie' l'indice usato per unfoldare l'assioma della grammatica (cioe' startSymbol). poi parte una chiamata ricorsiva di check

se lo stack non e' vuoto, sono "in mezzo" al mio unfolding tree:
guardo l'elemento al top of the stack, e cerco nel productionSet delle parti sinistre (leftSide) che sono nella sententialForm corrente, cioe' quella dove sono arrivato unfoldando fino ad adesso. appena ne ho trovata una continuo ad unfoldare, controllando ogni volta se stringToCheck matcha la currentSententialForm e la pusho nello stack con l'indice della produzione che ho usato. se non riesco a trovare ulteriori produzioni per la currentStringToCheck, allora rimuovo l'elemento al top of the stack e continuo a parsare dall'indice dealla produzione che ho usato per andare nella vecchia sententialForm che ho eliminato. l'algoritmo funziona, da quello che ho potuto testare con stringhe da checkare di una decina di caratteri. il problema e' che con input piu' grossi incorro il 90% delle volte in stack overflow. ora ho qualche possibilita', apparte quella di cambiare completamente algoritmo?

public boolean check(int scanIndex)
	{
		productionSet = givenGrammar.getProductionSet();
		startSymbol = givenGrammar.getStartSymbol();
		
		if(sententialFormStack.isEmpty())
		{
			
			for (i = scanIndex; i < productionSet.size(); i++)
			{
				currentLeftSide = productionSet.elementAt(i).getLeftSide();
				currentRightSide = productionSet.elementAt(i).getRightSide();				
				
				if (currentLeftSide.equals(startSymbol) && currentRightSide.length() <= stringToCheck.length())
				{
					if(currentLeftSide.equals(stringToCheck))
					{
						return true;
					}
				
					sententialFormStack.push(new Ancestor(startSymbol, i));
					return check(0);
				}
			}
	
			return false;
		}
 
			
		else
		{
			currentSententialForm = sententialFormStack.peek().getSententialForm();
			currentScanIndex = sententialFormStack.peek().getProductionIndexUsedToUnfold();
			
			
			for(i = scanIndex; i < productionSet.size(); i++)
			{
				currentLeftSide = productionSet.elementAt(i).getLeftSide();
				currentRightSide = productionSet.elementAt(i).getRightSide();
				
			
				totalLength = currentSententialForm.length() + currentRightSide.length() - currentLeftSide.length();
					
				if(currentSententialForm.contains(currentLeftSide) && totalLength <= stringToCheck.length())
				{
					newSententialForm = currentSententialForm.replaceFirst(currentLeftSide, currentRightSide);
					
					
					if(newSententialForm.equals(stringToCheck))
					{
						return true;
					}
					
					sententialFormStack.peek().setProductionIndexUsedToUnfold(i);
					sententialFormStack.push(new Ancestor(newSententialForm, -1));
					
					return check(0);
				}
			}
			
			
			if(currentSententialForm.equals(startSymbol))
			{
 
				return false;
			}
			
			sententialFormStack.removeElementAt(sententialFormStack.size()-1);
			currentScanIndex = sententialFormStack.peek().getProductionIndexUsedToUnfold();
			sententialFormStack.peek().setProductionIndexUsedToUnfold(-1);
 
			return check(currentScanIndex+1);
			
		}
	}

[cionci]

Prova a stampare la profondità della ricorsione e verifica che non cambi con la modifica della dimensione dello stack (non metterla 100 mega, ma prova qualcosa come 2048K o 4096k)...

[xplorer87]

mh, come faccio a "stampare la profondita' della ricorsione"? comunque con il comando java -Xss2048m Main oppure java -Xss4096m Main l'esito del programma non cambia (sempre stackoverflow per input grandi o risultato corretto per input piccoli).

[cionci]

k non mega... -Xss2048k

Per stampare la profondità della ricorsione basta fare questo:

public boolean check(int scanIndex, int depth)
{
//stampa depth
depth++; //poi lo passi nelle varie ricorsioni

Chiaramente la prima chiamata di check dovrà essere fatta con depth a 0...

[PGI-Bis]

Rispondo qua perchè a tenere gli occhi su due forum viene quello strabismo che se non sei Venere fa un po' impressione .

Dimmi che usi una versione di Java precedente all'attuale (6) su Windows XP.

Se così fosse allora potresti aver incontrato il bug 6316197: l'opzione -Xss non altera la dimensione predefinita dello stack per il Thread main.

Se così fosse allora dovresti poter risolvere cambiando il main da un ipotetico:

public static void main(String[] args) {
   primoMetodo();
}

a

public static void main(String[] args) {
    new Thread() {
        public void run() {
            primoMetodo();
        }
    }.start();
}

Comunque consiglio il passaggio alla versione iterativa.

[xplorer87]

dunque, grazie mille pgi, facendo come da te suggerito (infatti uso java 5 su xp, a proposito, la 6 come va?) sono riuscito ad aumentare lo stack a piacere e quindi ad evitare lo stack overflow. inoltre, sempre come da te suggerito, ho riscritto questa vista DFS (perche' e' questo in realta') secondo un algoritmo iterativo, che sebbene non abbia assolutamente problemi di stack overflow, e' un po' meno performante di quello ricorsivo, che e' comunque molto esoso in termini di memoria (stack).

altri consigli?

[PGI-Bis]

Stando alla bug-parade il problema è stato risolto in Mustang. La sua JVM, tra l'altro, ha performance che mettono in serio imbarazzo le sue progenitrici. Puoi provare a vedere come se la cava col tuo codice.

Nel valutare le performance di un algoritmo del genere occorre andare coi piedi di piombo. C'è una soglia minima di invocazioni (predefinita in 1000 per la JVM client, 10.000 per quella server) necessaria prima che il compilatore HotSpot produca una versione in codice macchina dei metodi coinvolti. E' ben possibile che si noti un'apprezzabile differenza passando dall'uso di una stack "nativa", quale lo stack frame dei Thread, ad una Java, che è possibile tu abbia usato per la versione iterativa. Tale differenza, tuttavia, dovrebbe valere solo per i primissimi tentativi, dopo i quali dovresti notare un crollo verticale dei tempi di esecuzione.

Naturalmente sarò dragicamente smentito da un "ho provato due volte di seguito e fa schifo lo stesso"

P.s.: se puoi scrivi che hai trovato una soluzione anche nell'altro forum, così resta come documentazione ad uso di quanti incontrino problemi simili.