Wie viele sind zu viele verschachtelte Funktionsaufrufe?

15

Zitiert von MSDN über StackOverflowException :

Die Ausnahme, die ausgelöst wird, wenn der Ausführungsstapel überläuft, weil er zu viele verschachtelte Methodenaufrufe enthält.

Too manyist hier ziemlich vage. Woher weiß ich, wenn zu viele wirklich zu viele sind? Tausende Funktionsaufrufe? Millionen? Ich gehe davon aus, dass es in irgendeiner Weise mit der Größe des Arbeitsspeichers im Computer zusammenhängt, aber ist es möglich, eine ungefähr genaue Größenordnung zu finden?

Ich mache mir darüber Sorgen, weil ich ein Projekt entwickle, bei dem rekursive Strukturen und rekursive Funktionsaufrufe häufig verwendet werden. Ich möchte nicht, dass die Anwendung versagt, wenn ich sie für mehr als nur kleine Tests benutze.

.net exceptions recursion stackoverflow Marco-Fiset
quelle
4
Es ist relativ einfach, eine rekursive Funktion in eine nicht rekursive Funktion umzuwandeln. Kleben Sie einfach Ihre Daten auf ein Stack<T>.
Brian
1
Wie groß "zu viele" sind, können Sie selbst bestimmen. Verwenden Sie für .NET editbin /stack:WHATEVER-NUMBER-YOU-LIKE yourexefile.exe.
SK-logic

Antworten:

28

Ich mache mir darüber Sorgen, weil ich ein Projekt entwickle, bei dem rekursive Strukturen und rekursive Funktionsaufrufe häufig verwendet werden. Ich möchte nicht, dass die Anwendung versagt, wenn ich sie für mehr als nur kleine Tests benutze.

Es sei denn , Ihre Sprachumgebung unterstützt Endrekursion Optimierung (und Ihre Rekursion ist ein Endaufruf), eine Faustregel ist: Rekursionstiefe sollte O (log n), dh unter Verwendung von Algorithmen oder Datenstrukturen gewährleistet werden , auf der Grundlage sein divide-and Erobern (wie Bäume, die meisten Sortieralogorithmen usw.) ist in Ordnung, aber alles, was linear ist (wie rekursive Implementierungen der Behandlung verknüpfter Listen), ist es nicht.

Michael Borgwardt
quelle
3
+1. Sehr gute Antwort, ich habe diese Regel implizit angewendet, war mir aber nicht bewusst.
Giorgio
In der heutigen Zeit wird praktisch jeder Compiler in Produktionsqualität, der das Adjektiv verdient, die Optimierung von Tail Calls unterstützen.
John R. Strohm
1
@ JohnR.Strohm Allerdings hat das OP die Frage .NET markiert, sodass AFAIK im Moment nur den 64-Bit- Jitter zur Tail-Call-Optimierung nutzt.
Mark Hurd
1
Nur damit es keine Verwirrung gibt, ehren sowohl x86 als auch x64 immer den "Schwanz" der CIL. Anweisungspräfix. Zusammenfassend lässt sich sagen, dass in .NET-Land F # die Tail-Call-Optimierung abschließt, C # nicht und der x64-Jitter, wenn es "einfach" ist (davon kann nicht abgewichen werden). Siehe blogs.msdn.com/b/clrcodegeneration/archive/2009/05/11/…
Stephen Swensen
1
Richtig, aber in einigen Fällen, wie in einem berüchtigten IIS, der ASP.NET hostet, kann sogar eine reine O (log n) -Rekursionstiefe aufgrund ihrer pathetischen, ungerechtfertigten, lächerlichen winzigen Stapeltiefenbeschränkung fehlschlagen, die so ziemlich jede Rekursion (oder Rekursion) verursacht sogar eine lange Kette von nicht rekursiven verschachtelten Aufrufen ist unmöglich. Die einzige Möglichkeit besteht darin, die iis-Binärdatei selbst zu bearbeiten.
SK-logic
17

Standardmäßig weist die CLR dem Stapel für jeden Thread 1 MB zu (siehe diesen Artikel ). Es sind jedoch viele Anrufe erforderlich, um diesen Betrag zu überschreiten. Dies hängt davon ab, wie viel Speicherplatz auf dem Stack von jedem Aufruf für Parameter und lokale Variablen verwendet wird.

Sie können es sogar StackOverflowExceptionmit einem einzigen Anruf zum Werfen bringen , wenn Sie bereit sind, etwas unorthodox zu sein:

private static unsafe void BlowUpTheStack()
{
    var x = stackalloc byte[1000000000];
    Console.WriteLine("Oh no, I've blown up the stack!");
}
Cole Campbell
quelle
Leider wird häufig gegen diese vernünftige Vorgabe verstoßen (z. B. in asp.net).
SK-logic
2

Da Cole Campbell die Speichergröße und Michael Borgwardt die Tail-Call-Optimierung bemerkte, werde ich diese nicht behandeln.

Zu beachten ist auch CPS, mit dem mehrere verwobene Funktionen optimiert werden können, während die Tail-Call-Optimierung für einzelne Funktionen vorgesehen ist.

Sie können den Stapel wie hier vergrößern und sich darüber im Klaren sein, dass 64-Bit-Code den Stapel schneller als 32-Bit-Code auffrisst.

Bemerkenswert ist, dass wir eines der Beispiele unter F # Interactive mehr als 40 Stunden lang ausgeführt haben, ohne den Stapel zu sprengen. Ja, es war ein Funktionsaufruf, der von selbst kontinuierlich bis zum erfolgreichen Abschluss lief.

Wenn Sie eine Codeabdeckung durchführen müssen, um herauszufinden, wo die Probleme auftreten, und keine Codeabdeckung mit VS haben, die Sie verwenden können, verwenden Sie TestDriven.NET

Guy Coder
quelle