Performance of 2-dimensional array vs 1-dimensional array

by

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.

More Related Contents:

  1. C programming: array not have any bound [duplicate]
  2. Dynamic Array of strings [closed]
  3. Fast way to tokenize a string in c
  4. How to resolve a variable for char length? [closed]
  5. C pointer to array/array of pointers disambiguation
  6. Difference between passing array and array pointer into function in C
  7. Create a pointer to two-dimensional array
  8. Dynamic allocation of an unknown matrix in C
  9. typedef fixed length array
  10. Difference between array type and array allocated with malloc
  11. printf adds extra `FFFFFF` to hex print from a char array [duplicate]
  12. Unsized array declaration in a struct
  13. “error: assignment to expression with array type error” when I assign a struct field (C)
  14. Is this a pointer to a pointer of the start of an array?
  15. Return char[]/string from a function [duplicate]
  16. Print all permutation in lexicographic order
  17. Find malloc() array length in C? [duplicate]
  18. What’s a modern term for “array/pointer equivalence”?
  19. In C, why can’t I assign a string to a char array after it’s declared?
  20. Is it possible to allocate array inside function and return it using reference?
  21. Doesn’t a 2D array decay to pointer to pointer
  22. Why can’t I create an array with size determined by a global variable?
  23. Store data in array from input [duplicate]
  24. Why can’t the size of a static array be made variable?
  25. How to define and work with an array of bits in C?
  26. Associative arrays in C
  27. Array of size 0 at the end of struct [duplicate]
  28. Difference between dereferencing pointer and accessing array elements
  29. Difference between pointer to pointer and pointer to array?
  30. 2D Array indexing – undefined behavior?

Leave a Comment