[C] memoria dello stack finita : si può aumentare??

[thesalien]

Salve a tutti, ho un grossissimissimo problema:
Se creo due array di tipo intero del tipo: array[4][7][5000] il programma si blocca. Ho sentito che esiste un modo per far si che il compilatore allochi memoria per lo stack in più.
Io uso borland c++. Ho provato ad andare in OPTION->linker->32-bitimage->reserved stack size e ho modificato il valore a 300000 ma non cambia lo stesso
sapete dirmi il motivo???????
Avete idea del perchè un pentium 4 come il mio non riesca a allocare un tanto di memoria pari a 2 * [4][7][5000] ??

[anx721]

Col compilatore MinGW riesco a dichiarare un array di interi che è mille volte piu grande di quello che dichiari te:

int array1[4][7][5000][1000];


col borland regge fino a int array1[4][7][5000][100] mentre se dichiaro int array1[4][7][5000][1000] il compilatore stesso ha un errore fatale di out of memory durante la compilazione...

senza che il programma si blocchi...

[thesalien]

Ciao Anx, ti invito a eseguire questo sorgente, da me non eseguisce neanche il main. Se tolgo int testa_heap[4][7][DIMENSIONE_MAX_LISTA]; invece il programma gira perfettamente.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#ifdef _WIN32
#include <windows.h>
#define MAX_CIFRE 4 // numeri compresi tra 0 e 999
#define RADICE_SIZE 10
#define IS_FULL(ptr) (!ptr)
#define IS_EMPY(ptr) (!ptr)
#define MAX 5000
#define MAX_CIFRE 4 // numeri compresi tra 0 e 999
#define RADICE_SIZE 10
#define IS_FULL(ptr) (!ptr)
#define IS_EMPY(ptr) (!ptr)
#define ITERAZIONI 7
#define DIMENSIONE_MAX_LISTA 5000


static LARGE_INTEGER _tstart, _tend;
static LARGE_INTEGER freq; 

void tstart(void)
{
static int first = 1;
if(first){
         QueryPerformanceFrequency(&freq);
         first = 0;
         }
QueryPerformanceCounter(&_tstart);
} 

void tend(void)
{
QueryPerformanceCounter(&_tend);
} 

double tval()
{
return ((double)_tend.QuadPart - (double)_tstart.QuadPart)/((double)freq.QuadPart);
} 
#else 
#include <sys/time.h> 

static struct timeval _tstart, _tend; 
static struct timezone tz;

void tstart(void)
{
gettimeofday(&_tstart, &tz);
} 

void tend(void)
{
gettimeofday(&_tend,&tz);
} 

double tval()
{
typedef signed long s;
s t1, t2;
t1 = (s)_tstart.tv_sec + (s)_tstart.tv_usec/(1000*1000);
t2 = (s)_tend.tv_sec + (s)_tend.tv_usec/(1000*1000);
return t2-t1; 
}
#endif


typedef struct list_node *list_pointer;
typedef struct list_node {
int chiave[MAX_CIFRE];
list_pointer link;
}lista;

int dimensioni[]= {50,100,200,500,1000,2000,5000};

void creazione_dati (int testa[][ITERAZIONI][DIMENSIONE_MAX_LISTA]);

void scambia(int *x,int *y);

void sort_inserzione(int lista[][ITERAZIONI][DIMENSIONE_MAX_LISTA],int m,int n);

void sort_selezione (int lista[][ITERAZIONI][DIMENSIONE_MAX_LISTA],int m,int n);

void quicksort(int A[ ][ITERAZIONI][DIMENSIONE_MAX_LISTA], int u, int v,int z,int r);
int perno(int A[ ][ITERAZIONI][DIMENSIONE_MAX_LISTA], int primo, int ultimo, int z, int r);

void mergesort(int lista[ ][ITERAZIONI][DIMENSIONE_MAX_LISTA], int n, int z, int r);
void passo_merge(int lista[ ][ITERAZIONI][DIMENSIONE_MAX_LISTA], int ordinata[][ITERAZIONI][DIMENSIONE_MAX_LISTA], int n, int lungh,int z, int r);
void merge(int lista[ ][ITERAZIONI][DIMENSIONE_MAX_LISTA], int ordinata[ ][ITERAZIONI][DIMENSIONE_MAX_LISTA], int i, int m, int n, int z, int r);

void heapsort(int lista[ ][ITERAZIONI][DIMENSIONE_MAX_LISTA], int n, int z, int r);
void adatta(int lista[ ][ITERAZIONI][DIMENSIONE_MAX_LISTA], int radice, int n, int z, int r);

