-2

Why is it that my first and second programs are running fine but the third one is giving segmentation fault? I don't think the problem is with memory limit because even long long dp[40][100000] is running fine but if I try printing any value say std::cout << dp[0][0]; again it's giving error. I am really confused, I've tried compiling this code on Jdoodle and GDB online compiler. Both are giving the same error.

First:

#include<iostream>
#include<vector>


int main(){
    std::vector<long long> price(20);
    std::vector<long long> pages(20);
   
    return 0;
}

Second:

#include<iostream>
#include<vector>


int main(){

    long long dp[20][100000];    
    return 0;
}

Third:

#include<iostream>
#include<vector>


int main(){
    std::vector<long long> price(20);
    std::vector<long long> pages(20);

    long long dp[20][100000];    
    return 0;
}

Edit: I am interested in knowing why the second program is running fine and the third is giving segmentation fault. I think either both or none of them should run without any errors.

Keshav Garg
  • 85
  • 8
  • 4
    Local variables are usually placed on the stack, and the stack is limited (on Linux the default process stack is 8 MiB). Assuming that `long long` is 64 bits and therefore 8 bytes in size, then your array will use `20 * 100000 * 8` bytes, which is 16 *million* bytes and almost double the size of the Linux per-process stack. – Some programmer dude Apr 10 '21 at 18:27
  • 2
    As for why it seems to work when you only define the array and not use it, then it's probably being optimized away. Once you use the array, it will be in the program and lead to the stack overflow. – Some programmer dude Apr 10 '21 at 18:29
  • 1
    A `std::vector` uses *dynamic* memory, which is usually in a region that has bigger capacity. – Thomas Matthews Apr 10 '21 at 19:22
  • 2
    Does this answer your question? [Getting a stack overflow exception when declaring a large array](https://stackoverflow.com/questions/571945/getting-a-stack-overflow-exception-when-declaring-a-large-array) – ChrisMM Apr 10 '21 at 19:33
  • @ChrisMM Partly, It does not explain why the second code is running fine. I think Some programmer dude has explained it well but I don't understand why it is not being optimized in the third code. – Keshav Garg Apr 11 '21 at 06:58

1 Answers1

1

Here are some other options to try:

int main()
{
    static long long dp[20][100000];
    std::cout << "Size of dp: " << sizeof(dp) << "\n";
    return 0;
}

In many platforms, a variable declared as static within a function is placed into a different region, that usually has more capacity than local variables.

You could dynamically allocate:

long long * dp = new long long [20][100000];

Dynamic memory, a.k.a. heap, usually has a large capacity, definitely larger than the local variable area.

You could also allocate in the "global" space:

static long long dp[20][100000];
int main()
{
     //...
     return 0;
}

In most systems, the global regions is a lot larger than the local variable region (a.k.a. stack).

Thomas Matthews
  • 56,849
  • 17
  • 98
  • 154
  • Thanks for suggesting alternate methods to declare arrays but that doesn't answer why the second code is running fine while the third isn't. – Keshav Garg Apr 11 '21 at 07:05
  • The `std::vector` class has pieces that are declared local and data that is dynamically allocated. Maybe the local data of the `vector` has pushed the memory allocation over the limit. – Thomas Matthews Apr 11 '21 at 17:58