I am writing the game of life code. Now this is running for smaller size of matrices, but I need this to run for big matrices. So I need to deallocate the memory somehow. I tried it with the //deallocate part at the end of calculate(). But now its showing up an error.

Could you please deallocate the memory somehow so that it run for big matrices (like 10k * 10k with 10k iterations)?

#include<stdio.h>
#include<stdlib.h>
#include <malloc.h>
#include <math.h>
#include <sys/time.h>

#define ALIVE 1
#define DEAD 0

int **array = NULL;
int **history = NULL;
int HEIGHT;
int WIDTH;

double gettime(void) {
  struct timeval tval;

  gettimeofday(&tval, NULL);

  return( (double)tval.tv_sec + (double)tval.tv_usec/1000000.0 );
}


int **allocarray(int P, int Q) {
  int i;
  int *p, **a;
  p = (int *)malloc(P*Q*sizeof(int));
  a = (int **)malloc(P*sizeof(int*));
  if (p == NULL || a == NULL) 
    printf("Error allocating memory\n");
  /* for row major storage */
  for (i = 0; i < P; i++)
    a[i] = &p[i*Q];
  return a;
}
void initarray() {
  int i,j; 
  for (i=1; i<HEIGHT-1; i++){
    for (j=1; j<WIDTH-1; j++){
                if(drand48()>0.5){
                        array[i][j] = 1;
                }
                else{
                        array[i][j] = 0;
                }
        }
  }
} 
void printTable(int **table) {
        int height, width;

                for (height = 1; height < HEIGHT-1; height++) {
                for (width = 1; width < WIDTH-1; width++) {
                        if (table[height][width] == ALIVE) {
                                printf(" X ");
                        } else {
                                printf(" 0 ");
                        }
                }
                printf("\n");
        }
        printf("\n");
}

//to clear up everything

void clearTable() {
        int height, width;
        for (height = 0; height < HEIGHT; height++) {
                for (width = 0; width < WIDTH; width++) {
                        array[height][width] = DEAD;
                }
        }
}

int getNeighborValue(int **table, int row, int col) {
        if (table[row][col] == ALIVE) 
        { 
                return 1;
        } else {
                return 0;
        }
}


int getNeighborCount(int **table, int row, int col) {
        int neighbor = 0;

        neighbor += getNeighborValue(table, row - 1, col - 1);  //top left
        neighbor += getNeighborValue(table, row - 1, col);  //top
        neighbor += getNeighborValue(table, row - 1, col + 1);  //top right
        neighbor += getNeighborValue(table, row, col - 1);  //left
        neighbor += getNeighborValue(table, row, col + 1);  //right
        neighbor += getNeighborValue(table, row + 1, col - 1);  //below left
        neighbor += getNeighborValue(table, row + 1, col);   // below
        neighbor += getNeighborValue(table, row + 1, col + 1);  //below right
        
        return neighbor;
}

void calculate() {
        int **tableB = NULL;
        int neighbor, height, width;
                tableB = allocarray(HEIGHT, WIDTH);

        for (height = 1; height < (HEIGHT-1); height++) {
                for (width = 1; width < (WIDTH-1); width++) {
                        neighbor = getNeighborCount(array, height, width);
                        if (neighbor==3) {
                                tableB[height][width] = ALIVE;
                        } else if (neighbor == 2 && array[height][width] == ALIVE) {
                                tableB[height][width] = ALIVE;
                        } else {
                                tableB[height][width] = DEAD;
                        }
                }
        }

        for (height = 1; height < (HEIGHT-1); height++) {
                for (width = 1; width < (WIDTH-1); width++) {
                        array[height][width] = tableB[height][width];
                }
        }
for (height = 1; height < (HEIGHT-1); height++) {
        for (width = 1; width < (WIDTH-1); width++) {
                free(tableB [height][width]);
                free(tableB);
                }
        }
}
int matchArray(void){
        int count = 0;
        int height,width,flag=0;
        for(height = 0; height<HEIGHT; height++){
                for(width = 0; width<WIDTH; width++){
                        if(array[height][width] != history[height][width]){
                                count++;
                        }
                }
        }
        if(count>0){
                flag = 1;
        }
        return flag;
}


int main(int argc, char *argv[]) {
        int generation = 0;
        int i;
double starttime, endtime, time;
                int height,width;
                int flag = 0;
        if (argc!=3)
                printf("You need to enter the size of the matrix and the number of generations in the comment line arguement\n");
        else
        {
                printf("The matrix size given is:%s * %s\n",argv[1], argv[1]);
                HEIGHT = atoi(argv[1])+2;
                WIDTH = HEIGHT;
                array = allocarray(HEIGHT, WIDTH);
                history = allocarray(HEIGHT, WIDTH);
                clearTable();
                initarray();
                //printTable(array);
                //printf("Test data as Generation 0\n");
                //printf("-----------\n");
                starttime= gettime();
                //printf("Starttime= %f", starttime);
        for(i=0; i<(atoi(argv[2])); i++)
        {
                                for (height = 0; height < HEIGHT; height++) {
                                        for (width = 0; width < WIDTH; width++) {
                                                        history[height][width] = array[height][width];
                                        }
                                }
                calculate();
                                flag = matchArray();
                                //printf("The flag value is:%d\n",flag);
                                if(flag == 0){
                                        break;
                                }
                //printTable(array);
                                //printf("\n======================================\n");
                                //printTable(history);
                //printf("Generation %d\n", ++generation);
        }
        endtime= gettime();
        //printf("Endtime= %f", endtime);

        time= (endtime-starttime);
        printf("Time taken= %1f\n", time); 
        } 
        return 0;
}

