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

Question

Я реализую последовательную программу для сортировки типа быстрой сортировки. Я хотел бы проверить производительность моей программы в огромном массиве из 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. Но я не знаю, как его использовать? Кто-нибудь может мне помочь использовать его?

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

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

Answer 1

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

int *list;

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

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

Answer 2

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

#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 3

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

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

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

Answer 4

Распределение стека заставляет его сломаться.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

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

Answer 5

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

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

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

Answer 6

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

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