Best way to allocate memory to a two-dimensional a

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

data_type (*mat)[size_2] = malloc(size_1 * size_2 * sizeof(data_type));

That will allocate contiguous memory for an array of arrays ("2d array"). If you don't require ridiculous¹ amounts of space, this is the way to go. You'll decrease memory fragmentation, increase cache friendliness and avoid too much overhead due to the use of malloc.

---

¹ _{For some (application specific) definition of ridiculous}

Answer 2

Given a fixed size, you can simply say twoDimArray[100][100], which will allocate it on the stack. When allocating on the heap, however, (whether because the size is very large or because the size is dynamic) you have more options.

You could allocate an array of pointers, then loop through allocating memory for each row. This is problematic for cache locality, but very good if the size is very large and your access is sequential; it allows a reasonable amount of fragmentation without a massive impact on performance, because the array of arrays can be separate from the arrays themselves, which can each be separate from each other. In a linear access scenario, you will mostly not be jumping between memory regions; rather, you'll access across a whole line before even possibly moving to a new region.

The second way is to linearize the access and allocate it all at once; i.e., allocate enough memory for sizex * sizey and then index it with (positiony * sizex) + positionx; that is, count down some rows and then across some columns. This is great for random access and improves cache locality because the memory is contiguous, but it might fail if there is not enough contiguous memory available (and the cache locality benefit is not applicable if you need more memory than there is cache).

Answer 3

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].