In think this is what you want. Allocating pointer p is not necessary. To make a PXQ array you have to allocate Q integers for each row in P.

void destroyArray(int **a, int P)
{
   int i;
   for(i = 0; i < P; i++)
       free(a[i]);
   free(a);
}

int **allocarray(int P, int Q) {
  int i;
  int **a;
  a = calloc(P*sizeof(int*)); // typecast not necessary
  if (a == NULL) 
  {
    printf("Error allocating memory\n");
    return NULL; // no point continuing
  }
  /* for row major storage */
  for (i = 0; i < P; i++)
  {
    a[i] = malloc(Q*sizeof(int));
    if( a[i] == NULL)
    {
           destroyArray(a, P);
           return NULL;
    }
  return a;
}

Edited 6 Years Ago by Ancient Dragon: n/a

In think this is what you want. Allocating pointer p is not necessary. To make a PXQ array you have to allocate Q integers for each row in P.

void destroyArray(int **a, int P)
{
   int i;
   for(i = 0; i < P; i++)
       free(a[i]);
   free(a);
}

int **allocarray(int P, int Q) {
  int i;
  int **a;
  a = calloc(P*sizeof(int*)); // typecast not necessary
  if (a == NULL) 
  {
    printf("Error allocating memory\n");
    return NULL; // no point continuing
  }
  /* for row major storage */
  for (i = 0; i < P; i++)
  {
    a[i] = malloc(Q*sizeof(int));
    if( a[i] == NULL)
    {
           destroyArray(a, P);
           return NULL;
    }
  return a;
}

Thanks Ancient Dragon.. I tried with the code you provided. I dont know .. probably I messing up things and so its showing like a lot errors. Here must be some problem :-(

I rewrite the code:

#include<stdio.h>
#include<stdlib.h>
#include <malloc.h>
#include <math.h>
#include <sys/time.h>

#define ALIVE 1
#define DEAD 0

int **array = NULL;
int **history = NULL;
int HEIGHT;
int WIDTH;

double gettime(void) {
  struct timeval tval;

  gettimeofday(&tval, NULL);

  return( (double)tval.tv_sec + (double)tval.tv_usec/1000000.0 );
}

void destroyArray(int **a, int P) {
        int i;
        for (i=0; i<P; i++)
                free(a[i]);
        free(a);
}

int **allocarray(int P, int Q) {
  int i;
  int **a;
  //p = (int *)malloc(P*Q*sizeof(int));
  a = calloc(P*sizeof(int*));
  if (a == NULL) 
    {
    printf("Error allocating memory\n");
    return 0;
        }
  /* for row major storage */
  for (i = 0; i < P; i++) {
    a[i] = malloc(Q*sizeof(int));
    if (a[i] == NULL)
    {
       destroyArray(a, P);
        return 0;
        }
return a;
}

void initarray() {
  int i,j; 
  for (i=1; i<HEIGHT-1; i++){
    for (j=1; j<WIDTH-1; j++){
                if(drand48()>0.5){
                        array[i][j] = 1;
                }
                else{
                        array[i][j] = 0;
                }
        }
  }
}
 
void printTable(int **table) {
        int height, width;

                for (height = 1; height < HEIGHT-1; height++) {
                for (width = 1; width < WIDTH-1; width++) {
                        if (table[height][width] == ALIVE) {
                                printf(" X ");
                        } else {
                                printf(" 0 ");
                        }
                }
                printf("\n");
        }
        printf("\n");
}

//to clear up everything

void clearTable() {
        int height, width;
        for (height = 0; height < HEIGHT; height++) {
                for (width = 0; width < WIDTH; width++) {
                        array[height][width] = DEAD;
                }
        }
}

int getNeighborValue(int **table, int row, int col) {
        if (table[row][col] == ALIVE) 
        { 
                return 1;
        } else {
                return 0;
        }
}


int getNeighborCount(int **table, int row, int col) {
        int neighbor = 0;

        neighbor += getNeighborValue(table, row - 1, col - 1);  //top left
        neighbor += getNeighborValue(table, row - 1, col);  //top
        neighbor += getNeighborValue(table, row - 1, col + 1);  //top right
        neighbor += getNeighborValue(table, row, col - 1);  //left
        neighbor += getNeighborValue(table, row, col + 1);  //right
        neighbor += getNeighborValue(table, row + 1, col - 1);  //below left
        neighbor += getNeighborValue(table, row + 1, col);   // below
        neighbor += getNeighborValue(table, row + 1, col + 1);  //below right
        
        return neighbor;
}

void calculate() {
        int **tableB = NULL;
        int neighbor, height, width;
                tableB = allocarray(HEIGHT, WIDTH);

        for (height = 1; height < (HEIGHT-1); height++) {
                for (width = 1; width < (WIDTH-1); width++) {
                        neighbor = getNeighborCount(array, height, width);
                        if (neighbor==3) {
                                tableB[height][width] = ALIVE;
                        } else if (neighbor == 2 && array[height][width] == ALIVE) {
                                tableB[height][width] = ALIVE;
                        } else {
                                tableB[height][width] = DEAD;
                        }
                }
        }

        for (height = 1; height < (HEIGHT-1); height++) {
                for (width = 1; width < (WIDTH-1); width++) {
                        array[height][width] = tableB[height][width];
                }
        }
/* for (height = 1; height < (HEIGHT-1); height++) {
        for (width = 1; width < (WIDTH-1); width++) {
                free(tableB [height][width]);
                free(tableB);
                }
        }*/
}

int matchArray(void){
        int count = 0;
        int height,width,flag=0;
        for(height = 0; height<HEIGHT; height++){
                for(width = 0; width<WIDTH; width++){
                        if(array[height][width] != history[height][width]){
                                count++;
                        }
                }
        }
        if(count>0){
                flag = 1;
        }
        return flag;
}


int main(int argc, char *argv[]) {
        int generation = 0;
        int i;
double starttime, endtime, time;
                int height,width;
                int flag = 0;
        if (argc!=3)
                printf("You need to enter the size of the matrix and the number of generations in the comment line arguement\n");
        else
        {
                printf("The matrix size given is:%s * %s\n",argv[1], argv[1]);
                HEIGHT = atoi(argv[1])+2;
                WIDTH = HEIGHT;
                array = allocarray(HEIGHT, WIDTH);
                history = allocarray(HEIGHT, WIDTH);
                clearTable();
                initarray();
                //printTable(array);
                //printf("Test data as Generation 0\n");
                //printf("-----------\n");
                starttime= gettime();
                //printf("Starttime= %f", starttime);
        for(i=0; i<(atoi(argv[2])); i++)
        {
                                for (height = 0; height < HEIGHT; height++) {
                                        for (width = 0; width < WIDTH; width++) {
                                                        history[height][width] = array[height][width];
                                        }
                                }
                calculate();
                                flag = matchArray();
                                //printf("The flag value is:%d\n",flag);
                                if(flag == 0){
                                        break;
                                }
                //printTable(array);
                                //printf("\n======================================\n");
                                //printTable(history);
                //printf("Generation %d\n", ++generation);
        }
        endtime= gettime();
        //printf("Endtime= %f", endtime);

        time= (endtime-starttime);
        printf("Time taken= %1f\n", time); 
        } 
        return 0;
}

Corrected function

int **allocarray(int P, int Q) {
  int i;
  int **a;
  //p = (int *)malloc(P*Q*sizeof(int));
  a = calloc(P,sizeof(int*));
  if (a == NULL) 
    {
    printf("Error allocating memory\n");
    return 0;
        }
  /* for row major storage */
  for (i = 0; i < P; i++) {
    a[i] = malloc(Q*sizeof(int));
    if (a[i] == NULL)
    {
       destroyArray(a, P);
        return 0;
    }
  }
return a;
}

This one is not working too.

Corrected function

int **allocarray(int P, int Q) {
  int i;
  int **a;
  //p = (int *)malloc(P*Q*sizeof(int));
  a = calloc(P,sizeof(int*));
  if (a == NULL) 
    {
    printf("Error allocating memory\n");
    return 0;
        }
  /* for row major storage */
  for (i = 0; i < P; i++) {
    a[i] = malloc(Q*sizeof(int));
    if (a[i] == NULL)
    {
       destroyArray(a, P);
        return 0;
    }
  }
return a;
}

>>This one is not working too.

What exactly does that mean? I can not compile your program because my compiler does not support <sys/time.h>, gettimeofday(), or drand48().

Edited 6 Years Ago by Ancient Dragon: n/a

Its showing that old "error allocating memory" :-(

Please help!

>>This one is not working too.

What exactly does that mean? I can not compile your program because my compiler does not support <sys/time.h>, gettimeofday(), or drand48().

You are attempting to allocate 15000x15000x2 integers, or 1.800.000.000 bytes of memory, which is nearly 2 Gig. The limit of any 32-bit program is 2 Gig. You will either have to use a 64-bit compiler (and operating system) or settle for considerably smaller size of the arrays.

You are attempting to allocate 15000x15000x2 integers, or 1.800.000.000 bytes of memory, which is nearly 2 Gig. The limit of any 32-bit program is 2 Gig. You will either have to use a 64-bit compiler (and operating system) or settle for considerably smaller size of the arrays.

Hey I need to run 10k*10k matrix with 10k iterations on 32bit. In order to do that, can anything be done to the program so that it could use lesser amt of memory?

This article has been dead for over six months. Start a new discussion instead.