我想在100 X 100阵列上进行DFS.(假设数组的元素代表图形节点)因此,假设最坏的情况,递归函数调用的深度可以达到10000,每个调用占用20个字节.那么可行的方法是否存在stackoverflow的可能性？
C/C++中堆栈的最大大小是多少？
请指定gcc for
1)cygwin on Windows
2)Unix
一般限制是什么？
And*_*nck 94
在Visual Studio中,我认为默认的堆栈大小是1 MB,因此在递归深度为10,000的情况下,每个堆栈帧最多可以是~100个字节,这对于DFS算法应该是足够的.
包括Visual Studio在内的大多数编译器都允许您指定堆栈大小.在某些(所有？)linux风格上,堆栈大小不是可执行文件的一部分,而是OS中的环境变量.然后,您可以检查堆栈大小,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())
pix*_*eat 41
线程的堆栈通常较小.您可以在链接时更改默认值,也可以在运行时更改默认值.作为参考,一些默认值是:
DrP*_*zza 14
依赖于平台,依赖于工具链,依赖于ulimit,依赖于参数....它根本没有指定,并且有许多静态和动态属性可以影响它.
Gab*_*les 12
（2020 年 9 月 26 日添加）
2009 年 10 月 24 日，正如 @pixelbeat 首先指出的那样，Bruno Haible 凭经验发现了多个系统的以下默认线程堆栈大小。他说，在多线程程序中，“默认的线程堆栈大小”如下。我在“实际”大小列中添加了，因为 @Peter.Cordes 在我的答案下面的评论中指出，下面显示的奇数测试数字并不包括所有线程堆栈，因为其中一些用于初始化。如果我运行ulimit -s查看 Linux 计算机配置的“最大堆栈大小”，它会输出8192kB，即8 MB，而不是下表中列出的带有 gcc 编译器的 x86-64 计算机的奇数7.4 MB ， glibc。因此，您可以在下表中的数字上添加一些，以获得给定线程的实际完整堆栈大小。
另请注意，下面的“已测试”列单位均为 MB 和 KB（以 1000 为基数），而不是 MiB 和 KiB（以 1024 为基数）。我已经通过验证 7.4 MB 的案例向自己证明了这一点。
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 ?
布鲁诺·海布尔还表示：
32 KB 超出了您可以在多线程程序的堆栈上安全分配的大小
他说：
sigaltstack 的默认堆栈大小 SIGSTKSZ 是
- 在某些平台上只有 16 KB：IRIX、OSF/1、Haiku。
- 在某些平台上只有 8 KB：glibc、NetBSD、OpenBSD、HP-UX、Solaris。
- 在某些平台上只有 4 KB：AIX。
布鲁诺
他编写了以下简单的 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秒左右。以下是输出的最后几行：
Run Code Online (Sandbox Code Playgroud)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)
因此，该系统的线程堆栈大小约为 7.45 MB，如上面 Bruno 提到的 (7.4 MB)。
我对程序做了一些更改，主要是为了清晰起见，也是为了效率，还有一点是为了学习。
我的改变总结：
BYTES_TO_ALLOCATE_EACH_LOOP[学习] 我作为一个参数传递给了threadfunc()just 来练习在 C 中传递和使用泛型void*参数。
pthread_create()threadfunc()给 的回调函数（在pthread_create()我的例子中） 。请参阅： https: //www.man7.org/linux/man-pages/man3/pthread_create.3.html。[效率]我让主线程休眠而不是浪费性地旋转。
[清晰度]我添加了更详细的变量名称，例如BYTES_TO_ALLOCATE_EACH_LOOP和bytes_allocated。
[清晰度]我改变了这一点：
*((volatile char *) alloca(128)) = 0;
对此：
volatile uint8_t * byte_buff =
(volatile uint8_t *)alloca(BYTES_TO_ALLOCATE_EACH_LOOP);
byte_buff[0] = 0;
这是我修改后的测试程序，它的作用与布鲁诺的完全相同，甚至具有相同的结果：
您可以在这里在线运行它，或者从我的存储库下载它。如果您选择从我的存储库本地运行它，以下是我用于测试的构建和运行命令：
将其作为 C 程序构建并运行：
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/tmp
将其作为 C++ 程序构建并运行：
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 的原始程序结果相同）：
Run Code Online (Sandbox Code Playgroud)bytes_allocated = 7450240 bytes_allocated = 7450368 bytes_allocated = 7450496 bytes_allocated = 7450624 bytes_allocated = 7450752 bytes_allocated = 7450880 Segmentation fault (core dumped)
是的，存在堆栈溢出的可能性。C 和 C++ 标准没有规定堆栈深度之类的东西，这些通常是环境问题。
大多数体面的开发环境和/或操作系统将允许您在链接或加载时定制进程的堆栈大小。
您应该指定您使用的操作系统和开发环境以获得更有针对性的帮助。
例如，在 Ubuntu Karmic Koala 下，gcc 的默认值是 2M 保留和 4K 已提交，但这可以在您链接程序时更改。使用--stack选项ld来做到这一点。
我刚工作的时候栈用完了，是一个数据库，运行了一些线程，基本上之前的开发者在栈上扔了一个大数组，反正栈是低的。该软件是使用 Microsoft Visual Studio 2015 编译的。
即使线程已用完堆栈，它也默默地失败并继续运行，只有在访问堆栈上的数据内容时才会发生堆栈溢出。
我能给出的最好建议是不要在堆栈上声明数组——尤其是在复杂的应用程序中，尤其是在线程中，而是使用堆。这就是它的用途;)
另外请记住，在声明堆栈时它可能不会立即失败，而只会在访问时失败。我的猜测是编译器在 windows 下“乐观地”声明堆栈，即它会假设堆栈已经被声明并且足够大，直到它使用它然后发现堆栈不存在。
不同的操作系统可能有不同的堆栈声明策略。如果您知道这些政策是什么，请发表评论。
我不确定对矩形数组进行深度优先搜索是什么意思，但我假设您知道自己在做什么。
如果堆栈限制是一个问题，您应该能够将递归解决方案转换为迭代解决方案，将中间值推送到从堆分配的堆栈上。
| 归档时间： |
|
| 查看次数： |
126702 次 |
| 最近记录： |