Javascript:stack overflow bei Rekursion

[BlueJay]

Hallo Leute,

da ist so ein Progrämmchen, was mir ein 3D-Labyrinth erstellen soll mit folgendem Algo:


// 1. alle Raeume ohne Durchgang kreieren
// 2. Start in beliebigem Raum
// 3. Weg bahnen: ist ein beliebiger der Nachbarraum ohne Gang, Weg dahin bahnen,
// sonst den bisher gebahnten Weg zurückgehen, bis ein unberührter Nachbarraum vorhanden ist,
// 4. weiter mit 3, bis kein Weg bahnen mehr möglich ist.


Mit Firefox3.0b5/Linux läuft das Ganze problemlos, aber mit Konqueror 3.8.5 und IE6/Wine scheitert das Ganze kläglich bei der Rekursion, dann gibt es bei größeren Systemen den Stack Overflow.

Der verantwortliche Codeteil dazu:

function weg_bahnen(ind)
{ var i=-1;
get_nachbar(ind);
if (liste[0]>0)
{ i=liste[Math.floor(liste[0]*Math.random())+1]; // einen Nachbarn herauspicken
// Nachbarschaft bestimmen, Wände öffnen:
if (i==ind-1) { f[ind]=f[ind]+8; f[i]=f[i]+2; } // links
else if (i==ind+1) { f[ind]=f[ind]+2; f[i]=f[i]+8; } // rechts
else if (i==(ind-xmax)) { f[ind]=f[ind]+1; f[i]=f[i]+4; } // vorne
else if (i==(ind+xmax)) { f[ind]=f[ind]+4; f[i]=f[i]+1; } // hinten
else if (i==(ind-xmax*ymax)) { f[ind]=f[ind]+32; f[i]=f[i]+16; } // oben
else if (i==(ind+xmax*ymax)) { f[ind]=f[ind]+16; f[i]=f[i]+32; } // unten
else alert('Fehler bei Nachbarbestimmung Zelle '+ind+' nach '+i);
add_liste(i,gang);
}
else
{ do
{ gang[0]--;
if (gang[0]>0) get_nachbar(gang[gang[0]]);
}
while ((liste[0]==0) && (gang[0]>0));
if (gang[0]>0) i=gang[gang[0]];
}
if (i>=0) weg_bahnen(i);
}

liste ist ein counted array, global, und wird mit get_nachbar gefüttert.
gang ist auch ein globales counted array, was sich die Verzweigungen merkt.
Beide können nicht über xmax*ymax*zmax+1 (Zellenanzahl+1) hinaus wachsen.
Ja, und dann sind da noch die xmax*ymax*zmax Zellen im globalen Array f.

Bisher versucht, aber ohne Erfolg:
1. Variable i als outer_i global gemacht
2. Schwanz geändert in obigen Quellcode, die Absprünge in die Rekursion waren vorher jeweils am Ende der äußeren if-else-Blöcke

Da ergab sich aber auch *exakt* das gleiche Verhalten bei der Rekursion: Firefox war kein Thema, den habe ich bis zu 4600 Zellen gequält, Konqueror und IE6 machten jedoch nach 450, spätestens 480 Zellen schlapp.

Das Programm dazu:
Labyrinth-Generator 3D (http://www.gamecraft.de/tools/laby3d/index.htm)

Irgendwelche Ideen, wie man den beiden eine ähnliche Performance wie dem Firefox beibringen kann?

so long,
BlueJay

[undefined]

Ich glaube das das liegt an der Zeichenkettenlänge.
Ich hatte schon mal ein ähnliches Problem mit json und grossen Array's bei Konqueror/Opera und IE.
Jetzt frag mich aber nicht wo die Grenze war, das ist schon ne weile her.
Als Referenz nehme am besten die limits von C.

grep --color=auto MAX /usr/include/limits.h

[BlueJay]

Hm, in meiner limits.h (x-86) steht nicht so das Richtige drin. Die Pointer reichen jedenfalls doppelt und dreifach.

Mit etwas mehr Sahne, äh RAM, kann man beim Konqueror das Doppelte rauskitzeln, aber vom FF trennen ihn noch Welten!

Ich vermute, dass Firefox eine andere, bessere Stackbehandlung hat. Der meckert eher über zuwenig Rechenzeit als dass er einen Stack overflow bringt. Hat an einem 24x24x24er Labyrinth 2 Minuten lang herumgerechnet. :cool:

Ist tail-recursion optimization bei den anderen Browsern verlorene Liebesmüh'?

[BlueJay]

.. und noch so ein Schwächeanfall vom Konqueror:

FF3 und Konqueror 3.5.6 wurden zunächst mit Permutationen eines 8 Elemente enthaltenen Vektors gequält, dann wurden die Ergüsse mit dingsbums.sort() in Reihenfolge gebracht.

FF3 nagte ziemlich an den Daten rum, brachte aber dann das sortierte Ergebnis korrekt bis zum 40320. Datensatz.

Das Konqueror-Array.sort() scheiterte kläglich am 10 000. Datensatz, die vorangegangene Permutation konnte er immerhin noch innerhalb 1 Minute durchziehen.

:rolleyes: