Максимальный размер стека программы C / C ++

115

Я хочу сделать DFS на массиве 100 X 100. (Скажем, элементы массива представляют собой узлы графа). Таким образом, в худшем случае глубина рекурсивных вызовов функций может доходить до 10000, причем каждый вызов может занимать до 20 байт. Так возможно ли это, есть ли возможность переполнения стека?

Каков максимальный размер стека в C / C ++?

Пожалуйста, укажите для gcc как
1) cygwin в Windows
2) Unix

Каковы общие ограничения?

АВД
источник
11
Вы ведь знаете, что можно реализовать поиск в глубину без рекурсии, верно?
Себастьян
4
Нет, не знаю, объясните, пожалуйста.
avd 01
1
В своем ответе я привел небольшой пример DFS без рекурсии
Андреас Бринк,
56
плюс один за вопрос о фактическом переполнении стека
Сэм Уоткинс,
3
@SamWatkins: да, одна из самых больших проблем для меня с названием Stack Overflow заключается в том, что я могу поискать «переполнение стека» в Google и оказаться на этом веб-сайте, но не обязательно / менее вероятно в вопросах о переполнении стека ...
lalilulelost

Ответы:

106

В Visual Studio размер стека по умолчанию, я думаю, составляет 1 МБ, поэтому при глубине рекурсии 10000 каждый кадр стека может быть не более ~ 100 байт, что должно быть достаточно для алгоритма DFS.

Большинство компиляторов, включая Visual Studio, позволяют указать размер стека. В некоторых (всех?) Версиях Linux размер стека не является частью исполняемого файла, а является переменной среды в ОС. Затем вы можете проверить размер стека ulimit -sи установить новое значение, напримерulimit -s 16384 .

Вот ссылка с размерами стека по умолчанию для gcc.

DFS без рекурсии:

std::stack<Node> dfs;
dfs.push(start);
do {
    Node top = dfs.top();
    if (top is what we are looking for) {
       break;
    }
    dfs.pop();
    for (outgoing nodes from top) {
        dfs.push(outgoing node);
    }
} while (!dfs.empty())
Андреас Бринк
источник
12
И для справки: BFS такая же, за исключением того, что вы используете FIFO вместо стека.
Стив Джессоп,
Да, или в STL-lingo используйте std :: deque с pop_front / push_back
Андреас Бринк
ваша DFS с результатами стека будет отличаться от версии с рекурсией. В некоторых случаях это не имеет значения, но в других (например, при топологической сортировке) вы получите неверные результаты
spin_eight
Да, ограничение по умолчанию для VS действительно составляет 1 МБ. Дополнительную информацию и способ установки другого значения можно найти в документации Microsoft: msdn.microsoft.com/en-us/library/tdkhxaks(v=vs.140).aspx
FrankS101
Я предпочитаю использовать явную структуру данных стека для таких алгоритмов, а не рекурсию, чтобы 1. не зависеть от размера системного стека, 2. можно было изменить алгоритм, чтобы использовать другую структуру данных, например очередь или очередь с приоритетами, не бросая из всего кода.
Сэм Уоткинс,
47

стеки для потоков часто меньше. Вы можете изменить значение по умолчанию во время связывания или изменить во время выполнения. Для справки некоторые значения по умолчанию:

  • glibc i386, x86_64 7,4 МБ
  • Tru64 5.1 5.2 МБ
  • Cygwin 1,8 МБ
  • Solaris 7..10 1 МБ
  • MacOS X 10.5 460 КБ
  • AIX 5 98 КБ
  • OpenBSD 4.0 64 КБ
  • HP-UX 11 16 КБ
pixelbeat
источник
14
Определено эмпирически Бруно Хейбле lists.gnu.org/archive/html/bug-coreutils/2009-10/msg00262.html
pixelbeat 01
17

Платформенно-зависимый, зависящий от инструментальной цепочки, зависящий от ulimit, зависящий от параметра ... Он вообще не указан, и существует множество статических и динамических свойств, которые могут на него повлиять.

DrPizza
источник
4
Нет никаких «общих ограничений». В Windows с параметрами компоновщика VC ++ по умолчанию и поведением CreateThread по умолчанию, обычно около 1 МБ на поток. Я считаю, что в Linux с неограниченным числом пользователей обычно нет ограничений (стек может просто расти вниз и занимать почти все адресное пространство). По сути, если вам нужно спросить, вы не должны использовать стек.
DrPizza 01
1
Во встроенных системах у вас может быть 4 КБ или меньше. В этом случае вам нужно спросить, даже если использование стека разумно. Обычно в ответ на это галльское пожатие плечами.
Стив Джессоп,
1
Ах да, тоже часто бывает в режиме ядра.
DrPizza 01
6

Да, есть вероятность переполнения стека. Стандарт C и C ++ не требует таких вещей, как глубина стека, обычно это проблема окружающей среды.

Большинство достойных сред разработки и / или операционных систем позволят вам настроить размер стека процесса либо во время ссылки, либо во время загрузки.

Вы должны указать, какую ОС и среду разработки вы используете для получения более адресной помощи.

Например, в Ubuntu Karmic Koala по умолчанию для gcc зарезервировано 2 Мбайт, а зафиксировано 4 КБ, но это можно изменить при связывании программы. Для этого используйте --stackпараметр ld.

paxdiablo
источник
2
@lex: общих ограничений нет. Это зависит от множества параметров.
Майкл Фукаракис, 01
@paxdiablo: Что означает "зарезервировано и совершено"?
avd 01
2
Зарезервировано - это объем адресного пространства, который нужно выделить, зафиксированный - это объем, к которому нужно подключить резервное хранилище. Другими словами, резервирование адресного пространства не означает, что память будет там, когда она вам понадобится. Если вы никогда не используете стек более 4 КБ, вы не тратите реальную память на остальные 1,6 МБ. Если вы хотите гарантировать, что стека будет достаточно, зарезервированные и зафиксированные должны быть идентичны.
paxdiablo
3
@paxdiablo 2M - 4k - это не 1,6M. Просто говорю. (запутал меня первые 3 раза, когда я прочитал ваш комментарий)
griffin
2
@griffin, спасибо первому, кто уловил это за 3+ года. Я, конечно, имел в виду «остальное» - я избегаю реальных цифр, чтобы не допустить еще одной возможной ошибки :-)
paxdiablo
5

У меня просто закончился стек на работе, это была база данных, и в ней выполнялись некоторые потоки, в основном предыдущий разработчик бросил в стек большой массив, и стек все равно был низким. Программное обеспечение было скомпилировано с использованием Microsoft Visual Studio 2015.

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

Лучший совет, который я могу дать, - не объявлять массивы в стеке - особенно в сложных приложениях и особенно в потоках, вместо этого используйте кучу. Вот для чего он нужен;)

Также помните, что при объявлении стека он может выйти из строя не сразу, а только при доступе. Я предполагаю, что компилятор объявляет стек под окнами «оптимистично», то есть он будет предполагать, что стек был объявлен и имеет достаточный размер, пока он не дойдет до его использования, а затем обнаружит, что стека там нет.

В разных операционных системах могут быть разные политики объявления стека. Пожалуйста, оставьте комментарий, если вы знаете, что это за политика.

Сова
источник
3

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

Если ограничение стека является проблемой, вы сможете преобразовать свое рекурсивное решение в итеративное решение, которое помещает промежуточные значения в стек, который выделяется из кучи.

Дэйв Кирби
источник