Can I allocate a 2D array of size [20000][20000] (roughly 1.5 GB) on the heap (by dynamic allocation) or as a global variable ?
// heap
int** dp = (int**)malloc(20000*sizeof(int*));
for(int i=0; i<20000; ++i) dp[i] = (int*)malloc(n*sizeof(int));
// global variable outside of main() function
int dp[20000][20000];
Can somebody please explain the bound of the memory avaliable on heap and global area?
please help…
nope, if your question is regarding ACM Amrita ICPC Online Problem Lauch Tower.
Using just two rows you can calculate the answer, by converting dp[20000,20000] to dp[20000,2], even after that your solution will get TLE verdict, you need another approach of Dynamic Programming.
See the editorial by Anudeep,
I knew that it will get TLE, but that question just made me curious to know about the memory limit of heap and global data segment.
Can you please give the approximate memory bounds of both…?
When I allocated [20000,20000] on the heap and also global, it worked fine on my Ubuntu but gave SIGABRT (vector dp(20000,vi(20000))) and sigsegv (int** dp) on codechef
The maximum memory that you can allocate is 2*10^7, if you declare your array globally. In your question you are allocating 4*10^8 memory space which is not allowed.
@roman8, what about the heap (dynamic allocation) ?
As you know that every process in Linux environment has these segments.
The memory that you are talking about “Heap” comes within a Process Data Segment which consists of uninitialized data, initialized data and heap. So to view/alter the limits of a process, you can use ulimit command.
To Programmatically change the limits you can use getrlimit/setrlimit.
There are two type of limits
The soft limit is the value that the kernel enforces for the corresponding resource. The hard limit acts as a ceiling for the soft limit: an unprivileged process may set only its soft limit to a value in the range from 0 up to the hard limit, and (irreversibly) lower its hard limit.
Ulimit will only change the values for that shell and it’s child processes only. It will not change the values system wide and is not permanent.
To set the values permanantly make changes in /etc/security/limits.conf. as root.
same as for static. Dynamically you cannot allocate more than 2*10^7 memory space.
So you mean to say, the heap and the data segment has the same bound on the codechef judge (spoj) ? Why is it so? Any link or reference is appreciated…
@sumanth232 If you are running the code on your PC it depends on the RAM available and for OJ problems it’s mentioned in the constraints section.