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

Question

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

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

Пожалуйста, укажите для GCC для обоих
1) cygwin на Windows
2) Unix

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

Answer 1

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

Answer 2

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

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

Answer 3

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

Answer 4

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

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

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

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

Answer 5

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

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

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

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

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

Answer 6

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

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