¿Cómo declarar y usar grandes matrices de mil millones de enteros en C?

Question

Estoy implementando un programa secuencial para ordenar como quicksort. Me gustaría probar el rendimiento de mi programa en una gran variedad de 1 o 10 mil millones de enteros. Pero el problema es que obtengo un error de segmentación debido al tamaño de la matriz.

Un código de ejemplo de declaración de esta matriz:

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

tengo una propuesta para utilizar la función mmap. Pero no sé cómo usarlo? ¿Alguien puede ayudarme a usarlo?

Estoy trabajando en Ubuntu 10.04 64-bit, gcc versión 4.4.3.

Gracias por sus respuestas.

Answer 1

Michael tiene razón, no puede caber tanto en la pila. Sin embargo, puede hacerlo global (o estático) si no desea malloc.

#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

Debe utilizar malloc para este tipo de asignación. Eso en la pila fallará casi todo el tiempo.

int *list; 

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

Esto coloca la asignación en el montón donde hay mucha más memoria disponible.

Answer 3

Probablemente no crees una matriz tan grande y si lo haces, ciertamente no la creas en la pila; la pila simplemente no es tan grande.

Si tiene un espacio de direcciones de 32 bits y un int de 4 bytes, entonces no puede crear una matriz con mil millones int s; simplemente no habrá suficiente espacio contiguo en la memoria para ese objeto grande (probablemente no habrá suficiente espacio contiguo para un objeto una fracción de ese tamaño). Si tiene un espacio de direcciones de 64 bits, puede salirse con la suya asignando ese espacio.

Si realmente quieres probar, deberás crearlo estáticamente (es decir, declarar la matriz en el alcance del archivo o con el calificador static en la función) o dinámicamente (usando malloc).

Answer 4

Otra opción es asignar dinámicamente una lista vinculada de matrices más pequeñas. Tendrás que envolverlos con funciones de acceso, pero es mucho más probable que puedas tomar 16 256 MB de memoria que un solo fragmento de 4 GB.

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

Answer 5

en sistemas Linux malloc de grandes trozos apenas hace un mmap bajo el capó, por lo que es tal vez demasiado tedioso para mirar en eso.

Tenga cuidado de no tener desbordamiento (enteros con signo) ni envolvente silenciosa (enteros sin signo) para sus límites e índices de matriz. Utilice size_t como un tipo para eso, ya que está en una máquina de 64 bits, esto debería funcionar.

Pero como hábito definitivamente debe verificar sus límites contra SIZE_MAX, algo así como assert(N*sizeof(data[0]) <= SIZE_MAX), para estar seguro.

Answer 6

Las asignaciones de pila lo hacen romperse. N = 1Gig ints => 4Gig de memoria (ambos con un compilador de 32 bits y uno de 64 bits).Pero si quiere medir el rendimiento del servicio rápido, o un algoritmo similar al suyo, esta no es la manera de hacerlo. Intente en su lugar usar múltiples quicksorts en secuencia en muestras preparadas con un tamaño 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 

Ahora tiene una respuesta muy precisa a la cantidad de tiempo que su algoritmo ha consumido. Ejecútelo varias veces para tener una idea de "qué tan preciso" (use una nueva semilla srand (semilla) cada vez). Y cambie la N para más inspección.