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())
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
1.将其作为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;
}
7条答案
按热度按时间guicsvcw1#
在Visual Studio中，默认的堆栈大小是1 MB，我认为，因此递归深度为10，000，每个堆栈帧最多可以是100字节，这对于DFS算法来说应该足够了。
大多数编译器，包括Visual Studio，都允许你指定堆栈大小。在一些（所有？）Linux版本中，堆栈大小不是可执行文件的一部分，而是操作系统中的一个环境变量。然后你可以使用
ulimit -s检查堆栈大小，并使用例如ulimit -s 16384将其设置为一个新值。下面是gcc的默认堆栈大小的link。
无递归的DFS：
wydwbb8l2#
线程的堆栈通常较小。您可以在链接时更改默认值，也可以在运行时更改。作为参考，一些默认值如下：
***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
64jmpszr3#
依赖于平台、依赖于工具链、依赖于ulimit、依赖于参数......它根本没有指定，并且有许多静态和动态属性可以影响它。
2vuwiymt4#
是的，有可能发生堆栈溢出。C和C++标准并没有规定堆栈深度之类的事情，这些通常是环境问题。
大多数像样的开发环境和/或操作系统都允许您在链接或加载时定制进程的堆栈大小。
您应该指定要使用的操作系统和开发环境，以获得更有针对性的帮助。
例如，在Ubuntu Karmic Koala下，gcc的默认值是2 M reserved和4K committed，但当您链接程序时可以更改。使用
ld的--stack选项来完成此操作。92dk7w1h5#
我只是在工作中用完了堆栈，这是一个数据库，它正在运行一些线程，基本上是以前的开发人员在堆栈上抛出了一个大数组，反正堆栈很低。该软件是使用Microsoft Visual Studio 2015编译的。
即使线程已经耗尽了堆栈，它也会默默地失败并继续，只有当它访问堆栈上的数据内容时才会发生堆栈溢出。
我能给予的最好的建议是不要在堆栈上声明数组--特别是在复杂的应用程序中，特别是在线程中，而应该使用堆。）
另外要记住，声明栈的时候可能不会立即失败，而只会在访问的时候失败。我的猜测是编译器在windows下声明栈是“乐观的”，也就是说，它会假设栈已经被声明，并且足够大，直到它开始使用它，然后发现栈不存在。
不同的操作系统可能有不同的堆栈声明策略。
qlvxas9a6#
（2020年9月26日）
2009年10月24日，as @pixelbeat first pointed out here，Bruno Haible empirically discovered the following default thread stack sizes用于几个系统。他说在多线程程序中，“默认线程堆栈大小是”如下。我在“实际”大小列中添加，因为@Peter.Cordes在我的答案下面的评论中指出，然而，下面显示的奇数测试数字不包括所有线程堆栈，如果我运行
ulimit -s来查看我的Linux计算机配置的“最大堆栈大小”，它输出8192kB，正好是8 MB，* 不是 * 下表中列出的奇数7.4 MB。对于我的x86-64计算机，使用gcc编译器和glibc。所以，你可以在下表中的数字上加一点，以获得给定线程的实际完整堆栈大小。还要注意，下面的“测试”列单位都是MB和KB（基数为1000的数字），而不是MiB和KiB（基数为1024的数字）。
Bruno Haible还指出：
在多线程程序中，32 KB的内存超过了您可以安全地在堆栈上分配的内存
他说：
sigaltstack的默认堆栈大小SIGSTKSZ为
布鲁诺
他写了下面这个简单的Linux C程序来根据经验确定上述值。你可以在你的系统上运行它来快速查看你的最大线程堆栈大小是多少，或者你可以在GDBOnline上在线运行它：https://onlinegdb.com/rkO9JnaHD。
**解释：**它只是创建一个新线程，检查 * 线程堆栈大小 * 而不是 * 程序堆栈大小 ，如果它们不同，那么它会让该线程重复分配128字节的内存 * 在堆栈上（而不是堆上），使用Linux
alloca()call，然后它会将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日的节目，copied directly from the GNU mailing list here：
同样，您可以run it live online here。
当我使用上面的链接在GDBOnline上运行它时，我每次运行它都会得到完全相同的结果，作为C和C++17程序。运行大约需要10秒左右。下面是输出的最后几行：
因此，这个系统的线程堆栈大小约为7.45 MB，正如Bruno在上面提到的（7.4 MB）。
我对程序做了一些修改，主要是为了清晰，但也是为了提高效率，还有一点是为了学习。
我的修改摘要：
1.[学习]我传入
BYTES_TO_ALLOCATE_EACH_LOOP作为threadfunc()的参数，只是为了练习传入和使用C中的泛型void*参数。1.注意：这也是the
pthread_create()function所需的函数原型，用于传递给pthread_create()的回调函数（在我的例子中是threadfunc()）。请参阅：https://www.man7.org/linux/man-pages/man3/pthread_create.3.html。1.[效率]我让主线程休眠，而不是浪费地旋转。
1.我添加了更详细的变量名，比如
BYTES_TO_ALLOCATE_EACH_LOOP和bytes_allocated。1.[清晰度]我改变了这个：
对此：
这是我修改后的测试程序，它做的事情和Bruno的完全一样，甚至有相同的结果：
你可以使用run it online here或download it from my repo here。如果你选择从我的仓库本地运行它，这里是我用于测试的build和run命令：
1.编译并运行它作为一个C程序：
1.将其作为C++程序构建并运行：
在线程堆栈大小约为7.4 MB的快速计算机上本地运行所需时间〈0.5秒。
程序如下：
示例输出（与Bruno Haible的原始程序相同的结果）：
khbbv19g7#
我不知道你在矩形数组上做深度优先搜索是什么意思，但我假设你知道你在做什么。
如果堆栈限制是一个问题，您应该能够将递归解决方案转换为迭代解决方案，该解决方案将中间值推送到从堆分配的堆栈上。