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

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

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

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

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

В 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())

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

• 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 КБ

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

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

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

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

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

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

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

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

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

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

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

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