In the context of the CLR in .NET how is stack space allocated

Question

In the context of the CLR in .NET how is stack space allocated and what is it typically limited by?

For example:

Can any given thread continue to add to the stack until memory runs out? If not; how does the CLR decide how much space to allocate and can it change its mind?

PS: Just to put some context on it this all started from a discussion on how to build a method that will calculate the Fibonacci sequence and one of the suggestions was a recursive function.

David Heffernan · Accepted Answer · 2011-05-12T08:06:54.363

4

The CLR immediately commits the full stack space for each thread, as soon as it is created. The default stack size is 1MB. If you push your stack over that size, that's a stack overflow and an error is raised.

The CLR adopts a different policy from native code which merely reserves 1MB but commits it on demand.

Those are implementation details. It is best to simply view the stack as a fixed size data structure. This view fits with both .net and native stack implementations.

A recursive function is the absolute worst way to calculate Fibonacci because its complexity is exponential. Instead you should use an iterative algorithm which is linear in time and constant in space. For example:

static int fib(int n)
{
    int result = 0;
    int a = 1;
    for (int i=1; i<=n; i++)
    {
        int temp = result;
        result = a;
        a = temp + a;
    }
    return result;
}

Of course, in reality, you'd overflow your result variable long before you reached a stack overflow. But the performance of a recursive algorithm is untenable for values of n in the region of 30-40.

Yet another sensible approach is to fill a static array with pre-calculated values. Again since the values grow so fast you don't need a very large array for it to contain all values that fit into an int or even a long.

edited May 12 '11 at 08:06

answered May 12 '11 at 07:27

David Heffernan

601,492
42
1,072
1,490

@Marc Naive recursive algorithms, i.e. `fib(n)=fib(n-1)+fib(n-2)` have exponential complexity, see http://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence - I agree that my statement above is sloppy, I will remedy that – David Heffernan May 12 '11 at 07:58
ah, yes, hence my "both previous terms" - I guess that *even on a slow day* it wouldn't occur to me to implement fibonacci *that badly* ;p – Marc Gravell May 12 '11 at 10:11
@Marc It's quite a nice implementation if you can memoize. I think Python, for example, has a built-in memoize decorator that can turn this horrid version of `fib` into a super efficient one. A single decorator can turn O(1^n) into O(n)! – David Heffernan May 12 '11 at 10:26
1

good job than 1^n is cheap, then ;p (just kidding, I know what you mean) – Marc Gravell May 12 '11 at 10:32
@Marc Yeah, I'm not very good at this O() stuff! I think I should write O(k^n). – David Heffernan May 12 '11 at 10:37

In the context of the CLR in .NET how is stack space allocated

1 Answers1