How to allow more memory and avoid stack overflow on lots of recursion?

Question

I'm testing the timing of an algorithm that does lots of recursive calls. My program dies at about 128k recursive calls, and this takes only .05 seconds. I'd like to allow more memory to have longer timings in my analysis. I'm running linux and using gcc. Is there a system call, or environment variable, or gcc flag, or wrapper, or something?

Answer 1

There is no stack size complier option for gcc under Linux. However this text discusses how to set the stack size on Linux. using the ulimit command.

Edit: That link died in Dec 2023 so here are the contents, as retrieved by the Wayback Machine:

Stack Overflow Problems

This file gives some hints on addressing this problem on different platforms.

Under Unix-like systems, programs may throw a "Segmentation Fault" error. This can be due to stack overflow, especially from recursive function calls or huge data sets. In our demo program "Pi" (see "$(CORE_PATH)/progs/pi"), we compute Pi to any number of desired bits or digits.

Here are some test results on when stack overflows will occur on different platforms, using their default stack sizes.

platform	default size	# bits	# digits
SunOS/Solaris	8172K bytes	<=39875	<=12003 (Shared Version)
Linux	8172K bytes	<=62407	<=18786
Windows	1024K bytes	<=10581	<=3185 (Release Version)
cygwin	2048K bytes	<=3630	<=1092

If we now change their stack size to their maximum, our Pi program can compute more bits.

platform	stack size	# bits	# digits
SunOS/Solaris	unlimited	>=100,000	30102
Linux	8172K bytes	<=33,219,282	<=10,000,000(?)
Windows	32768K bytes	<=343077	<=12041

How to change the default stack size on different platforms

In general, under Unix-like platforms, the stack size is controlled by environment variable, not the program itself.
So you cannot pass any flags to the compilers, like gcc, to setup stack size.
Under Windows platforms, the stack size information is contained in the executable files. It can be set during compilation in Visual C++, but this is not available in gcc.
Alternatively, Microsoft provides a program "editbin.exe" which can change the executable files directly. Here are more details:

SunOS/Solaris:

limit # shows the current stack size
unlimit # changes the stack size to unlimited
setenv STACKSIZE 32768 # limits the stack size to 32M bytes

Linux:

ulimit -a # shows the current stack size
ulimit -s 32768 # sets the stack size to 32M bytes

Windows (during compilation):

1. Select "Project->Setting".
2. Select "Link" page.
3. Select "Category" to "Output".
4. Type your preferred stack size in "Reserve:" field under "Stack allocations". eg, 32768 in decimal or 0x20000 in hexadecimal.

Windows (to modify the executable file):

There are two programs included in Microsoft Visual Studio, "dumpbin.exe" and "editbin.exe".
Run dumpbin /headers executable_file and you can see the "size of stack reserve" information in "optional header values".
Run editbin /STACK:size to change the default stack size.

Answer 2

Try to organize your recursive function to have tail recursion.

That is to say, make sure the last operation of your recursive function is the recursive call. By doing this, the compiler can optimize it into simply iterations.

Tail recursion will help you because iterations will dramatically decrease the stack space used.

With tail recursion, you typically pass your value UP all the way, calculating 1 step at a time. So when the recursion is done, all that needs to be done is to return.

---

Example:

Convert the following code:

unsigned fact(unsigned x)
{
  if(x == 1)
    return 1;

   //--> Not tail recursive, multiply operation after the recursive call
   return fact(x-1) * x;
}

To this:

unsigned fact(unsigned x)
{
    return tail_fact(x, 1);
}

unsigned tail_fact(unsigned x, unsigned cur_val)
{
  if(x == 1)
    return cur_val;  

  return tail_fact(x-1, x * cur_val);  
}

Answer 3

Although other answers talk about how to either avoid recursion altogether, or how to use tail recursion, or how to simply set a larger stack size, I think for completeness that it's worthwhile to consider memory usage patterns (to answer "how to allow more memory ... on lots of recursion").

Out of habit, many programmers will allocate buffers inside the recursive function, and reallocate new buffers when the function is called recursively:

int recursive_function(int x)
{
    if (1 == x)
        return 1;
    int scratchpad[100];
    ... // use scratchpad
    return recursive_function(x-1) + scratchpad[x-1];
}

Since this is a throwaway sample, I won't bother worrying about invalid input (negative values, values larger than 100) and I will assume somebody asking a question about programming either knows how to do that or is smart enough to find out.

The important point here is that scratchpad takes up 400 bytes (on a 32 bit machine, 800 bytes on a 64 bit machine) of the stack each and every time recursive_function() is called, so if recursive_function() is called recursively 100 times, then 40,000 bytes (or 80,000 bytes on a 64 bit machine) of stack space are being used for buffers, and it's very likely you can modify the function to reuse the same buffer on each call:

int recursive_function(int x, int* buffer, int buffer_length)
{
    if (1 == x)
        return 1;
    ... // use buffer (and buffer_length to avoid overflow)
    int temp_value = buffer[x-1];
    return recursive_function(x-1, buffer, buffer_length) + temp_value;
}

Of course you could instead use a std::vector, which handles some details for you to protect you against memory leaks and buffer overruns (and, for the record, keeps the data on the heap [see footnote], meaning it will likely use less stack space).

40k or even 80k may not seem like much but things can add up. If the function doesn't have many other stack-allocated variables then this can dominate stack space (that is, if it weren't for the extra space the buffers take up you may be able to call the function far more times).

This may seem obvious, but it does come up, even in nonrecursive functions. Additionally, buffers aren't always obvious as arrays. They may be strings or objects, for instance.

---

Footnote: STL containers, such as arrays don't necessarily put all their data on the heap. They actually take a template argument to specify the memory allocation used; it's just that the allocator they use by default puts the data on the heap. Obviously unless you specify an allocator that somehow puts the data on the stack, the end result will be the same: using STL containers will probably use less memory than using stack allocated arrays or objects.

I say "probably" because although the data is kept on the heap (or somewhere else), the container can only access that data through pointers it keeps internally, if the container is on the stack then those pointers will reside on the stack, and those pointers take up space. So a one or two element std::vector may actually take up more space on the stack than the corresponding array.

Answer 4

Take a look at setrlimit():

RLIMIT_STACK
This is the maximum size of the initial thread's stack, in bytes. The implementation does not automatically grow the stack beyond this limit. If this limit is exceeded, SIGSEGV shall be generated for the thread. If the thread is blocking SIGSEGV, or the process is ignoring or catching SIGSEGV and has not made arrangements to use an alternate stack, the disposition of SIGSEGV shall be set to SIG_DFL before it is generated.

Answer 5

You have three options:

1. Rewrite the program to make it non-recursive. This is the best, but not always possible.

2. Rewrite the program to use a separate stack for storing the execution state. This way you preserve the recursive nature but no longer use the system stack for storing the recursion algorithm state data.

3. Tweak the environment to postpone the inevitable. Visual C++ has a linker setting for the stack size. Almost sure gcc has one too.