Jak deklarować i używać ogromnych tablic o wielkości 1 miliarda w C?

Question

Wdrażam sekwencyjny program do sortowania jak quicksort. Chciałbym przetestować wydajność mojego programu w ogromnej ilości 1 lub 10 miliardów liczb całkowitych. Ale problemem jest to, że otrzymuję błąd segmentacji ze względu na rozmiar tablicy.

Próbkę kodu deklaracji tej tablicy:

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

Dostałem propozycję korzystania z funkcji mmap. Ale nie wiem, jak z niego korzystać? Czy ktoś może mi pomóc go użyć?

Pracuję nad 64-bitowym systemem Ubuntu 10.04, gcc w wersji 4.4.3.

Dzięki za odpowiedzi.

Answer 1

Michael ma rację, na stosie nie można zmieścić tak dużo. Możesz jednak uczynić go globalnym (lub statycznym), jeśli nie chcesz go zdekompresować.

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

Musisz użyć malloc do tego przydziału. Tyle na stosie zawiodą prawie za każdym razem.

int *list; 

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

Spowoduje to umieszczenie przydziału na stercie, gdzie jest znacznie więcej dostępnej pamięci.

Answer 3

Prawdopodobnie nie tworzysz tak dużej tablicy, a jeśli nie, to nie twórz jej na stosie; stos po prostu nie jest taki duży.

Jeśli masz 32-bitową przestrzeń adresową i 4-bajtowe int, to nie możesz utworzyć tablicy z miliardem int s; po prostu nie będzie wystarczającej przestrzeni w pamięci dla tego dużego obiektu (prawdopodobnie nie będzie wystarczającej przestrzeni dla obiektu ułamek tej wielkości). Jeśli masz 64-bitową przestrzeń adresową, możesz uciec przy przydzielaniu tak dużej ilości miejsca.

Jeśli naprawdę chcesz spróbować, musisz go utworzyć statycznie (tj. Zadeklarować tablicę w zakresie pliku lub z kwalifikatorem static w funkcji) lub dynamicznie (przy użyciu malloc).

Answer 4

Inną opcją jest dynamiczne przydzielanie połączonej listy mniejszych macierzy. Będziesz musiał owijać je dodatkowymi funkcjami, ale jest znacznie bardziej prawdopodobne, że możesz pobrać 16 256 MB porcji pamięci niż jeden porcja 4 GB.

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

Answer 5

W systemach Linux malloc z bardzo dużymi kawałkami właśnie robi mmap pod maską, więc jest to chyba zbyt uciążliwe zajrzeć do tego.

Należy uważać, aby nie mieć ani przepełnienia (liczby całkowite ze znakiem), ani cichego oblewania (liczby całkowite bez znaku) dla granic tablicy i indeksów. Użyj size_t jako typ do tego, ponieważ jesteś na maszynie 64-bitowej, to powinno działać.

Ale na pewno powinieneś definitywnie sprawdzić swoje granice przed SIZE_MAX, coś jak assert(N*sizeof(data[0]) <= SIZE_MAX), aby mieć pewność.

Answer 6

Alokacja stosów powoduje jej podział. N = 1Gig ints => 4Gig pamięci (zarówno z kompilatorem 32-bitowym, jak i 64-bitowym).Ale jeśli chcesz zmierzyć wydajność programu quicksort lub podobnego algorytmu, nie jest to sposób, aby to osiągnąć. Spróbuj zamiast tego użyć wielu quicksorts w sekwencji na przygotowanych próbkach o dużym rozmiarze.

-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 

Teraz masz bardzo precyzyjną odpowiedź na pytanie, ile czasu zużył Twój algorytm. Uruchom go kilka razy, aby poczuć "jak precyzyjnie" (używaj za każdym razem nowego nasienia). I zmień N, aby uzyskać więcej kontroli.