Performance of 2-dimensional array vs 1-dimensional array

Question

In C, is there a difference in time and space between an m×n 2-dimensional array vs a 1-dimensional array of length m×n (for large values of m and n)? Will accessing elements be faster with a 1-dimensional array?

Answer 1

In C, 2-dimensional arrays are just a neat indexing scheme for 1-dimensional arrays. Just like with a 1D array, 2D arrays allocate a single block of contiguous memory, and the A[row][col] notation is similar to saying A[row*NCOLS+col].

Usually if you were to implement your own multidimensional arrays using single dimensional arrays, you'd write an indexing function:

int getIndex(int row, int col) { return row*NCOLS+col; } 

Assuming your compiler inlines this function, the performance here would be precisely the same as if you used the built in 'indexing function' of 2D arrays.

To illustrate:

#define NROWS 10 #define NCOLS 20 

This:

int main(int argc, char *argv[]) {     int myArr[NROWS*NCOLS];     for (int i=0; i<NROWS; ++i) {        for (int j=0; j<NCOLS; ++j) {           myArr[getIndex(i,j)] = i+j;        }     }     return 0; } 

Should perform the same as this:

int main(int argc, char *argv[]) {     int myArr[NROWS][NCOLS];     for (int i=0; i<NROWS; ++i) {        for (int j=0; j<NCOLS; ++j) {           myArr[i][j] = i+j;        }     }     return 0; } 

Though as AraK pointed out, if you are jumping around rows a lot, and the rows are very large, you could hit a lot of page faults... in that case the custom indexing function (with rows and cols switched around) could help, but so could simply changing which of the dimensions in a 2-dimensional array you treat as the rows and which you treat as the columns.