Comment déclarer et utiliser d’énormes tableaux de 1 milliard d’entiers en C?

J’implémente un programme séquentiel pour sortinger comme quicksort. Je voudrais tester les performances de mon programme dans une vaste gamme de 1 ou 10 milliards d’entiers. Mais le problème est que j’obtiens une erreur de segmentation en raison de la taille du tableau.

Un exemple de code de déclaration de ce tableau:

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

J’ai eu une proposition d’utiliser la fonction mmap. Mais je ne sais pas comment l’utiliser? quelqu’un peut-il m’aider à l’utiliser?

Je travaille sur Ubuntu 10.04 64 bits, gcc version 4.4.3.

Merci pour vos réponses.

Michael a raison, vous ne pouvez pas mettre autant sur la stack. Cependant, vous pouvez le rendre global (ou statique) si vous ne voulez pas le mallocaliser.

 #include  #include  #include  #define N 1000000000 int list[N]; int main(int argc, char **argv) { int i; srand(time(NULL)); for(i=0; i 

Vous devez utiliser malloc pour ce type d’allocation. Cela sur la stack échouera presque à chaque fois.

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

Cela place l’allocation sur le tas où il y a beaucoup plus de mémoire disponible.

Vous ne créez probablement pas un tableau si grand et si vous le faites, vous ne le créez certainement pas sur la stack; la stack n’est pas si grosse.

Si vous avez un espace d’adressage 32 bits et un entier de 4 octets, vous ne pouvez pas créer de tableau avec un milliard d’ int s; il n’y aura tout simplement pas assez d’espace contigu en mémoire pour un object de grande taille (il n’y aura probablement pas assez d’espace contigu pour un object d’une fraction de cette taille). Si vous disposez d’un espace d’adressage 64 bits, vous pouvez vous en tirer en allouant autant.

Si vous voulez vraiment essayer, vous devrez soit le créer statiquement (c.-à-d. Déclarer le tableau à la scope du fichier ou avec le qualificateur static dans la fonction) ou dynamicment (à l’aide de malloc ).

Sur les systèmes linux, malloc de très gros morceaux ne fait qu’un mmap sous le capot, il est donc peut-être trop fastidieux de se pencher là-dessus.

Veillez à ce que vous n’ayez ni débordement (entiers signés), ni bouclage silencieux (entiers non signés) pour les limites et les index de votre tableau. Utilisez size_t comme type pour cela, puisque vous êtes sur une machine 64 bits, cela devrait alors fonctionner.

Mais, par habitude, vous devez vérifier vos limites avec SIZE_MAX , comme assert(N*sizeof(data[0]) <= SIZE_MAX) , pour en être sûr.

Les allocations de stack permettent de casser. N = 1Gig ints => 4Gig de mémoire (avec compilateur 32 bits et 64 bits). Mais si vous souhaitez mesurer les performances de quicksort, ou d’un algorithme similaire, ce n’est pas la solution. Essayez plutôt d’utiliser plusieurs quicksorts en séquence sur des échantillons préparés de grande taille.

 -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 ( eg 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 

Vous avez maintenant une réponse très précise à la quantité de temps que votre algorithme a consommé. Exécutez-le plusieurs fois pour avoir une idée de la précision (utilisez une nouvelle graine de srand (graine) à chaque fois). Et changez le N pour plus d’inspection.

Une autre option consiste à allouer de manière dynamic une liste chaînée de tableaux plus petits. Vous devrez les encapsuler avec des fonctions d’accesseur, mais il est beaucoup plus probable que vous puissiez récupérer 16 blocs de 256 Mo de mémoire qu’un seul bloc de 4 Go.

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