-1
#include<stdio.h>    
int main(){
  scanf("%d",&Testcase)
  while(Testcase--){
  int a[100000] = {0};

  /* Other statements */

  }
}

In the above program, for every Testcase, the program allocates 100000*sizeof(int) bytes of memory. But in codechef the maximum memory that we can use is about 10 MB. So, is there any optimal way to reduce the memory usage?

P.S. I have tried declaring it as a global variable. But the problem with that is, after every test case, the old Testcase values interferes with the new Testcase values.

Also, I have tried reinitializing the entire array with value 0, after every Testcase, using a for loop. But that takes so long, exceeding the time requirement which is 3 seconds.

The problem I'm trying to solve is http://www.codechef.com/MARCH13/problems/FIRESC

Edit: The total allowable memory limit is actually about 10 MB

  • 1
    What about [dynamic allocation](http://www.cplusplus.com/reference/cstdlib/malloc/)? –  Mar 10 '13 at 15:19
  • If the maximum memory you can use is 64kB, then there is no way to allocate 100k ints! Do you actually mean "the maximum **stack** memory"? – Oliver Charlesworth Mar 10 '13 at 15:20
  • @OliCharlesworth http://www.codechef.com/MARCH13/problems/FIRESC This is the problem I'm solving –  Mar 10 '13 at 15:20
  • The name of the site gives a hint - the stack is a limited size, it's not designed for huge data structures. – teppic Mar 10 '13 at 15:23
  • Huh? You've just changed your question from "64kB" to "10MB". 10MB is obviously more than sufficient for 100k ints, so what's the problem? – Oliver Charlesworth Mar 10 '13 at 15:27
  • @OliCharlesworth But the site is giving back Runtime error (SEGMENTATION fault) But the program works just fine in my system, I'm sure that it's the memory issue –  Mar 10 '13 at 15:30

1 Answers1

4

If you declare the array as a global variable, it will be allocated into the .bss section which again is not very optimal. If you wish to allocate a large section of memory, malloc would be the preferred way where you would allocate the memory in heap section.

Ganesh
  • 5,880
  • 2
  • 36
  • 54
  • malloc doesn't initialize the memory.. wont that create any problem –  Mar 10 '13 at 15:33
  • @FrodoBaggins If you wish to initialize it to `zero` always, then please use `calloc` – Ganesh Mar 10 '13 at 15:34
  • If the usage allows it, allocation in global static or memory is fine. (and superior, IMO). The file size of the executable will not be inflated, and `initialised with zeros` will cause the pages to be automagically be initialised by faulting-in cloned pages from /dev/zero. (on a typical unix platform with MMU) – wildplasser Mar 10 '13 at 15:50
  • @wildplasser Yes, theoritically if the usage allows it and if there is sufficient memory in the system, then it could be a global array. However, in an embedded system, `.bss` holds static/global variables which might be critical to execution. To facilitate good speed up, the `.bss` section is typically allocated into a memory closer to the CPU. However, if we allocate a huge array, the `.bss` section would have to be allocated into slower memory, thereby impacting the rest of the software system. A related discussion: http://stackoverflow.com/questions/9535250/why-is-the-bss-segment-required – Ganesh Mar 10 '13 at 16:11