Best way to allocate memory to a two-dimensional array in C?

Question

What is the best way to allocate memory to a two-d array in C,from both the perspectives : memory-management and speed ?

Also, which is better to use, a two-d array (and allocate memory to it) or a double pointer ? Can someone explain in detail,what happens inside,why a method is better than the other one ?

Answer 1

To get best performance and best readability, such arrays should always be allocated as a contiguous chunk of memory:

type (*array) [X][Y] = malloc( sizeof(type[X][Y]) );

You should avoid this:

// BAD METHOD, not a real array

type** lookup_table = malloc( X*sizeof(type*) );
for(size_t i=0; i<Y; i++)
{
  lookup_table[i] = malloc( Y*sizeof(type) );
}

The former is faster for many reasons. It is allocated in a contiguous chunk of memory and not segmented all over the heap. Segmented versions block all forms of code optimizations and efficient on-chip data cache use, plus the actual allocation is also much slower.

The "bad" version above has one advantage though, and that is when you want individual dimensions to have variable length, such as when making a look-up table for strings. Then you have to use that form. But if you want a real 2D array, there is never a reason not to use the former.

---

Note that the first version is usually written as

type (*array) [Y] = malloc( sizeof(type[X][Y]) );

to allow more convenient use: array[i][j], rather than the less readable (*array)[i][j].