4

When I write the following program, it works correctly i.e. the bitset array is declared outside the main() method.

Correctly Works

#include <iostream>
#include <bitset>

using namespace std;

bitset<5000> set[5000];

int main(){
    cout<<"program runs fine"<<endl;
    return 0;
}

But I get stack-overflow exception when I create it inside the main method. Can anyone explain in detail as to what is going on here? Normally I see stack-overflow exceptions in recursive methods. So who is using the stack here?

#include <iostream>
#include <bitset>

using namespace std;


int main(){
    bitset<5000> set[5000];
    cout<<"program runs fine"<<endl;
    return 0;
}

Doesn't work and throws stack-overflow exception enter image description here

Varun Sharma
  • 2,591
  • 8
  • 45
  • 63
  • **TL;DR;:** In general _'non global arrays'_ and references to them might go out of scope, and **be invalid** for any access afterwards!! – πάντα ῥεῖ Mar 18 '14 at 23:05
  • 3
    Defining a large local variable is a good way to get a stack overflow. Use dynamic allocation for large variables. – Paul R Mar 18 '14 at 23:06
  • Sorry I didn't get your point. The second program doesn't even run but if I reduce the size to 50 then it runs fine so something to do with memory but looks like there are different types of memory involved here. I have heard of stack and heap. But there is no dynamic memory allocation here so no heap is involved. – Varun Sharma Mar 18 '14 at 23:07
  • Just a shot into dark, I think @PaulR is right ... – πάντα ῥεῖ Mar 18 '14 at 23:11

3 Answers3

5

Declaring it in main is declaring it in "automatic storage" AKA the stack. Declaring it outside of main, is declaring it in "static storage" AKA global data. You are declaring a ton of data. std::bitset<5000> is 632 bytes on my system with VS2013 (likely an alignment from 5000/8). And you are declaring 5000 of them. 5000 * 632 = 3 160 000 bytes, or roughly 3 Megabytes. Default in VS2013 is 1 megabyte for the stack, which is why you are seeing an overflow.

There are three kinds of storage: automatic, storage, and dynamic. These are colloquially referred to as stack, static (in some cases, global) and heap memory respectively:

int static_int;

int main() {
  int automatic_int;
  static int local_static_int; // also static storage!
  int * dynamic_int_ptr = new int;
}
  • Automatic storage is allocated at a mix of compile time/run time. The stack expands at run-time entry to a function in order to hold local variables, but this is a known compile-time value since the number of variables and their sizes are well known (I'm ignoring dynamic arrays here because they are non-standard) These variables are constructed on scope entry, and destructed on scope exit.
  • Static storage is allocated at compile time. This memory is paid for up front, and constructed at program start. It is destructed when the program exits.
  • Dynamic storage is allocated at run-time. This memory is allocated by new and a pointer to some blob that holds your shiny new data is returned. These variables are constructed when new is called, and destructed when delete is called.
Sam Cristall
  • 4,328
  • 17
  • 29
  • So basically there are three types of storage - stack, heap and static storage/global data ? I have only heard of first two. – Varun Sharma Mar 18 '14 at 23:10
  • @VVV I updated my answer with more info! Let me know if you need further clarification – Sam Cristall Mar 18 '14 at 23:18
  • Thanks buddy. I saw Nilesh's answer's link and it turns out there are 5 types of memory actually. Time to refresh my c++ ! Have been embedded in c# world for quite a while. – Varun Sharma Mar 18 '14 at 23:20
  • 2
    @VVV That answer is good, but actually very platform specific. C++ does not say anything about `.data` and `.bss`, they are a solution on how to implement static storage. As far as C++ is concerned, there are only 3 kinds of storage: automatic, static and dynamic. – Sam Cristall Mar 18 '14 at 23:26
  • @SamCristall: I agree with you. Organization of segments in a process could be different depending on the platform & there could be different ways of implementing static storage. – Nilesh Mar 18 '14 at 23:44
  • Thanks guys, changing it to static inside main() works as mentioned above with "local_static_int". – Varun Sharma Mar 19 '14 at 00:36
3

Because when you declare array as global, memory is allocated in the data segment of the process while when you try to declare it inside a function, memory is allocated on the stack. Since you are allocating large amount of memory, it results in stackoverflow exception.

Edit: Here is good explanation of the memory allocation.

Community
  • 1
  • 1
Nilesh
  • 5,955
  • 3
  • 24
  • 34
1

You are trying to create (5000*5000)/8 bytes - 3Megs of data on the program stack which is causing a Stack Overflow as reported. You do not have enough stack space in your program for this. When you create it as a global, it is inserted in your programs data segment.

Chris
  • 2,655
  • 2
  • 18
  • 22
  • Thanks but isn't heap used for dynamic memory allocation? So something like int*x = new int[10000] will use heap (irrespective of whether its inside or outside a c++ function). Please let me know if my reasoning is right. – Varun Sharma Mar 18 '14 at 23:09
  • Your understanding is right. When you use operator like new, memory will be allocated on heap. In your case, you are declaring it as global & not allocating memory on heap. – Nilesh Mar 18 '14 at 23:10
  • 2
    Yep. Been reading too many Heap v Stack questions on SO recently, got heap on the brain. It's in the data segment not the heap, which is static and depends on your program. Noting that I'm correcting this. – Chris Mar 18 '14 at 23:13