Thread: Dynamically allocate Large 4-D arrays

  1. #1
    Registered User
    Join Date
    Aug 2009
    Posts
    1

    Dynamically allocate Large 4-D arrays

    Hello,

    For a project I am working on, I need to be able to dynamically allocate large 4-dimensional arrays. The code I am using to do this is:

    Code:
    void allocate_data_mem(size_t count0, size_t count1, size_t count2, size_t count3, double *****data)
    {
        int i, j, k, l;
        
        *data = (double ****)malloc(count2*sizeof((*data)));
    	if ((*data) != NULL) {
            for(i = 0; i < count2; i++) {
         		(*data)[i] = (double ***)malloc(count3*sizeof((*data)));
         		if ((*data)[i] != NULL) {
               		for(j = 0; j < count3; j++) {
                 		(*data)[i][j] = (double **)malloc(count1*sizeof((*data)));
                 		if ((*data)[i][j] != NULL) {
                            for (k = 0; k < count1; k++) {
                                (*data)[i][j][k] = (double *)malloc(count0*sizeof((*data)));
                                if ((*data)[i][j][k] == NULL) {
                                   printf("Mem allocation failed\n");
                                   exit(1);
                                }
                            }
                        }              
                        else {
                             printf("Mem allocation failed\n");
                             exit(1);
                             }
                    }
                }
                else {
                     printf("Mem allocation failed\n");
                     exit(1);
                     }
            }
        }
        else {
              printf("Mem allocation failed\n");
              exit(1);
        }
    
    }
    It works fine, but the problem is it is slow. For a 300x400x30x10 array, this code will use 3.6 million malloc calls and takes about 0.5 seconds to complete. The program as a whole will do this many times, so the time adds up.

    Is there another way to accomplish this using fewer mallocs?

    Thanks.

  2. #2
    Registered User
    Join Date
    Sep 2001
    Posts
    4,912
    Is there another way to accomplish this using fewer mallocs?
    Yes - multiply all of your dimensions together, and allocate the space in one large chunk. But remember that just getting that much memory might cause delays also - but at least all your allocation would be done in one large chunk.

    Remember that when you're working with arrays, you really just have a pointer to the beginning and an offset. Let's say I have a an array of chars:
    Code:
    char string[80];
    If I refer to "string" it's just a pointer to the beginning of the array, and is equal to &string[0]. But when I try to access string[10] or string[20], it's the same as dereferencing the pointers "string+10" or "string+20". So you could allocate a huge chunk of memory with one pointer, and then work with various arrays by using the offsets. So given your example dimensions, you could access every element by adding 1 to the offset every time. You could access each 1-d array by adding 10 every time, each 2-d array by adding 30 every time, etc... Just be very careful with your bounds.

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    You can malloc each dimension separately as a single contiguous block (so a 4D array would be just 4 mallocs).

    Example for 2D
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    int **allocate2Darray ( int rows, int cols ) {
      int **result;
      int r, *rp;  // initialise each row pointer
      
      result = malloc( rows * sizeof *result );
      result[0] = malloc( rows * cols * sizeof *result[0] );
      for ( r = 0, rp = result[0] ; r < rows ; r++, rp += cols ) {
        result[r] = rp;
      }
      return result;
    }
    
    void free2Darray ( int **array ) {
      free( array[0] );
      free( array );
    }
    
    #define MAX_R 5
    #define MAX_C 16
    int main(int argc, char **argv) {
      int **a = allocate2Darray( MAX_R, MAX_C );
      int r, c;
      for ( r = 0 ; r < MAX_R ; r++ ) {
        for ( c = 0 ; c < MAX_C ; c++ ) {
          a[r][c] = 0;
        }
      }
      printf( "The pitch between rows is %x bytes\n", MAX_C * sizeof(int) );
      for ( r = 0 ; r < MAX_R ; r++ ) {
        printf( "Row %d begins at %p\n", r, (void*)a[r] );
      }
      free2Darray( a );
      return 0;
    }
    3D would have a malloc for result[0][0] and so on.

    It's quite nice in that it doesn't involve any pointer casting and do-it-yourself pointer arithmetic to make it work
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #4
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    A brief skimming reminded me of this:
    4-dimensional array contiguous allocation
    Last edited by Dave_Sinkula; 08-24-2009 at 11:08 AM. Reason: D'oh! Left the tab open a little too long methinks.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Dagnabbit, how come you could find it and I couldn't
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  6. #6
    Registered User
    Join Date
    Oct 2001
    Posts
    2,129
    here's another way if you know the dimensions at compile time (doesn't look like you do, but I'm putting it out there just in case)
    Code:
    double (*array)[300][400][30][10] = malloc(sizeof *array);
    double (*array2)[400][30][10] = malloc (sizeof(*array2) * 300);
    (*array)[200][350][25][5] = 2.0;
    array2[200][350][25][5] = 1.0;
    free(array);
    free(array2);

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Have you thought about putting the data into a struct, and then just using a 1D array of those structs?

    instead of:

    array[1d][2d][3d][4d], to access some data (each Nd being an index), it would be:

    array[1d].struct member4

    Seems to simplify the whole thing.

  8. #8
    Registered User
    Join Date
    Sep 2001
    Posts
    4,912
    Then it just becomes a 2d array - 1 dimension of structs, and 1 dimension of members in the struct. Each dimension was a different length.

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Whoa! Will you really have all 300x400x30x10 slots in the array filled at once?! That's 36 Million items!
    Or perhaps what you really need is some kind of sparse array... That's something that acts like an array but places that aren't occupied by items mostly don't count towards the space used. I made a multiway-trie class that handles such functionality.

    If it's not sparse that you need, then at the very least combine some of the dimensions together into bitmap style array indexing. Maybe combine the last 3 dimensions together. That's 300 mallocs to 120000 items each - much more manageable. Of course it depends on your access patterns, e.g. which way round your loops are nested.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Dynamically allocate an array of two bytes?
    By dre in forum C Programming
    Replies: 9
    Last Post: 08-13-2009, 09:27 AM
  2. Problem declaring large arrays
    By mattAU in forum C Programming
    Replies: 5
    Last Post: 09-28-2006, 05:47 AM
  3. Building B-Tree from Arrays
    By 0rion in forum C Programming
    Replies: 1
    Last Post: 04-09-2005, 02:34 AM
  4. dynamically allocating 2D arrays
    By Neo in forum C++ Programming
    Replies: 4
    Last Post: 03-29-2004, 09:51 PM
  5. Destructors in dynamically allocated arrays
    By frenchfry164 in forum C++ Programming
    Replies: 1
    Last Post: 11-28-2003, 11:26 PM