list_pointer radice_sort(list_pointer ptr);

void creazione_dati_heap (int testa_heap[][ITERAZIONI][DIMENSIONE_MAX_LISTA]);

void visualizza(list_pointer ptr);

main(){
randomize();
printf("\nEsercitazione numero 23\n");
int i,j,k,h;

int testa[4][7][DIMENSIONE_MAX_LISTA];
int testa_heap[4][7][DIMENSIONE_MAX_LISTA];
int tempo[4][7][6];
int confronti[4][7][6];
int scambi[4][7][6];

for(i=0;i<4;i++)
for(j=0;j<7;j++)
for(k=0;k<6;k++)
confronti[i][j][k] = 0;

for(i=0;i<4;i++)
for(j=0;j<7;j++)
for(k=0;k<6;k++)
scambi[i][j][k] = 0;



//****************************************************************************
//****************************************************************************
//*************************ORDINAMENTO PER SELEZIONE**************************
//****************************************************************************
//****************************************************************************

//creazione dei dati di input
creazione_dati (testa);

for(i=0;i<4;i++)
for(j=0;j<7;j++)
{
tstart();
sort_selezione(testa,i,j);
tend();
tempo[i][j][0]=tval();
}



//****************************************************************************
//****************************************************************************
//*************************ORDINAMENTO PER INSERZIONE*************************
//****************************************************************************
//****************************************************************************

//creazione dei dati di input
creazione_dati (testa);


for(i=0;i<4;i++)
for(j=0;j<7;j++)
{
tstart();
sort_inserzione(testa,i,j);
tend();
tempo[i][j][1]=tval();
}


//****************************************************************************
//****************************************************************************
//***********************ORDINAMENTO VELOCE (QuickSort)***********************
//****************************************************************************
//****************************************************************************

//creazione dei dati di input
creazione_dati (testa);

for(i=0;i<4;i++)
for(j=0;j<7;j++)
{
h = dimensioni[j] - 1;
tstart();
quicksort(testa,0,h,i,j);
tend();
tempo[i][j][2]=tval();
}
printf("\n");
for(i=0;i<50;i++)printf(" %d ",testa[3][0][i]);


//****************************************************************************
//****************************************************************************
//*********************ORDINAMENTO PER FUSIONE (MergeSort)********************
//****************************************************************************
//****************************************************************************

//creazione dei dati di input
creazione_dati (testa);

for(i=0;i<4;i++)
for(j=0;j<7;j++)
{
h = dimensioni[j];
tstart();
//mergesort(testa,h,i,j);
tend();
tempo[i][j][3]=tval();
}
printf("\n");
//for(i=0;i<50;i++)printf(" %d ",testa[3][0][i]);

//****************************************************************************
//****************************************************************************
//***************************ORDINAMENTO CON HEAP*****************************
//****************************************************************************
//****************************************************************************
//creazione dei dati di input
creazione_dati_heap (testa_heap);

for(i=0;i<50;i++)printf(" %d ",testa_heap[3][0][i]);

for(i=0;i<4;i++)
for(j=0;j<7;j++)
{
h = dimensioni[j];
tstart();
heapsort(testa_heap,h,i,j);
tend();
tempo[i][j][4]=tval();
}
printf("\n\n\n\n\n\n\n");
for(i=0;i<50;i++)printf(" %d ",testa_heap[3][0][i]);


getchar();
fflush(stdin);
}

void sort_inserzione(int lista[][ITERAZIONI][DIMENSIONE_MAX_LISTA],int m,int n)
{
int i,j,h;
int prossimo;
h = dimensioni[n];
for(i=1;i<h;i++)
{
prossimo=lista[m][n][i];
for(j=i-1;j>=0 && prossimo<lista[m][n][j];j--)
lista[m][n][j+1] = lista[m][n][j];

lista[m][n][j+1] = prossimo;
}

}


void sort_selezione (int lista[][ITERAZIONI][DIMENSIONE_MAX_LISTA],int m,int n)
{
int i,j,h,min;
h = dimensioni[n];
for(i=0;i<h-1;i++)
{
min =i;
for(j=i+1;j<h;j++)
   if(lista[m][n][j]<lista[m][n][min])min=j;
   scambia(&lista[m][n][i],&lista[m][n][min]);
}
}



void quicksort(int A[ ][ITERAZIONI][DIMENSIONE_MAX_LISTA], int u, int v,int z,int r)
{
int q;
if(u == v) return;
q = perno(A, u, v, z, r);
if( u < q ) quicksort(A, u, q-1, z, r);
if( q < v ) quicksort(A, q+1, v, z, r);
}

