我想在一个100x100的数组上进行深度优先搜索。 (假设数组元素代表图节点)。因此，假设最坏情况下，递归函数调用的深度可能会达到10000个，每个调用占用20个字节。那么这是否可行，也就是是否存在栈溢出的可能性？
C/C++中堆栈的最大大小是多少？
请分别为gcc指定以下两种情况:
1）Windows上的cygwin
2）Unix
有哪些常见限制？
主流操作系统上C/C++程序的最大堆栈大小
152
- avd
3
14你知道可以不使用递归实现深度优先搜索吗？请注意，翻译后的内容应保持与原文相同的意思，且更加通俗易懂。 - Sebastian
6不，我不知道，请解释。 - avd
3我在我的回答中提供了一个不使用递归的DFS小例子。 - Andreas Brinck
7个回答
136
在Visual Studio中，默认的堆栈大小为1 MB，所以如果递归深度为10,000，则每个堆栈帧最多可以为约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())
- Andreas Brinck
5
19仅供参考，BFS 与其相同之处在于你使用一个先进先出队列而不是栈。 - Steve Jessop
1是的，在STL术语中，可以使用std :: deque和pop_front / push_back。 - Andreas Brinck
你使用栈实现的深度优先搜索结果会与递归版本不同。在某些情况下这并不重要，但在其他情况下（例如拓扑排序）你将得到错误的结果。 - spin_eight
是的，VS 的默认限制确实为 1MB。有关更多信息以及设置不同值的方法，请参阅 Microsoft 文档：https://msdn.microsoft.com/zh-cn/library/tdkhxaks(v=vs.140).aspx - FrankS101
1我更喜欢使用显式的堆栈数据结构来实现这样的算法，而不是使用递归，这样可以避免以下问题：1. 不依赖于系统堆栈的大小；2. 可以更改算法以使用其他数据结构，例如队列或优先队列，而无需丢弃所有代码。 - Sam Watkins
74
线程的堆栈通常比较小。 您可以在链接时更改默认值， 也可以在运行时更改。 作为参考，一些默认值如下：
- glibc i386, x86_64：7.4 MB
- Tru64 5.1：5.2 MB
- Cygwin：1.8 MB
- Solaris 7..10：1 MB
- MacOS X 10.5：460 KB
- AIX 5：98 KB
- OpenBSD 4.0：64 KB
- HP-UX 11：16 KB
- pixelbeat
4
21这是Bruno Haible亲自确定的实证结果。http://lists.gnu.org/archive/html/bug-coreutils/2009-10/msg00262.html - pixelbeat
我已经在我的新答案中粘贴了Bruno Haible的代码和引用，并展示了如何使用他的代码手动测试您自己的系统：https://dev59.com/8nI-5IYBdhLWcg3wf4ZD#64085509。 - Gabriel Staples
1Linux的默认
ulimit -s为8 MiB；如果您测量的值小于此值，则意味着在进程启动时，一些堆栈已经用于保存环境变量和命令行参数。超过半兆字节似乎有点过多，也许是由于编译器为alloca（128）使用了更多空间而导致的测量误差。 (@GabrielStaples)。您可以在它发生段错误时检查/proc/<PID>/smaps以查看8MiB区域。 - Peter Cordes对我来说，
ulimit 给出的输出为：8176。但是，在程序内部测量时，它给出了大约 8167 的值，在 macOS Monterey 12.6.1 上是正确的。 - Albi9320
与平台、工具链、ulimit、参数相关，这些都没有具体说明，有很多静态和动态属性会对其产生影响。
- DrPizza
3
4在Windows操作系统中，使用默认的VC++链接选项和CreateThread行为，每个线程的栈大小通常约为1MB左右。在Linux操作系统中，如果用户没有设限制，栈大小一般没有限制（栈空间可以从上往下增长以占用几乎整个地址空间）。总之，如果你需要问这个问题，那么你可能不应该使用栈。 - DrPizza
2在嵌入式系统中，你可能只有4k或更少的内存。在这种情况下，即使使用堆栈是合理的，你也必须要考虑是否需要使用。答案通常是一种高傲的耸肩。 - Steve Jessop
1啊，这在内核模式下也经常发生。 - DrPizza
10
（添加于2020年9月26日）
2009年10月24日，像@pixelbeat在这里首次指出的那样, Bruno Haible经验性地发现了几个系统的默认线程堆栈大小。他说，在多线程程序中，“默认线程堆栈大小为”如下。我在“实际”大小列中添加了内容，因为@Peter.Cordes在我的答案下面的评论中指出，下面显示的奇数测试数字并不包括所有线程堆栈，因为其中一些用于初始化。如果我运行ulimit -s来查看我的Linux计算机配置的“最大堆栈大小”，它会输出8192 kB，这正好是8 MB，而不是表格下面列出的奇怪的7.4 MB，对于我的带有gcc编译器和glibc的x86-64计算机来说。因此，您可以将表格中的数字稍微增加一点，以获取给定线程的实际完整堆栈大小。
Thread stack sizes
System and std library Tested Actual
---------------------- ------ ------
- glibc i386, x86_64 7.4 MB 8 MiB (8192 KiB, as shown by `ulimit -s`)
- Tru64 5.1 5.2 MB ?
- Cygwin 1.8 MB ?
- Solaris 7..10 1 MB ?
- MacOS X 10.5 460 KB ?
- AIX 5 98 KB ?
- OpenBSD 4.0 64 KB ?
- HP-UX 11 16 KB ?
Bruno Haible也表示：
32 KB是多线程程序中可以安全分配的堆栈大小上限。
他还说：
而sigaltstack的默认堆栈大小，SIGSTKSZ，在某些平台上为：
- IRIX、OSF/1、Haiku：仅为16 KB。
- glibc、NetBSD、OpenBSD、HP-UX、Solaris：仅为8 KB。
- AIX：仅为4 KB。
Bruno
他编写了以下简单的Linux C程序来实验性地确定上述值。您可以在今天在您的系统上运行它，以快速查看您的最大线程堆栈大小，或者您可以在GDBOnline上在线运行它：https://onlinegdb.com/rkO9JnaHD。
说明：它只是创建一个新线程，以检查线程堆栈大小而不是程序堆栈大小，以防它们不同，然后让该线程重复在栈上分配128字节的内存（而非堆），使用Linuxalloca()调用，之后将0写入此新内存块的第一个字节，然后打印出它已经分配了多少总字节。它会重复这个过程，每次在栈上分配128个字节，直到程序崩溃并显示Segmentation fault (core dumped)错误为止。最后打印的值是您系统允许的估计最大线程堆栈大小。重要提示：
alloca() 在堆栈上分配内存：尽管这看起来像是动态内存分配到堆上，类似于调用malloc()，但是alloca()并不会在堆上动态分配内存。相反，alloca()是一个专门的Linux函数，可以直接“伪动态”地（我不确定应该称之为什么，所以选择了这个术语）分配内存，就好像它是静态分配的内存一样。由alloca()使用和返回的堆栈内存范围仅限于函数级别，因此“当调用alloca()的函数返回其调用者时，它会自动释放”。这就是为什么它的静态范围没有退出，并且由alloca()分配的内存在完成每个for循环迭代并到达for循环范围的末尾时不会被释放。有关详细信息，请参见man 3 alloca。以下是相关引用（已加粗）：
描述
alloca()函数在调用者的堆栈帧中分配size字节的空间。当调用alloca()的函数返回到它的调用者时，这个临时空间会自动释放。返回值
alloca()函数返回指向分配空间开头的指针。如果分配导致堆栈溢出，则程序行为未定义。
以下是Bruno Haible于2009年10月24日从GNU邮件列表直接复制的程序（此处）：
同样，您可以在此在线运行它。
// By Bruno Haible
// 24 Oct. 2009
// Source: https://lists.gnu.org/archive/html/bug-coreutils/2009-10/msg00262.html
// =============== Program for determining the default thread stack size =========
#include <alloca.h>
#include <pthread.h>
#include <stdio.h>
void* threadfunc (void*p) {
int n = 0;
for (;;) {
printf("Allocated %d bytes\n", n);
fflush(stdout);
n += 128;
*((volatile char *) alloca(128)) = 0;
}
}
int main()
{
pthread_t thread;
pthread_create(&thread, NULL, threadfunc, NULL);
for (;;) {}
}
当我使用上面的链接在GDBOnline上运行它时，无论是作为C程序还是C++17程序，每次运行都会得到完全相同的结果。运行大约需要10秒钟左右。以下是输出的最后几行：
Allocated 7449856 bytes Allocated 7449984 bytes Allocated 7450112 bytes Allocated 7450240 bytes Allocated 7450368 bytes Allocated 7450496 bytes Allocated 7450624 bytes Allocated 7450752 bytes Allocated 7450880 bytes Segmentation fault (core dumped)
所以，正如Bruno上面提到的一样（7.4 MB），对于这个系统来说，线程堆栈大小约为7.45 MB。
我对程序进行了一些修改，主要是为了清晰明了，但也为了提高效率和学习一点。
我的更改摘要：
[learning] I passed in
BYTES_TO_ALLOCATE_EACH_LOOPas an argument to thethreadfunc()just for practice passing in and using genericvoid*arguments in C.- Note: This is also the required function prototype, as required by the
pthread_create()function, for the callback function (threadfunc()in my case) passed topthread_create(). See: https://www.man7.org/linux/man-pages/man3/pthread_create.3.html.
- Note: This is also the required function prototype, as required by the
[efficiency] I made the main thread sleep instead of wastefully spinning.
[clarity] I added more-verbose variable names, such as
BYTES_TO_ALLOCATE_EACH_LOOPandbytes_allocated.[clarity] I changed this:
*((volatile char *) alloca(128)) = 0;to this:
volatile uint8_t * byte_buff = (volatile uint8_t *)alloca(BYTES_TO_ALLOCATE_EACH_LOOP); byte_buff[0] = 0;
这是我的修改过的测试程序，与Bruno的完全相同，甚至有相同的结果：
您可以在此处在线运行它，或从我的存储库下载。如果您选择从我的存储库本地运行它，则以下是我用于测试的构建和运行命令：
Build and run it as a C program:
mkdir -p bin && \ gcc -Wall -Werror -g3 -O3 -std=c11 -pthread -o bin/tmp \ onlinegdb--empirically_determine_max_thread_stack_size_GS_version.c && \ time bin/tmpBuild and run it as a C++ program:
mkdir -p bin && \ g++ -Wall -Werror -g3 -O3 -std=c++17 -pthread -o bin/tmp \ onlinegdb--empirically_determine_max_thread_stack_size_GS_version.c && \ time bin/tmp
在快速计算机上，使用线程堆栈大小约为7.4 MB，本地运行时间不到0.5秒。
以下是程序：
// =============== Program for determining the default thread stack size =========
// Modified by Gabriel Staples, 26 Sept. 2020
// Originally by Bruno Haible
// 24 Oct. 2009
// Source: https://lists.gnu.org/archive/html/bug-coreutils/2009-10/msg00262.html
#include <alloca.h>
#include <pthread.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <unistd.h> // sleep
/// Thread function to repeatedly allocate memory within a thread, printing
/// the total memory allocated each time, until the program crashes. The last
/// value printed before the crash indicates how big a thread's stack size is.
///
/// Note: passing in a `uint32_t` as a `void *` type here is for practice,
/// to learn how to pass in ANY type to a func by using a `void *` parameter.
/// This is also the required function prototype, as required by the
/// `pthread_create()` function, for the callback function (this function)
/// passed to `pthread_create()`. See:
/// https://www.man7.org/linux/man-pages/man3/pthread_create.3.html
void* threadfunc(void* bytes_to_allocate_each_loop)
{
const uint32_t BYTES_TO_ALLOCATE_EACH_LOOP =
*(uint32_t*)bytes_to_allocate_each_loop;
uint32_t bytes_allocated = 0;
while (true)
{
printf("bytes_allocated = %u\n", bytes_allocated);
fflush(stdout);
// NB: it appears that you don't necessarily need `volatile` here,
// but you DO definitely need to actually use (ex: write to) the
// memory allocated by `alloca()`, as we do below, or else the
// `alloca()` call does seem to get optimized out on some systems,
// making this whole program just run infinitely forever without
// ever hitting the expected segmentation fault.
volatile uint8_t * byte_buff =
(volatile uint8_t *)alloca(BYTES_TO_ALLOCATE_EACH_LOOP);
byte_buff[0] = 0;
bytes_allocated += BYTES_TO_ALLOCATE_EACH_LOOP;
}
}
int main()
{
const uint32_t BYTES_TO_ALLOCATE_EACH_LOOP = 128;
pthread_t thread;
pthread_create(&thread, NULL, threadfunc,
(void*)(&BYTES_TO_ALLOCATE_EACH_LOOP));
while (true)
{
const unsigned int SLEEP_SEC = 10000;
sleep(SLEEP_SEC);
}
return 0;
}
样例输出（与Bruno Haible原始程序相同）：
bytes_allocated = 7450240 bytes_allocated = 7450368 bytes_allocated = 7450496 bytes_allocated = 7450624 bytes_allocated = 7450752 bytes_allocated = 7450880 Segmentation fault (core dumped)
- Gabriel Staples
12
1感谢您贡献这个答案。我在Windows上运行了Bruno的代码，对输出到底代表什么有点困惑（Windows没有给我seg fault错误，只是关闭了控制台）。Windows与MinGW需要
#include <malloc.h>而不是#include <alloca.h>，因此可能值得一提。另外，我们不能捕获seg fault并将其输出吗？ - Skewjo程序堆栈大小实际上是指主线程的堆栈大小，对吧？我注意到主线程和新创建的工作线程之间存在堆栈大小的差异（11169280与9315968），你有什么想法为什么会有这样的差异吗？ - Baiyan Huang
2Linux的默认
ulimit -s为8 MiB；这设置了主线程的堆栈大小增长限制。环境变量和命令行参数在其顶部占用了一些空间。通过pthread启动的其他线程不会动态增长它们的堆栈，而是使用相同的默认8MiB进行固定大小分配。您可以在它发生段错误时检查/proc/<PID>/smaps以查看8MiB区域。请注意，它在printf/write调用内部发生段错误，并且stdio代码使用了大量的堆栈空间，您没有测量到。 - Peter Cordes1当我在GDB中进行测试以便在段错误后查看
smaps时，线程堆栈是一个8204 kiB的分配。程序内计算的堆栈大小为7451008字节，而7451008 / (128/144) / 1024约为8186 kiB，printf堆栈深度可能解释了其余部分。 - Peter Cordes2顺便说一句，验证GCC的
alloca是否使用了比您要求的更多的空间的另一种方法是将大小增加到例如4096。或者将其设置为4096-8，结果是GCC仅分配4096，而不是4096 + 16。(https://godbolt.org/z/8T4xfbEdq)。每个分配浪费16或8个字节，未计算的总分数将小得多。 - Peter Cordes显示剩余7条评论
9
我在工作中刚刚用完栈，它是一个数据库，正在运行一些线程，基本上前任开发人员在栈上丢了一个大数组，而且栈本来就很低。该软件是使用Microsoft Visual Studio 2015编译的。
尽管线程已经用完了栈，但它在默默失败后继续运行，只有在访问栈上的数据内容时才会发生堆栈溢出。
我能给出的最好建议是不要在栈上声明数组-尤其是在复杂应用程序中，特别是在线程中，请使用堆。这正是其存在的目的 ;)
还要记住的是，当声明栈时可能不会立即失败，只有在访问时才会失败。我猜测编译器在Windows下“乐观地”声明栈，即它假设栈已经声明并具有足够的大小，直到使用它时才发现栈不存在。
不同的操作系统可能有不同的栈声明策略。
- Owl
8
是的，存在堆栈溢出的可能性。C和C++标准并不规定堆栈深度等问题，这些通常是环境问题。
大多数良好的开发环境和/或操作系统都会让您在链接或加载时自定义进程的堆栈大小。
您应该指定您使用的操作系统和开发环境以获取更有针对性的帮助。
例如，在Ubuntu Karmic Koala下，gcc的默认值为2M保留和4K提交，但是在链接程序时可以更改此设置。使用ld的--stack选项即可实现。
大多数良好的开发环境和/或操作系统都会让您在链接或加载时自定义进程的堆栈大小。
您应该指定您使用的操作系统和开发环境以获取更有针对性的帮助。
例如，在Ubuntu Karmic Koala下，gcc的默认值为2M保留和4K提交，但是在链接程序时可以更改此设置。使用ld的--stack选项即可实现。
- paxdiablo
5
2@lex：没有普遍的限制。它取决于许多参数。 - Michael Foukarakis
@paxdiablo：reserved和committed的意思是什么？ - avd
2保留是分配多少地址空间，承诺是附加后备存储器的数量。换句话说，保留地址空间并不意味着在需要时内存会存在。如果您从未使用超过4K堆栈，则不会为其他1.6M浪费实际内存。如果您想确保有足够的堆栈，保留和承诺应该相同。 - paxdiablo
3@paxdiablo 2M - 4k 不等于1.6M。只是说一下。（我第一次读你的评论时也被搞糊涂了，） - griffin
2@griffin，恭喜你在三年多的时间里第一个发现了这个问题。当然，我是指“其余部分”——我会避免给出实际数字，以免犯下另一个可能的错误 :-) - paxdiablo
5
我不确定您所说的在矩形阵列上进行深度优先搜索是什么意思，但我认为您知道自己在做什么。
如果堆栈限制成为问题，您应该能够将递归解决方案转换为迭代解决方案，将中间值推入从堆分配的堆栈中。
- Dave Kirby
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接