C/C++ maximum stack size of program

Question

I want to do DFS on a 100 X 100 array. (Say elements of array represents graph nodes) So assuming worst case, depth of recursive function calls can go upto 10000 with each call taking upto say 20 bytes. So is it feasible means is there a possibility of stackoverflow?

What is the maximum size of stack in C/C++?

Please specify for gcc for both
1) cygwin on Windows
2) Unix

What are the general limits?

Answer 1

In Visual Studio the default stack size is 1 MB i think, so with a recursion depth of 10,000 each stack frame can be at most ~100 bytes which should be sufficient for a DFS algorithm.

Most compilers including Visual Studio let you specify the stack size. On some (all?) linux flavours the stack size isn't part of the executable but an environment variable in the OS. You can then check the stack size with ulimit -s and set it to a new value with for example ulimit -s 16384.

Here's a link with default stack sizes for gcc.

DFS without recursion:

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

I am not sure what you mean by doing a depth first search on a rectangular array, but I assume you know what you are doing.

If the stack limit is a problem you should be able to convert your recursive solution into an iterative solution that pushes intermediate values onto a stack which is allocated from the heap.

Answer 3

Platform-dependent, toolchain-dependent, ulimit-dependent, parameter-dependent.... It is not at all specified, and there are many static and dynamic properties that can influence it.

Answer 4

stacks for threads are often smaller. You can change the default at link time, or change at run time also. For reference some defaults are:

• 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

Answer 5

I just ran out of stack at work, it was a database and it was running some threads, basically the previous developer had thrown a big array on the stack, and the stack was low anyway. The software was compiled using Microsoft Visual Studio 2015.

Even though the thread had run out of stack, it silently failed and continued on, it only stack overflowed when it came to access the contents of the data on the stack.

The best advice i can give is to not declare arrays on the stack - especially in complex applications and particularly in threads, instead use heap. That's what it's there for ;)

Also just keep in mind it may not fail immediately when declaring the stack, but only on access. My guess is that the compiler declares stack under windows "optimistically", i.e. it will assume that the stack has been declared and is sufficiently sized until it comes to use it and then finds out that the stack isn't there.

Different operating systems may have different stack declaration policies. Please leave a comment if you know what these policies are.

Answer 6

Yes, there is a possibility of stack overflow. The C and C++ standard do not dictate things like stack depth, those are generally an environmental issue.

Most decent development environments and/or operating systems will let you tailor the stack size of a process, either at link or load time.

You should specify which OS and development environment you're using for more targeted assistance.

For example, under Ubuntu Karmic Koala, the default for gcc is 2M reserved and 4K committed but this can be changed when you link the program. Use the --stack option of ld to do that.