LinuxQuestions.org
Visit the LQ Articles and Editorials section
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices



Reply
 
Search this Thread
Old 11-04-2006, 02:13 AM   #1
vkmgeek
Member
 
Registered: Feb 2006
Location: Ahmedabad
Distribution: rhel5
Posts: 185
Blog Entries: 2

Rep: Reputation: 31
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.
 
Old 11-04-2006, 05:38 AM   #2
primo
Member
 
Registered: Jun 2005
Posts: 542

Rep: Reputation: 34
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".
 
Old 11-04-2006, 07:11 AM   #3
jlliagre
Moderator
 
Registered: Feb 2004
Location: Outside Paris
Distribution: Solaris10, Solaris 11, Mint, OL
Posts: 9,523

Rep: Reputation: 365Reputation: 365Reputation: 365Reputation: 365
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:
Code:
# ulimit -s 100000
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.
 
Old 11-04-2006, 09:16 AM   #4
taylor_venable
Member
 
Registered: Jun 2005
Location: Indiana, USA
Distribution: OpenBSD, Ubuntu
Posts: 892

Rep: Reputation: 41
Quote:
Originally Posted by vkmgeek
Why is it huge difference? Which one is better? To avail a huge amount of memory for call stack is good or bad?
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.
 
Old 11-05-2006, 02:46 AM   #5
jlliagre
Moderator
 
Registered: Feb 2004
Location: Outside Paris
Distribution: Solaris10, Solaris 11, Mint, OL
Posts: 9,523

Rep: Reputation: 365Reputation: 365Reputation: 365Reputation: 365
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.
 
Old 11-05-2006, 11:57 AM   #6
taylor_venable
Member
 
Registered: Jun 2005
Location: Indiana, USA
Distribution: OpenBSD, Ubuntu
Posts: 892

Rep: Reputation: 41
Quote:
Originally Posted by jlliagre
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.
That is, statically allocated local variables, correct? IIRC, dynamically allocated data goes on the heap.

Quote:
Originally Posted by jlliagre
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.
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.

Quote:
Originally Posted by jlliagre
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'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.
 
Old 11-05-2006, 12:51 PM   #7
soggycornflake
Member
 
Registered: May 2006
Location: England
Distribution: Slackware 10.2, Slamd64
Posts: 249

Rep: Reputation: 31
Quote:
That is, statically allocated local variables, correct? IIRC, dynamically allocated data goes on the heap.
No, static variables go in the data/bss segment(s), regardless of whether they are declared inside a function of not.

e.g.

Code:
void foo()
{
   int array[1000];
   static int counter = 1;
   char *str = malloc(10);
}
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.
 
Old 11-05-2006, 02:53 PM   #8
jlliagre
Moderator
 
Registered: Feb 2004
Location: Outside Paris
Distribution: Solaris10, Solaris 11, Mint, OL
Posts: 9,523

Rep: Reputation: 365Reputation: 365Reputation: 365Reputation: 365
Quote:
Originally Posted by taylor_venable
That is, statically allocated local variables, correct?
No, I mean non static local variables, a.k.a. automatic variables.
Quote:
IIRC, dynamically allocated data goes on the heap.
Dynamically allocated (i.e. malloc'ed) variables data go on the heap except when mmap allocated.
Quote:
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
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.

Last edited by jlliagre; 11-05-2006 at 02:54 PM.
 
Old 11-05-2006, 04:08 PM   #9
taylor_venable
Member
 
Registered: Jun 2005
Location: Indiana, USA
Distribution: OpenBSD, Ubuntu
Posts: 892

Rep: Reputation: 41
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.])
 
Old 11-06-2006, 03:20 AM   #10
jlliagre
Moderator
 
Registered: Feb 2004
Location: Outside Paris
Distribution: Solaris10, Solaris 11, Mint, OL
Posts: 9,523

Rep: Reputation: 365Reputation: 365Reputation: 365Reputation: 365
Quote:
Originally Posted by taylor_venable
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].
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".
Quote:
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.]
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.
Quote:
(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.])
Interesting.
However, the need for strongly recursive support is unfrequent in "real-life" programming. It is more of an academic topic.
 
Old 11-06-2006, 08:52 AM   #11
vkmgeek
Member
 
Registered: Feb 2006
Location: Ahmedabad
Distribution: rhel5
Posts: 185
Blog Entries: 2

Original Poster
Rep: Reputation: 31
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.
 
Old 11-06-2006, 10:42 AM   #12
jlliagre
Moderator
 
Registered: Feb 2004
Location: Outside Paris
Distribution: Solaris10, Solaris 11, Mint, OL
Posts: 9,523

Rep: Reputation: 365Reputation: 365Reputation: 365Reputation: 365
Quote:
Originally Posted by vkmgeek
THat is why I love open Source, OPen Discussion, and Linux at the end.
or BSD and Solaris for that matter.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
how to disable 4K stack size wahaha Linux - Wireless Networking 1 08-26-2006 07:33 AM
16K stack size in 2.6..xx quietguy47 Linux - Kernel 3 04-24-2006 02:21 PM
FC4 - new stack size? DJOtaku Fedora 2 10-07-2005 01:22 PM
Thread call stack StephenG Linux - General 3 08-24-2005 11:34 PM
Stack size decision atul_mehrotra Programming 2 10-08-2004 05:32 AM


All times are GMT -5. The time now is 11:33 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration