size of call stack?
 

Hi...

include
int i;
int RecursiveFunction()
{
printf(" %d ", i++);
RecursiveFunction();
}
int main()
{
RecursiveFunction();
}


Above code will give SegFault due to Stack Overflow. Fine Enough. But here question is something different. If I run same program on windows platform, the total function calls comes around 11754...... If I run this program on Linux Platform, the total function calls comes around 758758....

Why is it huge difference? Which one is better? To avail a huge amount of memory for call stack is good or bad?


Thanks if some one can speak here.

If you compiled with optimization enabled, gcc may limit the stack use. Why isn't 'i' initialized ? There's no guarantee it will be 0 unless explicity set or the variable is made "static".

vkmgeek: you are missing (again) the #include argument.

The stack size is a tunable parameter under Unix. Not sure about Linux, but with Solaris I can set it to 100 MB with this command:
Then your test program only crash after printing 6399438

primo: I believe "i" is guaranteed to be initialized to 0, as it is defined outside a function block.

Ideally, the operating system would give a running process as much memory as it could spare for a function call stack. That way you could do as much recursion as you need to in order to solve your problem. But exactly how much memory you get is very operating system -dependent. Above all, don't write your code to work for some specific assumed value of max recursion depth!

Really, the exact size of the function call stack shouldn't matter to the programmer because recursive algorithms will hardly ever get that far down unless there's a bug in your code. Or if they are supposed to recurse that many times, you probably should rethink what algorithm you should be using for that kind of operation. (e.g. You don't want to use depth-first search [a recursive solution] on a tree with depth 6.02e23.)

Now, some compilers adjust for this sort of problem using something called recursive tail-call optimization, whereby they actually convert recursion to iteration during compilation. The result is that you can recurse down as much as you want for free. The compilers of many functional languages (e.g. MzScheme, Erlang/OTP) support this; not sure about more hip ones like Perl or CPython. See Wikipedia for more information.

There is no specific "function call stack". A program has one main stack where not only the functions return addresses are stored but also all local variables and passed parameters. Using large arrays as local variables can lead to stack overflows, even with few or even no recursion at all.
As I already wrote, the stack size isn't an O/S constant but a per process variable, and can be tuned with the "ulimit -s" shell command. This is true at least on BSDs, Gnu/Linux and Solaris O/Ses.

This is getting more complicated with multi-threaded applications, as each thread requires its own stack, so there is a trade-off between the number of created threads and their stack size.

That is, statically allocated local variables, correct? IIRC, dynamically allocated data goes on the heap.

You're absolutely right about the use of `ulimit`. But it is up to the operating system to determine how much stack to give you, and what to do with it, because it is the OS's responsibility to manage it, not yours. Robert Seacord mentions in "Secure Coding in C and C++" that stack management is dependent on the compiler, the operating system, and the processor. See also the Wikipedia article on the function stack.

That's a good point. I've been taking a look at Erlang recently, and it's fascinating (to me at least, not knowing much about that sort of thing) how the language approaches the problem of concurrency without kernel-level threads using extremely lightweight internal processes. That way, everything is up to the Erlang virtual machine, which can allocate and optimize memory however it needs to. The Erlang VM seems also to be much faster at switching threads than the underlying hardware would be if it were using kernel-level threads instead. Or at least, that's my understanding of it so far.

No, static variables go in the data/bss segment(s), regardless of whether they are declared inside a function of not.

e.g.

Here, "array" is auto-allocated, "counter" goes in the data segment (and is initialised to 1 at compile time), and "str" is dynamically allocated (on the heap). Thus, only "array" goes on the stack.

No, I mean non static local variables, a.k.a. automatic variables.
Dynamically allocated (i.e. malloc'ed) variables data go on the heap except when mmap allocated.
I disagree and this contradict the previous point.
The O/S has indeed a default stack size for new processes creation, but it really has no idea about what is the optimal stack size for any given application.
The default value is at most an empirical, large enough, fit for all size.
This is why an application or an administrator can set it to a better value, at least under Unix.

Ah, OK; I made a mistake in my terminology of "statically allocated" (by which I really meant automatic variables). Thanks.

BTW, it seems that BSD systems will automatically try to allocate more stack space for you if you go past the end (hard ulimits permitting, I presume) [McKusick & Neville-Neil, 2005]. Interestingly enough, on my FreeBSD 6.1 system (1 GB RAM, 1 GB Swap; ulimit set to infinite), this program gets to 4193889 before it dies. [Hardly a scientific benchmark, as the same machine was also running X.Org, Emacs, Opera, and Sylpheed at the same time, but I was somewhat surprised to see it much higher than what vkmgeek reported for Linux and Windows. Of course, memory stats may be significant here, as it may simply be that I just have four times as much memory as vkmgeek does.]

(Just for kicks, it's a blast to sit there and run the (almost) exact same code with mzscheme and see it rocket past 50_000_000 without breaking a sweat -- just a cool 6.4 MB of memory in use. :) Of course, at this point the CPU isn't very cool; X.Org hates printing 10_000 numbers per second on the console. [It's using three-quarters of the time on one of my processors.])

That depends on what you mean by "past the end". Solaris and Linux will grow the stack too at runtime when needed, but that really mean that the initial stack size for a process is smaller that the limit set with "ulimit -s".
I believe the reason is more you have set the stack limit to be as large as possible (inifinite) while vkmgeek was using the default value for his system.
Interesting.
However, the need for strongly recursive support is unfrequent in "real-life" programming. It is more of an academic topic.

Cool...
I found it really interesting and enriching my knowledge..
Thanks all..
THat is why I love open Source, OPen Discussion, and Linux at the end.

or BSD and Solaris for that matter.