Dynamically creating a contiguous 5D array?

Question

I am working with a very large 5D array that I need to read into contiguous memory (another 5D array). I cannot place the array on the stack because it is too large and creates seg faults. What I've done is to create a 5D array dynamically with malloc however I've found that it is not contiguous memory. Is there an elegant solution to this or is it going to be messy no matter what?

Answer 1

From Jens Gustedt: Don't use fake matrices.

Allocate a 5-dimensional matrix with dimensions A x B x C x D x E (dimensions aren't required to be known at compile time) like so:

float (*matrix5d)[B][C][D][E] = malloc(sizeof(float[A][B][C][D][E]));

Release the memory with a single call to free.

free(matrix5d);

Note that the above requires C99 or higher for variable-length arrays.

Answer 2

Being represented via a contiguous chunk of memory is one of the distinguishing properties of a C array. Multidimensional arrays are arrays of arrays, and therefore contiguous the same as any other array, so if you want a genuine 5D array then you certainly do need contiguous memory for it. As some of the other answers have observed, to ensure that you get a contiguous block of memory, you must allocate the whole thing at once.

Although you can form data structures consisting of arrays of pointers to [[arrays of pointers to [arrays of pointers to ...]] arrays, these are not the same thing at all, just as pointers are not arrays. You can use the indexing operator, [], with such data structures in the same way that you can do with multi-dimensional arrays, but that doesn't make them the same thing.

@EvelynParenteau suggested simulating your 5D array with a 1D array, and indeed that's one way to satisfy your contiguity requirement. You could even write macros to make indexing into such an array easier.

But as long as you are using at least C99, you can dynamically allocate a genuine 5D array. The general form might look something like this:

void allocate_5d(unsigned dim1, unsigned dim2, unsigned dim3, unsigned dim4,
        unsigned dim5, double (**aptr)[dim2][dim3][dim4][dim5]) {
    *aptr = malloc(dim1 * sizeof(**aptr));
}

It would be used like this:

void do_something(unsigned dim1, unsigned dim2, unsigned dim3, unsigned dim4,
        unsigned dim5) {
    double (*array)[dim2][dim3][dim4][dim5];

    allocate_5d(dim1, dim2, dim4, dim4, dim5, &array);

    if (!array) {
        // Handle allocation failure ...
    }

    array[0][0][0][0][0] = 42;
    // ...

    free(array);
}

If dimensions 2 - 5 are compile-time constants, then you can even do a this (slightly differently) in C90, but the variation presented above depends on variable-length arrays, which were new in C99.

Answer 3

One way of thinking about it is to use malloc to allocate a 1d array of 4d arrays, because fundamentally malloc can only allocate 1d arrays, and an N-d array is just 1d array of (N-1)-d arrays.

However, just like any array allocated by malloc, the "array object" is actually a pointer, so you shouldn't use sizeof() to get the size of the array.

#include <stdio.h>
#include <stdlib.h>
typedef int Array_4D_Type[4][3][2][1];
int main(void) {
    Array_4D_Type *arr = malloc(5 * sizeof(Array_4D_Type));
   // ^^^^^^^^^^^^^^^^ here, allocate a length-5 vector of 4d array type
    int *p = &arr[0][0][0][0][0];
    for (int i = 0 ; i < 120 ; i++){
        p[i] = i;
    }
    printf("arr_start = %d, end = %d\n", arr[0][0][0][0][0], arr[4][3][2][1][0]);

    return 0;
}

You can test the code here.

Update:

As is mentioned in the comments, using typedef here forces the array to be static sized except the top dimension.

The use of typedef here is only to make the pointer-to-array syntax a little cleaner.

However, with VLA enabled, int (*arr)[n][o][p][q] = malloc(m*sizeof(*arr)); should still work and allow you to specify dynamic size on each dimension.

Answer 4

There is a way to make the memory contiguous, but whether its elegant or messy I'll leave up to you ;)

First, let's consider the case of a 1 dimensional array. In this case, it's trivial to get contiguous memory; the memory you get from malloc will be contiguous. It seems simple enough, but we're going to later use this fact to get a 5 dimensional contiguous array.

Now, let's consider a 2 dimensional array that is M by N in size. Here's one way of creating one (assuming we're using floats).

float** array2d = malloc(M * sizeof(float*));
for (int i = 0; i < M; i++) {
  array2d[i] = malloc(N * sizeof(float));
}

Strictly speaking, this is not a two dimensional array, it's an array of arrays. Now, we can access elements of array2d like array2d[0][0], array2d[0][1] etc. Conceptually this is very nice, but as you've noted, we don't necessarily have contiguous memory since we did multiple calls to malloc. What we need is a way to allocate all of the memory necessary to store M*N floats in one call to malloc.

float* array2d = malloc(M * N * sizeof(float));

Note that in this form, array2d is float* instead of float**, i.e. it's an array of floats, not an array of arrays of floats. So, we can't do array2d[0][0] any more. How do we now index this array?

It's entirely up to us to decide how this 2 dimensional array is laid out in memory. Let's say that M is the "width" of the array (meaning the number of elements in a row) and that N is the "height" of the array (meaning the number of rows in the array). Also, let's just say that the first M entries in the array are the first row, the next M entries are the second row, etc. So to read the entry at row y, column x, we would do this:

float data = array2d[y * M + x];

Say we want element (0, 0). Then y * M + x simply becomes 0, so we're good. Now say we want element (1, 0) (i.e. the first element in the second row). Then, y * M + x becomes M, which as we've decided above is where the second row starts.

We can generalize this approach to higher dimensions. Let's say we have a three dimensional array of size L by M by N. You can think of this as L two dimensional arrays laid out sequentially in memory, all of size M by N. Then, to access element (x, y, z) we would do:

float data = array3d[z * (M * N) + y * (M) + x];

Conceptually you can think of this as skipping the first z two dimensional arrays, then skipping the first y rows of that array, and then going to the xth element of that row. For more dimensions, there are more multiplicative terms when indexing, but the approach is fundamentally the same.

Answer 5

With dynamic allocation, using malloc:

int** x;

x = malloc(dimension1_max * sizeof(int*));
for (int i = 0; i < dimension1_max; i++) {
  x[i] = malloc(dimension2_max * sizeof(int));
}

[...]

for (int i = 0; i < dimension1_max; i++) {
  free(x[i]);
}
free(x);

This allocates an 2D array of size dimension1_max * dimension2_max. So, for example, if you want a 640*480 array (f.e. pixels of an image), use dimension1_max = 640, dimension2_max = 480. You can then access the array using x[d1][d2] where d1 = 0..639, d2 = 0..479.

But a search on SO or Google also reveals other possibilities, for example in this SO question

Note that your array won't allocate a contiguous region of memory (640*480 bytes) in that case which could give problems with functions that assume this. So to get the array satisfy the condition, replace the malloc block above with this:

int** x;
int* temp;

x = malloc(dimension1_max * sizeof(int*));
temp = malloc(dimension1_max * dimension2_max * sizeof(int));
for (int i = 0; i < dimension1_max; i++) {
  x[i] = temp + (i * dimension2_max);
}

[...]

free(temp);
free(x);

on similar way you can build dynamically 5d array

Answer 6

If I understand your question, that you have a current 5D array, and you need to allocate storage for, and make a copy of that array, and then you wish to access the values in a sequential manner. As others have noted, the approach is to use a pointer to a 4D array to allocate a block of memory dim1 * sizeof 4D to hold your existing array. (you can think about is as allocating for dim1 rows of what makes up your 5D array). You can then simply copy the existing array, (using memcpy or the like) then and assign a pointer to the first element for sequential access.

The benefit is you allocate a single block to hold a copy of your existing array. This will require only a single free when you are done making use of the copy.

This does not work with fake (pointer to pointer to pointer... collections of memory)

Below is a short example of creating a dim1 pointers to what makes up the remaining 4d of your existing array (in a single block allocation) where all but your dim1 dimensions are known at compile time. The existing 5D array a is copied to a new block of memory assigned to b. An integer pointer 'p' is then assigned the beginning address of b. The values of b are accessed sequentially through pointer p.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main (void) {

    int a[2][2][2][2][2] = { { { {{1,2}, {3,4}},        /* 5D Array */
                                 {{5,6}, {7,8}} },
                               { {{1,2}, {3,4}},
                                 {{5,6}, {7,8}} } },
                             { { {{1,2}, {3,4}},
                                 {{5,6}, {7,8}} },
                               { {{1,2}, {3,4}},
                                 {{5,6}, {7,8}} } } };
    /* ptr to 5D, ptr to int* */
    int (*b)[2][2][2][2] = NULL, *p = NULL;

    /* allocate block to hold a */
    b = malloc (sizeof a/sizeof *a * sizeof *b);
    memcpy (b, a, sizeof a/sizeof *a * sizeof *b);  /* copy a to b */

    p = ****b;                 /* assign address of first element */
    printf ("\nb:\n");          /* ouput using sequential access */
    for (int i = 0; i < (int)(sizeof a/sizeof *****a); i++)
        printf (" *(p + %2d) : %d\n", i, p[i]);

    free (b);   /* single free is all that is required */

    return 0;
}

Example Use/Output

$ ./bin/arr5dstatic1

b:
 *(p +  0) : 1
 *(p +  1) : 2
 *(p +  2) : 3
 *(p +  3) : 4
 *(p +  4) : 5
 *(p +  5) : 6
 *(p +  6) : 7
 *(p +  7) : 8
 *(p +  8) : 1
 *(p +  9) : 2
 *(p + 10) : 3
 *(p + 11) : 4
 *(p + 12) : 5
 *(p + 13) : 6
 *(p + 14) : 7
 *(p + 15) : 8
 *(p + 16) : 1
 *(p + 17) : 2
 *(p + 18) : 3
 *(p + 19) : 4
 *(p + 20) : 5
 *(p + 21) : 6
 *(p + 22) : 7
 *(p + 23) : 8
 *(p + 24) : 1
 *(p + 25) : 2
 *(p + 26) : 3
 *(p + 27) : 4
 *(p + 28) : 5
 *(p + 29) : 6
 *(p + 30) : 7
 *(p + 31) : 8

There is good reason that the rest of the comments and answers suggest you find some way other than using a 5D array setup. It would be worth while to investigate if you can modify whatever is producing the data you capture in your original 5D array to output the data in some other format.