int perno(int A[ ][ITERAZIONI][DIMENSIONE_MAX_LISTA], int primo, int ultimo, int z, int r)
{
int i = primo;
int j =ultimo+1;
int pivot=A[z][r][primo];

do{
do i++; while(A[z][r][i]<pivot && i<j);
do j--; while(A[z][r][j]>pivot && j>primo);
if(i<j) scambia(&A[z][r][i],&A[z][r][j]);
}while(i<j);

scambia(&A[z][r][primo], &A[z][r][j]) ;

return j;

}

void merge(int lista[ ][ITERAZIONI][DIMENSIONE_MAX_LISTA], int ordinata[ ][ITERAZIONI][DIMENSIONE_MAX_LISTA], int i, int m, int n, int z, int r)
{
/* fonde due file ordinati: lista[i],...,lista[m]
e lista[m+1],...,lista[n], per ottenere una sola lista ordinata
ordinata[i],...,ordinata[n]
*/
int j, k, t;
j = m+1;
// indice per la seconda lista
k = i;
// indice per la lista ordinata
while(i<=m && j<=n)
{
if(lista[z][r][i]<=lista[z][r][j]) ordinata[z][r][k++] = lista[z][r][i++];
else
ordinata[z][r][k++] = lista[z][r][j++];
}
if(i>m) for(t=j; t<=n; t++) ordinata[z][r][k+t-j] = lista[z][r][t];
// ordinata[k],...,ordinata[n] = lista[j],...,lista[n]
else for(t=i; t<=m; t++) ordinata[z][r][k+t-i] = lista[z][r][t];
// ordinata[k],...,ordinata[n] = lista[i],...,lista[m]
}

void passo_merge(int lista[ ][ITERAZIONI][DIMENSIONE_MAX_LISTA], int ordinata[][ITERAZIONI][DIMENSIONE_MAX_LISTA], int n, int lungh,int z, int r)
{
/*
Svolge un passo dell'ordinamento per fusione.
Fonde una coppia di sottofile adiacenti da lista a ordinata;
n è il numero di elementi nella lista;
lungh è la lunghezza del sottofile */
int i, j;
for(i = 0; i <= n-2*lungh; i += 2*lungh)
merge(lista, ordinata, i, i+lungh-1, i+2*lungh-1, z, r);
if(i+lungh < n)
merge(lista, ordinata, i, i+lungh-1, n-1, z, r);
else for(j = i; j < n; j++)
ordinata[z][r][j] = lista[z][r][j];
}

void mergesort(int lista[ ][ITERAZIONI][DIMENSIONE_MAX_LISTA], int n, int z, int r)
{
/* ordina la lista lista[0],...,lista[n-1] per fusione */
int lungh = 1;
// lunghezza corrente delle liste da fondere
int extra[MAX][ITERAZIONI][DIMENSIONE_MAX_LISTA];
while(lungh < n)
{
passo_merge(lista, extra, n, lungh, z, r);
lungh *= 2;
passo_merge(extra, lista, n, lungh, z, r);
lungh *= 2;
}
}

void heapsort(int lista_heap[ ][ITERAZIONI][DIMENSIONE_MAX_LISTA], int n, int z, int r)
{

int i;
for(i = n/2; i > 0; i--)
adatta(lista_heap, i, n, z, r);
for(i = n-1; i > 0; i--) {
scambia(&lista_heap[z][r][1], &lista_heap[z][r][i+1]); //Scambia lista[1] con lista[i]
adatta(lista_heap, 1, i, z, r);
}
}


void adatta(int lista_heap[ ][ITERAZIONI][DIMENSIONE_MAX_LISTA], int radice, int n, int z, int r)
// adatta l'albero binario per ottenere l'heap
{
int figlio, chiaveradice;
int temp;
temp = lista_heap[z][r][radice];
chiaveradice = lista_heap[z][r][radice];
figlio = 2*radice;
// figlio a sinistra
while(figlio <= n) {
if((figlio < n) && (lista_heap[z][r][figlio]<lista_heap[z][r][figlio+1]))
figlio ++;
if(chiaveradice > lista_heap[z][r][figlio])
// confronta la radice e figlio max
break;
else {
lista_heap[z][r][figlio/2] = lista_heap[z][r][figlio];
// si sposta verso il padre
figlio *= 2;
}
}
lista_heap[z][r][figlio/2] = temp;
}

