Laden...

StackOverflowException bei hoher Zahl an Iterationen

Erstellt von Seidenraupe vor 5 Jahren Letzter Beitrag vor 5 Jahren 1.454 Views
S
Seidenraupe Themenstarter:in
2 Beiträge seit 2018
vor 5 Jahren
StackOverflowException bei hoher Zahl an Iterationen

Ich berechne gerade Wahrscheinlichkeiten für ein bestimmtes, komplexes Würfelsystem (Gesellschaftsspiel). Dabei werden vereinfacht gesagt aktuell natürliche Zahlen von 0 bis 99999 rekursiv durchlaufen und auf nicht triviale Weise ausgewertet.

Nach 60830 Zahlenfolgen bekomme ich eine StackOverFlowException.
Es handelt sich jedoch jeweils um unterschiedliche Zahlenfolgen (habe ich im Log nachgeprüft) und daher nicht um eine Endlosschleife. Das Log läuft von 1 1 1 1 1 bis 7 1 9 3 10, dann tritt die Exception auf. Die Exception tritt auch auf, wenn ich das Log ausschalte. Wenn ich nur 10.000 Zahlenfolgen auswerte, funktioniert das Programm einwandfrei. In Zukunft soll das Programm 1.000.000.000 oder mehr Zahlenfolgen auswerten können.

Fehlermeldung:
System.StackOverflowException wurde nicht behandelt.
HResult=-2147023895
Message=Eine Ausnahme vom Typ "System.StackOverflowException" wurde ausgelöst.
InnerException:

Muss ich für ein Programm mit derartig vielen Iterationen etwas besonderes beachten? Kommt der Garbage Collector nicht so schnell hinterher?

Bei der Suche zu dem Problem habe ich nichts passendes gefunden, ich weiß allerdings auch nicht so genau, mit welchen Suchbegriffen ich am ehesten etwas passendes zum Thema finde. Der PC sollte bei so etwas doch nicht überfordert sein? Ich öffne ja keine Ressourcen pro Iteration ohne sie wieder zu schließen.

T
2.219 Beiträge seit 2008
vor 5 Jahren

Wenn du rekursiv arbeitest bedeutet das nur, dass du durch die Menge der rekursiven Methoden Aufrufe eben den Stack zum überlaufen gebracht hat.
Rekursion sollte man nur in geringen Mengen nutzen.

Ich vermute mal, dass dein Code sich auch ohne viel Aufwand auf einen iterativen Ansatz umstellen lässt.
Das dürfte dein Problem auch lösen.

Aber bitte zeig auch mal deinen aktuellen Code der knallt samt den Aufrufen.
Dann kann man dies besser einschätzen!

T-Virus

Developer, Developer, Developer, Developer....

99 little bugs in the code, 99 little bugs. Take one down, patch it around, 117 little bugs in the code.

16.807 Beiträge seit 2008
vor 5 Jahren

Muss ich für ein Programm mit derartig vielen Iterationen etwas besonderes beachten?

Ja, mit Stack<> arbeiten; dafür ist es da - denn auch .NET hat ein Stack Limit und wirft danach eine StackOverflowException.

6.911 Beiträge seit 2009
vor 5 Jahren

Hallo Seidenraupe,

Muss ich für ein Programm mit derartig vielen Iterationen etwas besonderes beachten?

Iterationen sind eher bei Schleifen angesiedelt, daher Iterationen nicht mit rekursiven Aufrufen verwechseln, denn es sind zwei Paar Schuhe.

Kommt der Garbage Collector nicht so schnell hinterher?

Bei einer StackOverFlowException mischt der Garbage Collector (GC) nicht mit, somit ist es unerheblich wie schnell er ist. Der GC ist für Daten auf dem Heap verantworlich, die von der managed Runtime alloziert werden.

Der Stack ist ein anderer Speicherbereich, bei dem es in der Natur eines Stapelspeichers nur Adress-Inkrementierung / -Dekrementierung gibt und somit kein GC nötig ist.

Für jeden Methodenauruf* werden Daten wie Rücksprungadresse, lokale Variablen, etc. auf den Stack gelegt und bei Rückkehr aus der aufgerufenen Methode wiederhergestellt. Das ist sehr effizient, aber bei vielen Methodenaufrufen, die nicht zurückkehren, kann der erlaubte Stapelspeicherbereich "überlaufen" und das äußert sich eben in einer StackOverFlowException.

* mit ein paar Ausnahmen, wie endrekursive Methodenaufrufe / inlineing außer Acht gelassen

Möglichkeiten zur Behebung / Umgehung sind somit:* iteratives Vorgehen verwenden -- wie von T-Virus vorgeschlagen

  • endrekurisves Verhalten (nicht immer leicht)
  • die Stapelspeichergröße erhöhen (ist hier aber eher ein Hack, als eine gute Lösung)

Hallo Abt,

ob Stack<T> passend ist, lässt sich nicht pauschal sagen, da der Algorithmus unbekannt ist.
Z.B. lässt sich


private static int SumRecursive(int n)
{
    if (n == 1) return 1;

    return n + SumRecursive(n - 1);
}

ohne Stack<T> in eine iterative Variante überführen:


private static int SumIterative(int n)
{
    int sum = 0;

    for (int i = 1; i <= n; ++i)
        sum += i;

    return sum;
}

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

16.807 Beiträge seit 2008
vor 5 Jahren

Den Übertrag in eine iterative Weise zweifle ich auch nicht an; aber um eine StackOverflow-Exception zu vermeiden hilft im ersten Schritt eigentlich immer Stack<>.

6.911 Beiträge seit 2009
vor 5 Jahren

Hallo Abt,

StackOverflow-Exception zu vermeiden hilft

das in meinem Kommentar oben steht 😉

Der Weg via Stack<t> ist auch nicht immer ganz einfach und da kann der Code gleich richtig geändert werden.

Siehe dazu auch Forumssuche nach hanoi

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"