Come dichiarare e utilizzare enormi matrici di 1 miliardo di interi in C?

Question

Sto implementando un programma sequenziale per l'ordinamento come quicksort. Vorrei testare le prestazioni del mio programma in una vasta gamma di 1 o 10 miliardi di interi. Ma il problema è che ottengo un errore di segmentazione a causa delle dimensioni dell'array.

Un codice di esempio di dichiarazione di questa matrice:

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

ho avuto una proposta di utilizzare la funzione mmap. Ma non so come usarlo? qualcuno può aiutarmi a usarlo?

Sto lavorando su Ubuntu 10.04 64-bit, gcc versione 4.4.3.

Grazie per le vostre risposte.

Answer 1

Michael ha ragione, non si può stare così tanto nello stack. Tuttavia, puoi renderlo globale (o statico) se non vuoi mallocarlo.

#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

È necessario utilizzare malloc per questo tipo di allocazione. Quella parte in pila fallirà quasi ogni volta.

int *list; 

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

Questo pone l'allocazione nello heap in cui è disponibile molta più memoria disponibile.

Answer 3

Probabilmente non si crea un array così grande e, se lo si fa, sicuramente non lo si crea nello stack; lo stack non è così grande.

Se si dispone di uno spazio indirizzo a 32 bit e di un byte int a 4 byte, non è possibile creare un array con un miliardo di int s; non ci sarà abbastanza spazio contiguo in memoria per quel grande oggetto (probabilmente non ci sarà abbastanza spazio contiguo per un oggetto una frazione di quella dimensione). Se si dispone di uno spazio per gli indirizzi a 64 bit, si potrebbe farla franca allocando così tanto spazio.

Se davvero si vuole provare, è necessario sia per crearlo in modo statico (vale a dire, dichiarare la matrice nell'ambito di file o con il qualificatore static nella funzione) o dinamicamente (utilizzando malloc).

Answer 4

Un'altra opzione è allocare dinamicamente un elenco collegato di array più piccoli. Dovrai avvolgerli con le funzioni accessorie, ma è molto più probabile che tu possa afferrare 16 256 MB di pezzi di memoria di un singolo chunk da 4 GB.

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

Answer 5

su sistemi Linux malloc di grandi blocchi appena fa un mmap sotto il cofano, quindi è forse troppo noioso per guardare in quella.

Fare attenzione a non disporre di overflow (interi con segno) né di wrap invisibile (interi senza segno) per i limiti e gli indici dell'array. Utilizzare size_t come un tipo per quello, poiché si è su una macchina a 64 bit, questo dovrebbe funzionare.

Ma come abitudine, è necessario verificare definitivamente i limiti contro SIZE_MAX, ad esempio assert(N*sizeof(data[0]) <= SIZE_MAX), per sicurezza.

Answer 6

Le allocazioni di stack si interrompono. N = 1Gig ints => 4Gig di memoria (entrambi con un compilatore a 32 bit e 64 bit).Ma se vuoi misurare le prestazioni di quicksort, o un tuo algoritmo simile, questo non è il modo per farlo. Provare invece a utilizzare più quicksorts in sequenza su campioni preparati con una dimensione grande.

-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 

Ora hai una risposta molto precisa a quanto tempo il tuo algoritmo ha consumato. Eseguilo alcune volte per avere un'idea di "quanto preciso" (usa ogni volta un nuovo seme di srand (seme)). E cambia la N per ulteriori controlli.