Ile jest za dużo zagnieżdżonych wywołań funkcji?

15

Cytat z MSDN na temat StackOverflowException :

Wyjątek zgłaszany, gdy stos wykonania przepełnia się, ponieważ zawiera zbyt wiele zagnieżdżonych wywołań metod.

Too manyjest tu dość niejasne. Skąd mam wiedzieć, kiedy za dużo to naprawdę za dużo? Tysiące wywołań funkcji? Miliony? Zakładam, że musi to być w jakiś sposób związane z ilością pamięci w komputerze, ale czy można wymyślić mniej więcej dokładny rząd wielkości?

Martwię się tym, ponieważ rozwijam projekt, który wymaga intensywnego wykorzystania struktur rekurencyjnych i wywoływania funkcji rekurencyjnych. Nie chcę, aby aplikacja uległa awarii, gdy zacznę jej używać do więcej niż tylko małych testów.

.net exceptions recursion stackoverflow marco-fiset
źródło
4
Stosunkowo łatwo jest przekonwertować funkcję rekurencyjną na funkcję nierekurencyjną. Po prostu przyklej swoje dane do Stack<T>.
Brian
1
To, jak duże jest „zbyt wiele”, zależy wyłącznie od Ciebie. W przypadku .NET użyj editbin /stack:WHATEVER-NUMBER-YOU-LIKE yourexefile.exe.
SK-logic

Odpowiedzi:

28

Martwię się tym, ponieważ rozwijam projekt, który wymaga intensywnego wykorzystania struktur rekurencyjnych i wywoływania funkcji rekurencyjnych. Nie chcę, aby aplikacja uległa awarii, gdy zacznę jej używać do więcej niż tylko małych testów.

O ile twoje środowisko językowe nie obsługuje optymalizacji ogona (a twoja rekurencja jest ogonem), podstawową zasadą jest: głębokość rekurencji powinna być równa O (log n), tj. Przy użyciu algorytmów lub struktur danych opartych na podziale i podbijanie (jak drzewa, większość alogorytmów sortujących itp.) jest OK, ale nic liniowego (jak rekurencyjne implementacje obsługi połączonych list) nie jest.

Michael Borgwardt
źródło
3
+1. Bardzo dobra odpowiedź, domyślnie używałem tej reguły, ale nie byłem jej świadomy.
Giorgio
W dzisiejszych czasach niemal każdy kompilator jakości produkcyjnej, warty użycia przymiotnika, będzie wspierał optymalizację wezwania ogona.
John R. Strohm,
1
@ JohnR.Strohm Jednak OP oznaczył pytanie .NET, więc AFAIK tylko 64-bitowy fluktuacja obecnie optymalizuje wywołania ogonowe.
Mark Hurd,
1
Aby nie było pomyłek, zarówno x86, jak i x64 zawsze honorują „ogon” CIL. przedrostek instrukcji. Podsumowując, na platformie .NET F # wykonuje optymalizację wywołania ogona, C # nie, a jitter x64 robi, jeśli jest „łatwy” (nie można na nim polegać). Zobacz blogs.msdn.com/b/clrcodegeneration/archive/2009/05/11/…
Stephen Swensen,
1
To prawda, ale w niektórych przypadkach, na przykład w niesławnym programie IIS obsługującym ASP.NET, nawet zwykła głębokość rekurencji O (log n) może się nie powieść z powodu ich żałosnego, nieuzasadnionego, śmiesznego ograniczenia niewielkiej głębokości stosu, co powoduje prawie każdą rekurencję (lub nawet długi łańcuch nierekurencyjnych połączeń zagnieżdżonych) niemożliwe. Jedynym sposobem jest edytowanie samego pliku binarnego iis.
SK-logic
17

Domyślnie CLR przydziela 1 MB do stosu dla każdego wątku (zobacz ten artykuł ). Tak więc, tyle połączeń potrzeba, aby przekroczyć tę kwotę. To będzie się różnić w zależności od ilości miejsca na stosie, które każde wywołanie wykorzystuje na takie parametry, jak parametry i zmienne lokalne.

Możesz nawet sprawić, że rzucisz StackOverflowExceptionjednym telefonem, jeśli chcesz być trochę niekonwencjonalny:

private static unsafe void BlowUpTheStack()
{
    var x = stackalloc byte[1000000000];
    Console.WriteLine("Oh no, I've blown up the stack!");
}
Cole Campbell
źródło
Niestety, ta rozsądna wartość domyślna jest często naruszana (np. W asp.net).
SK-logic
2

Ponieważ Cole Campbell zauważył rozmiar pamięci, a Michael Borgwardt zauważył optymalizację połączeń ogonowych, nie będę ich opisywał.

Inną rzeczą, o której należy pamiętać, jest CPS, którego można użyć do optymalizacji kilku przeplecionych funkcji, w których optymalizacja wywołania ogona dotyczy pojedynczych funkcji.

Możesz zwiększyć rozmiar stosu, tak jak my tutaj , i pamiętaj, że 64-bitowy kod zjada stos szybciej niż kod 32-bitowy.

Warto zauważyć, że uruchomiliśmy jeden z przykładów pod interaktywnym F # przez ponad 40 godzin bez wysadzenia stosu. Tak, było to jedno wywołanie funkcji, które samo działało nieprzerwanie do pomyślnego zakończenia.

Ponadto, jeśli musisz zrobić pokrycie kodu, aby dowiedzieć się, gdzie występują problemy i nie masz pokrycia kodu VS, możesz użyć TestDriven.NET

Guy Coder
źródło