7

I'm trying to time and compare sorting algorithms. From what I understand: sizeof(int) is 4 bytes, therefore int array[one million]; yields (4) million bytes which is 4,000 kb or 4mb roughly.

So why can't I? I'm pretty sure I have more. 2gb to be precise.

I'm using gcc if that means anything.

lightburst
  • 231
  • 3
  • 19

4 Answers4

10

You can't have that many integers on stack.

Try allocating space on heap for your array.

int *array = malloc(1000000*sizeof(int));
// if array is not null, then you have an array with 1,000,000 ints.

After you are done with your sorting algorithms, you free the array:

free(array); // frees memory allocated before
Pablo Santa Cruz
  • 176,835
  • 32
  • 241
  • 292
  • I completely forgot about the stack... So ABSOLUTELY ALL variables in a function goes to the stack? even those that exploit storage duration? – lightburst Nov 13 '11 at 12:51
  • @lightburst: All variables inside a function goes to stack. Unless they're declared static. – Pablo Santa Cruz Nov 13 '11 at 12:54
  • I heard that the operating system can allocate stack when needed. Why can't that be the case here? Or is there just a threshold where the OS just won't allocate anymore, which I have met? – lightburst Nov 13 '11 at 12:59
  • I haven't used GCC, but on MS compilers the maximum stack size is set up as a linker option, and defaults vary with platform. – SmacL Nov 13 '11 at 13:02
  • 14
    Without stack limits, there would be no Stack Overflow. – u0b34a0f6ae Nov 13 '11 at 13:10
  • 1
    @ShaneMacLaughlin, it isn't compiler specific, it depends on the OS. On Windows, the stack limit is stored in the executable (at least last time I looked at it, years ago), on Unix variants I know of -- IIRC it is specified by POSIX, I don't know how it is handled by POSIX layers for Windows -- it is part of the environment (see ulimit(bourne shells)/limit(cshell) shell built in to query and change). Note that if you increase the stack size, you may reduce the number of threads you are able to launch or the maximum size of the heap. – AProgrammer Nov 13 '11 at 13:40
  • +1, I only think that `malloc(sizeod(int[1000000]))` is a bit more intuitive. – Jens Gustedt Nov 13 '11 at 14:21
4

It's likely you are trying to allocate it on the stack, which is small.

  • Make the array static or global (same thing really, but with different visibility)

    static int arr[...]

  • Use malloc

    int *p = malloc(... * sizeof *p);
cnicutar
  • 178,505
  • 25
  • 365
  • 392
2

The statement 

int array[one million];

declares and stores your array on the Stack. The size of your program's stack is pretty small, and cannot contain 1 million ints. Instead, what you should do, is declare the array on the Heap. For that, create a pointer to the array and use the malloc() function to allocate memory. This way, the memory is allocated on the heap, and you have way more memory for utilisation.

int *arrayName = malloc(1000000*sizeof(int));

You should always check the pointer for the value returned, since the malloc may fail, and it will return a NULL value. If you try to access such a pointer, your program will terminate abruptly. So make sure, to check for correct allocation.

Also, always remember to 

free(arrayName);

when you are done using the array. Else, it may lead to a memory leak, in a certain more complex programs.

For a better understanding of Stacks and Heaps, refer to this Question: What and where are the stack and heap?

Community
  • 1
  • 1
darnir
  • 4,870
  • 4
  • 32
  • 47
0

It is highly recommended that huge-sized variables should go to the heap via malloc or new. But, you can still have such big array in stack by increasing the stack size. This is often needed when you could have extremely deep recursion.

Linux/gcc has the 8MB of default size for stack, while Windows has 1MB. The stack size may be increased by tweaking linker options or binaries.

[EDITED] For example, you may increase the stack size in gcc:

gcc -Wl,--stack,16777216 hello.c (This is only for MigW/cygwin gcc on Windows)

So, the stack will be 16MB.

Also, the stack size can be modified the command ulimit by like (this is the easist way in Linux):

ulimit -s 16777216

Note that ulimit -s will give you the current size of the stack.

Finally, you may call setrlimit in your program.

minjang
  • 8,860
  • 9
  • 42
  • 61
  • According to the manpage, "This option is specific to the i386 PE targeted port of the linker" (i.e. only works for outputting Windows binaries). Seems like there isn't an option for ELF binaries. – darnir Nov 13 '11 at 13:09
  • Thanks, it was only for gcc on Windows. Edited. – minjang Nov 13 '11 at 13:14