Сколько слишком много вложенных вызовов функций?

15

Цитируется из MSDN о StackOverflowException :

Исключение, которое выдается при переполнении стека выполнения, поскольку он содержит слишком много вложенных вызовов методов.

Too manyздесь довольно расплывчато Как я знаю, когда слишком много на самом деле слишком много? Тысячи вызовов функций? Миллионы? Я предполагаю, что это должно быть каким-то образом связано с количеством памяти в компьютере, но возможно ли придумать примерно точный порядок величины?

Я обеспокоен этим, потому что я разрабатываю проект, который включает интенсивное использование рекурсивных структур и рекурсивных вызовов функций. Я не хочу, чтобы приложение не работало, когда я начинаю использовать его не только для небольших тестов.

марко-fiset
источник
4
Относительно легко преобразовать рекурсивную функцию в нерекурсивную функцию. Просто прикрепите свои данные к Stack<T>.
Брайан
1
Насколько велико «слишком много», зависит только от вас, чтобы определить. Для .NET используйте editbin /stack:WHATEVER-NUMBER-YOU-LIKE yourexefile.exe.
SK-logic

Ответы:

28

Я обеспокоен этим, потому что я разрабатываю проект, который включает интенсивное использование рекурсивных структур и рекурсивных вызовов функций. Я не хочу, чтобы приложение не работало, когда я начинаю использовать его не только для небольших тестов.

Если ваша языковая среда не поддерживает оптимизацию хвостовых вызовов (а ваша рекурсия - это хвостовой вызов), основное практическое правило: глубина рекурсии должна быть гарантированно равна O (log n), т. Е. С использованием алгоритмов или структур данных, основанных на разделяющем и conquer (например, деревья, большинство алгоритмов сортировки и т. д.) - это нормально, но все линейное (например, рекурсивные реализации обработки связанных списков) - нет.

Майкл Боргвардт
источник
3
+1. Очень хороший ответ, я неявно использовал это правило, но я не знал об этом.
Джорджио
В наши дни практически любой компилятор производственного качества, достойный прилагательного, будет поддерживать оптимизацию хвостовых вызовов.
Джон Р. Штром
1
@ JohnR.Strohm Однако ОП пометил вопрос .NET, поэтому AFAIK только 64-битный джиттер в данный момент выполняет оптимизацию вызовов.
Марк Херд
1
Просто чтобы не было путаницы, и x86, и x64 всегда чтят "хвост" CIL. префикс инструкции Подводя итог, можно сказать, что в среде .NET F # выполняет полную оптимизацию хвостового вызова, а C # - нет, а x64 выполняет джиттер, если он «прост» (от него нельзя зависеть). См. Blogs.msdn.com/b/clrcodegeneration/archive/2009/05/11/…
Стивен Свенсен
1
Да, но в некоторых случаях, например, в печально известном IIS, в котором размещается ASP.NET, даже простая глубина рекурсии O (log n) может потерпеть неудачу из-за их жалкого, неоправданного, смехотворного предела глубины крошечного стека, который делает практически любую рекурсию (или даже длинная цепочка нерекурсивных вложенных вызовов) невозможна. Единственный выход - это редактировать сам бинарный файл iis.
SK-logic
17

По умолчанию CLR выделяет 1 МБ стека для каждого потока (см. Эту статью ). Таким образом, однако, сколько звонков требуется, чтобы превысить эту сумму. Это будет зависеть от того, сколько места в стеке использует каждый вызов для таких вещей, как параметры и локальные переменные.

Вы даже можете сделать это StackOverflowExceptionс помощью одного звонка, если хотите быть немного неортодоксальным:

private static unsafe void BlowUpTheStack()
{
    var x = stackalloc byte[1000000000];
    Console.WriteLine("Oh no, I've blown up the stack!");
}
Коул Кэмпбелл
источник
К сожалению, это разумное значение по умолчанию часто нарушается (например, в asp.net).
SK-logic
2

Поскольку Коул Кэмпбелл отметил объем памяти, а Майкл Боргвардт отметил оптимизацию хвостового вызова, я не буду их освещать.

Еще одна вещь, о которой следует знать, это CPS, который можно использовать для оптимизации нескольких переплетенных функций, где оптимизация хвостового вызова предназначена для отдельных функций.

Вы можете увеличить размер стека, как мы делали здесь , и помните, что 64-битный код потребляет стек быстрее, чем 32-битный код.

Следует отметить, что мы запустили один из примеров в интерактивном режиме F # более 40 часов без потери стека. Да, это был один вызов функции, который выполнялся сам по себе непрерывно до успешного завершения.

Кроме того, если вам нужно выполнить покрытие кода, чтобы выяснить, где возникают проблемы, и нет покрытия кода с VS, которое вы можете использовать, TestDriven.NET

Гай Кодер
источник