Stack memory use continuous dynamically allocated array vs statically

Question

I'm working with 3D and 4D arrays of variable sizes and they have to be continuous (sometimes is easier call as *(&x[0][0][0] + k) than the 'x[][][]' way). 'Cause of the variable size of the array, I need to allocate dynamically. I found this code, in another answer (Dynamic memory allocation for 3D array) to do that and it works fine, but I don't know how much memory use of the stack.

double ***arr3dAlloc(const int ind1, const int ind2, const int ind3) {
    int i;
    int j;
    double ***array = (double***)malloc((ind1 * sizeof(double*)) + 
                                        (ind1 * ind2 * sizeof(double**)) + 
                                        (ind1 * ind2 * ind3 * sizeof(double)));
    for (i = 0; i < ind1; ++i) {
        array[i] = (double**)(array + ind1) + i * ind2;
        for (j = 0; j < ind2; ++j) {
            array[i][j] = (double*)(array + ind1 + ind1 * ind2) + i * ind2 * ind3 + j * ind3;
        }
    }
    return array;
}

the question is:

• What is the difference between double ***arr1 = arr3dAlloc(N1,N2,N3); and double arr2[N1][N2][N3];

• Given that arr2 uses N1*N2*N3*sizeof(double) memory of the stack, how much memory does arr1 use? Only sizeof(double***)?

• In general, is there a method to measure the use of stack memory of any variable?

Answer 1

A pointer has size of a pointer with the respective machine architecture (nowadays often long or long long). That size is independent of the type of the memory being referenced. (A "**" is just referring to another pointer.)

An array type[N] is always allocating sizeof(type)*N byte of memory. sizeof() includes padding of type to proper alignment boundary. Thus, using malloc(sizof(type)*N) will allocate sufficient memory for an array of N elements of type, providing a pointer to the allocated piece of memory. You may use calloc() for also getting the memory initialized to zero.

As the allocated memory is not dependent on the organisation of a multi-dimensional array, such an approach will work for any number of dimensions >=1.

To address your questions:

• double ***arr1 = … is just storing the pointer to some memory area, while arr2[N1][N2][N3] is allocating padded space for N1*N2*N3 doubles.
• arr1 uses sizeof(void *) bytes, while arr2 is using N1*N2*n3*sizeof(double) bytes.
• sizeof(var) always gives the size of the variable, whether this is being in data/bss segment or on stack.

Answer 2

Your code allocates a 3D array and a array of pointers to arrays of pointers to double to access its elements via double indirections. There are some issues with this approach:

• Your code does not align the double array on a double boundary. If the size of a pointer if 4 bytes and the array has size 3x4x5, the double array will be misaligned, which may cause undefined behavior on some systems.

• The types used in your size computations are approximate.

• Type int might overflow when computing the size of very large matrices.

Here is a corrected version (assuming all pointer types have the same size):

double ***arr3dAlloc(int ind1, int ind2, int ind3) {
    size_t level1_size = sizeof(double**) * ind1;
    size_t level2_size = sizeof(double*) * ind1 * ind2;
    size_t padding = (sizeof(double) - (level1_size + level2_size) % sizeof(double))
                      % sizeof(double);
    size_t level3_size = sizeof(double) * ind1 * ind2 * ind3;
    int i, j;
    double ***array = calloc(1, level1_size + level2_size + padding + level3_size);
    double *array3d = (double*)((unsigned char*)array + level1_size + level2_size + padding);
    for (i = 0; i < ind1; ++i) {
        array[i] = (double**)(array + ind1) + i * ind2;
        for (j = 0; j < ind2; ++j) {
            array[i][j] = array3d;
            array3d += ind3;
        }
    }
    return array;
}

Note that with C99, you can allocate real 3D arrays that you can use directly in your main computational code:

/* array3d is a pointer to an allocated 3D array: */
double (*array3d)[ind2][ind3] = calloc(sizeof(*array3d), ind1);

/* array3d can be used like a statically defined array: */
for (int i = 0; i < ind1; i++) {
    for (int j = 0; j < ind2; j++) {
        for (int k = 0; k < ind3; k++) {
            array3d[i][j][k] = i + j + k;
        }
    }
}

Answer 3

There are a couple of issues to address here.

The first is the difference between global variables, heap, and stack. These are all portions of RAM. malloc() allocates a portion of the heap and returns a pointer. This is discussed in many other places on the Internet.

The other issue is compile-time versus run-time allocation. For compile-time allocation, the size of the array must be known in advance. Your example uses run-time allocation (malloc()), because the size of the array is passed into the function as variables. It is not possible to allocate the array on the stack or in globals without knowing its size at compile time.