list_pointer radice_sort(list_pointer ptr)
{
list_pointer davanti[RADICE_SIZE], dietro[RADICE_SIZE];
int i, j, cifra;
for(i = MAX_CIFRE-1; i >=0; i--) {
for(j = 0; j < RADICE_SIZE; j++)
davanti[j] = dietro[j] = NULL;
while(ptr) {
cifra = ptr->chiave[i];
if (!davanti[cifra])
davanti[cifra] = ptr;
else
dietro[cifra]->link = ptr;
dietro[cifra] = ptr;
ptr = ptr->link;
}
// ristabilisce la lista concatenata per il passo succ
ptr = NULL;
for (j = RADICE_SIZE-1; j>=0; j--)
if(davanti[j]) {
dietro[j]->link = ptr;
ptr = davanti[j];
}
}
return ptr;
}

void scambia(int *x,int *y)
{
int temp= *x;
*x = *y;
*y = temp;
}

void visualizza (list_pointer ptr)
{
int x;
if(IS_EMPY(ptr)){printf("\nla lista e' vuota"); return;}
printf("\nI record presenti nella lista sono:");
for(;ptr;ptr=ptr->link) {
                        for(x=0;x<MAX_CIFRE;x++)
                        printf("%d",ptr->chiave[x]);
                        printf(" ");
                        }
}


void creazione_dati (int testa[][ITERAZIONI][DIMENSIONE_MAX_LISTA])
{
int i,j;

//liste ordinate
for(i=0;i<ITERAZIONI;i++)
for(j=0;j<dimensioni[i];j++) testa[0][i][j]=j;

//liste inversamente ordinate
for(i=0;i<ITERAZIONI;i++)
for(j=dimensioni[i];j>0;j--) testa[1][i][dimensioni[i]-j]=j;

//liste con numeri casuali
for(i=0;i<ITERAZIONI;i++)
for(j=0;j<dimensioni[i];j++) testa[3][i][j]=rand();

//liste quasi ordinate  (il 10% non e ordinato)
for(i=0;i<ITERAZIONI;i++)
for(j=0;j<(dimensioni[i]/10);j++) testa[2][i][j]=j + dimensioni[ITERAZIONI - 1] ;

for(i=0;i<ITERAZIONI;i++)
for(j=(dimensioni[i]/10);j<dimensioni[i];j++) testa[2][i][j]=j;

}

void creazione_dati_heap (int testa[][ITERAZIONI][DIMENSIONE_MAX_LISTA])
{
int i,j;

//liste ordinate
for(i=0;i<ITERAZIONI;i++)
for(j=1;j< (dimensioni[i]+1);j++) testa[0][i][j]=j;

//liste inversamente ordinate
for(i=0;i<ITERAZIONI;i++)
for(j=dimensioni[i]+1;j>1;j--) testa[1][i][(dimensioni[i]+1)-j]=j;

//liste con numeri casuali
for(i=0;i<ITERAZIONI;i++)
for(j=1;j< (dimensioni[i]+1);j++) testa[3][i][j]=rand();

//liste quasi ordinate  (il 10% non e ordinato)
for(i=0;i<ITERAZIONI;i++)
for(j=1;j<( (dimensioni[i]+1)/10);j++) testa[2][i][j]=j + dimensioni[ITERAZIONI - 1] ;

for(i=0;i<ITERAZIONI;i++)
for(j=( (dimensioni[i]+1) /10);j< (dimensioni[i]+1);j++) testa[2][i][j]=j;

}

[anx721]

Si, sembra un problema di memoria, se compilo col borland, quando vado ad eseguire il programma termina immediatamente; se riduco la dimensione di testa_heap invece funziona. Se uso il compilatore MinGW (che ti consiglio di provare, puoi scaricarlo con un ide come MinGWDeveloperStudio o devc++), il programma funziona anche con la dimensione originale di testa_heap. Puoi eventualmente risolvere il problema alllocando dinamicamente quegli array.

[thesalien]

Ciao Anx,
Sai se col borland si possa aumentare la dimensione dello stack? (almeno temporaneamente per l'esecuzione di quest'algoritmo e poi lo ripristino)? un mio amico, via linea di comando usando /stack ci è riuscito ma non riesco a farlo col borland.
Ho provato ad aumentare reserved stack size da 100000 a 300000 (in option->project->linker->32 bit image) ma senza risultati
MinGWDeveloperStudio e devc++ magari li provo ma purtroppo devo eseguire per forza questo programma in un borland perchè dove lo eseguo non è possibile usare altro