linux.dsplabs.com.au/forums

[QuantumKnot]

2D arrays in C (and C++) are slow to access, due to the way they are allocated in memory. For example, if you wish to allocate a 3 x 4 array in C, it actually consists of a 1D array of three pointers, where each pointer points to the address of three 1D arrays of 4 values.

Code: Select all

int **array = NULL, i, rows = 3, cols = 4;

array = (int **)malloc(rows * sizeof(int *));
for (i = 0; i < rows; i++)
   array[i] = (int *)malloc(cols * sizeof(int));


Hence the 2D array is not contiguous in memory, so accesses can be slow as these 1D arrays may reside in any part of memory. But it is nice to be able to use 2 indices to access the elements. eg. array[2][3] = 4;

We can make a "hacked" 2D array that stores things in a 1D array, such that the values are stored contiguously.

Code: Select all

int *array1 = NULL, **array2 = NULL, i, rows = 3, cols = 4;

array1 = (int *)malloc(rows * sizeof(int)); /* this is the 1D array */
array2 = (int **)malloc(rows * sizeof(int *)); /* This is the "hacked" 2D array */
for (i = 0; i < rows; i++)
   array2[i] = &(array1[cols * i]);


So now the values are stored in array1 (which is contiguous in memory so access is fast), but we access it like any other 2D array, e.g. array2[2][3] = 2;

And freeing the two arrays is much easier too. No need for a 'for' loop.