Как объявить и использовать огромные массивы из 1 миллиарда целых чисел в C?

Я реализую последовательную программу для сортировки как quicksort. Я хотел бы проверить производительность моей программы в огромном массиве из 1 или 10 миллиардов целых чисел. Но проблема в том, что я получаю ошибку сегментации из-за размера массива.

Пример кода объявления этого массива:

#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;
}

У меня есть предложение использовать функцию mmap. Но я не знаю, как его использовать? может ли кто-нибудь помочь мне использовать его?

Я работаю над 64-битной версией Ubuntu 10.04, gcc версии 4.4.3.

Спасибо за ваши ответы.

Ответ 1

Майкл прав, ты не можешь вместить так много в стек. Тем не менее, вы можете сделать его глобальным (или статическим), если не хотите размещать его неправильно.

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

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

Ответ 2

Вы должны использовать malloc для такого распределения. Это много в стеке будет терпеть неудачу почти каждый раз.

int *list;

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

Это помещает выделение в кучу, где доступно намного больше памяти.

Ответ 3

Вероятно, вы не создаете столь большой массив, и если вы это сделаете, вы, конечно же, не создадите его в стеке; стек просто не такой большой.

Если у вас есть 32-разрядное адресное пространство и 4-байтовый int, вы не можете создать массив с миллиардом int s; там просто не будет достаточно непрерывного пространства в памяти для этого большого объекта (вероятно, не будет достаточного смежного пространства для объекта, являющегося частью этого размера). Если у вас есть 64-разрядное адресное пространство, вы можете уйти с выделенным пространством.

Если вы действительно хотите попробовать, вам нужно либо создать его статически (т.е. объявить массив в области файла или с помощью квалификатора static в функции), либо динамически (используя malloc).

Ответ 4

В Linux-системах malloc из очень больших кусков просто выполняется mmap под капотом, поэтому, возможно, слишком утомительно смотреть на это.

Будьте осторожны, чтобы у вас не было ни переполнения (целые числа со знаком), ни молчания (целые числа без знака) для границ массива и индексов. Используйте size_t как тип для этого, так как вы находитесь на 64-битной машине, тогда это должно работать.

Но, как привычка, вы должны обязательно проверить свои границы на SIZE_MAX, что-то вроде assert(N*sizeof(data[0]) <= SIZE_MAX).

Ответ 5

Распределение стека заставляет его ломаться. N = 1Gig ints = > 4Gig памяти (как с 32-битным, так и с 64-битным компилятором). Но если вы хотите измерить производительность быстрой сортировки или аналогичный ваш алгоритм, это не так. Попробуйте вместо этого использовать несколько быстросортированных последовательностей на подготовленных образцах с большим размером.

-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

Теперь у вас есть очень точный ответ на то, сколько времени ваш алгоритм потребляет. Запустите его несколько раз, чтобы почувствовать "насколько точно" (каждый раз используйте новое семя srand (seed)). И измените N для дополнительной проверки.

Ответ 6

Другим вариантом является динамическое распределение связанного списка меньших массивов. Вам придется обернуть их функциями доступа, но гораздо более вероятно, что вы сможете захватить 16 256 Мбайт кусков памяти, чем один блок объемом 4 ГБ.

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