How to declare and use huge arrays of 1 billion integers in C ?

Question

I'm implementing a sequential program for sorting like quicksort. I would like to test the performance of my program in a huge array of 1 or 10 billions of integers. But the problem is that I obtain a segmentation error due to the size of the array.

A sample code of declaration of this array:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 1000000000

int main(int argc, char **argv)
{
  int list[N], i;
  srand(time(NULL));
  for(i=0; i<N; i++)
     list[i] = rand()%1000;
  return 0;
}

I got a proposition to use mmap function. But I don't know how to use it ? can anybody help me to use it ?

I'm working on Ubuntu 10.04 64-bit, gcc version 4.4.3.

Thanks for your replies.

Answer 1

You must use malloc for this sort of allocation. That much on the stack will fail nearly every time.

int *list;

list  = (int *) malloc(N * sizeof(int));

This puts the allocation on the heap where there is a lot more memory available.

Answer 2

You probably don't create so large an array and if you do you certainly don't create it on the stack; the stack just isn't that big.

If you have a 32-bit address space and a 4-byte int, then you can't create an array with a billion ints; there just won't be enough contiguous space in memory for that large an object (there probably won't be enough contiguous space for an object a fraction of that size). If you have a 64-bit address space, you might get away with allocating that much space.

If you really want to try, you'll need either to create it statically (i.e., declare the array at file scope or with the static qualifier in the function) or dynamically (using malloc).

Answer 3

Michael is right, you can't fit that much on the stack. However, you can make it global (or static) if you don't want to malloc it.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 1000000000
int list[N];

int main(int argc, char **argv)
{
  int i;
  srand(time(NULL));
  for(i=0; i<N; i++)
     list[i] = rand()%1000;
  return 0;
}

Answer 4

Another option is to dynamically allocate a linked list of smaller arrays. You'll have to wrap them with accessor functions, but it's far more likely that you can grab 16 256 MB chunks of memory than a single 4 GB chunk.

typedef struct node_s node, *node_ptr;
struct node_s
{
    int data[N/NUM_NODES];
    node_ptr next;
};

Answer 5

On linux systems malloc of very large chunks just does a mmap under the hood, so it is perhaps too tedious to look into that.

Be careful that you don't have neither overflow (signed integers) nor silent wrap (unsigned integers) for your array bounds and indices. Use size_t as a type for that, since you are on a 64bit machine, this then should work.

But as a habit you should definitively check your bounds against SIZE_MAX, something like assert(N*sizeof(data[0]) <= SIZE_MAX), to be sure.

Answer 6

The stack allocations makes it break. N=1Gig ints => 4Gig of memory (both with a 32-bit and a 64-bit compiler). But if you want to measure the performance of quicksort, or a similar algorithm of yours, this is not the way to go about it. Try instead to use multiple quicksorts in sequence on prepared samples with a large size.

-create a large random sample not more than half your available memory.
make sure it doesn''t fill your ram!
If it does all measuring efforts are in vain. 
500 M elements is more than enough on a 4 gig system.

-decide on a test size ( e.g. N = 100 000 elements)
-start timer 
--- do the algoritm for ( *start @ i*N, *end @ (i+1)*N) 
(rinse repeat for next i until the large random sample is depleted)
-end timer

Now you have a very precise answer to how much time your algorithm has consumed. Run it a few times to get a feel of "how precise" (use a new srand(seed) seed each time). And change the N for more inspection.