Multidimensional Array indexing

Question

I have read in several places that allocating multidimensional arrays as such is inefficient and should be avoided.

int main(){
    int** arr2d = malloc(3*sizeof(int*));
    for(int m = 0; m < 3 ; ++m){
        arr2d[m] = malloc(sizeof(int)*3);
    }
    for(int m = 0 ; m < 3 ; ++m){
        for(int n = 0; n < 3; ++n){
            arr2d[m][n] = m+n;
        }
    }
    for(int m = 0 ; m < 3 ; ++m){
        for(int n = 0; n < 3; ++n){
            printf("%d,",arr2d[m][n]);
        }
        printf("\n");
    }
    for(int m = 0; m < 3 ; ++m){
        free(arr2d[m]);
    }
    free(arr2d);
    return 0;
}

The alternative would be to allocate an array enough for m*n and index it accordingly giving the idea of 2D

int main(){
    int* arr = malloc(9*sizeof(int));
    for(int m = 0; m < 3; ++m){
        for(int n = 0; n < 3; ++n){
            int index = m*3+n;
            arr[index] = m+n;
        }
    }
    
    for(int m = 0; m < 3; ++m){
        for(int n = 0; n < 3; ++n){
            int index = m*3+n;
            printf("%d,",arr[index]);
        }
        printf("\n");
    }
    free(arr);
    return 0;
}

What I'm wondering is how much of a difference in terms of resource usage and timing does that really make? I know in the first example a total of 32 bytes are allocated and in the second example 27 bytes are allocated. When dealing with much larger matrices I can see that making a difference but does time complexity change or does it not matter since you're looping m*n number of times regardless? Should I always follow the second example as basically standard?

dbush · Accepted Answer · 2022-01-16 16:24:02Z

4

You can get the best of both worlds by allocating memory for a multidimentional array directly:

int (*arr)[3] = malloc(3 * sizeof *arr);

for(int m = 0 ; m < 3 ; ++m){
    for(int n = 0; n < 3; ++n){
        arr[m][n] = m+n;
    }
}
for(int m = 0 ; m < 3 ; ++m){
    for(int n = 0; n < 3; ++n){
        printf("%d,",arr[m][n]);
    }
    printf("\n");
}

free(arr);

This creates the memory in a single contiguous block like the second example, allowing for more efficient reads and writes, and gives you 2D array indexing, allowing for easier to read code and for letting the compiler figure out the best way to index into the memory block internally.

edited Jan 16, 2022 at 16:24

answered Jan 16, 2022 at 16:15

dbush

233k27 gold badges261 silver badges334 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Kayla Over a year ago

I've never seen it done that way.. in terms of efficiency would that be as good as the second example? I have seen examples where people type cast the 1D array to a 2D and I was wondering about that as well typedef int arr2d[m][n]; arr2d* matrix = (arr2d*)arr; Then indexing it as if it were matrix[m][n]

Fredrik Over a year ago

@kayla the example dbush has shown is how you dynamicly allocate a 2d array.

Kayla Over a year ago

Ah that's very cool ! thank you

Fredrik Over a year ago

@kayla you can also do it with variable lengths, example: "int (*arr)[width] = malloc(height * sizeof *arr);"

Yunnosch · Accepted Answer · 2022-01-16 16:17:11Z

1

If you have a rectangular matrix, i.e. all m x n values, then it is less tedious, less memory consumption and less error-prone to use the second option (though it arguably still is a matter of taster....).

The first option becomes more efficient if you do not have a rectangular thing, e.g. something like a array of differently long sub arrays.
Memory waste can get very relevant there.

Another example, back at matrices, would be a triangular matrix, with 0 or other know values outside of the triangle. Implementations could benefit from that attribute and use the "boring" or predictable values from outside the triangle, wihtout needing to store them.

edited Jan 16, 2022 at 16:17

answered Jan 16, 2022 at 16:11

Yunnosch

26.8k9 gold badges46 silver badges66 bronze badges

3 Comments

Kayla Over a year ago

So in terms of time complexity does it really not make much of a difference?

Yunnosch Over a year ago

What complexity are you looking at? If settting up the sub-mallocs/frees is a relevant load, then factor that in. It might outweigh the benefits/disadvantages. But a general prediction is not possible. As usual, before you optimise you should measure/benchmark.

Kayla Over a year ago

I understand, thank you. I think it stands the first one doesn't have much benefit although being easier to see and index.

Collectives™ on Stack Overflow

Multidimensional Array indexing

2 Answers 2

4 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related