3

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 ?

Jarvis
  • 8,494
  • 3
  • 27
  • 58

3 Answers3

13

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

Lundin
  • 195,001
  • 40
  • 254
  • 396
  • Nice explanation and plus one from me, but why `(*array)[Y]` can let you access/assign to it via using `array[i][j]` but when you create it using `(*array)[X][Y]` you have to use `(*array)[i][j]` for the manipulation later? – Yahya Dec 31 '17 at 12:59
  • 1
    @Yahya with `int (*array)[Y]` , `array` is a pointer to an array of size Y. This means it has two levels to dereference- so `array[row]` gives an array, and `array[row][col]` gives you the int. With `int (*array)[X][Y]`, there are now 3 levels- it is a pointer to a 2D array of ints. So you need the first `(*array)` star to allow the double index access. – Scott Staniewicz Feb 20 '18 at 16:28
5
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 ridiculous1 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.

1 For some (application specific) definition of ridiculous

StoryTeller - Unslander Monica
  • 165,132
  • 21
  • 377
  • 458
  • 1
    Even better would be `data_type (*mat)[size_2] = malloc( sizeof *mat * size_1 );`. `sizeof *mat` is equivalent to `sizeof (data_type[size_2])`. – John Bode Nov 28 '16 at 15:24
  • @JohnBode, thank. I was under the (mistaken) impression `sizeof` won't behave well for VLA's – StoryTeller - Unslander Monica Nov 28 '16 at 15:28
  • 2
    With respect to VLAs, the situation isn't 100% clear. Yes, if you read the standard literally, my version should invoke UB if `mat` is a VLA. However, a few of us are of the opinion that the standard is badly worded in that regard. There's no reason you should have to *dereference the pointer* to obtain a VLA's dimensions. The implementation has to carry around some kind of metadata for VLAs to work - there's no reason to believe it can't just use that metadata when evaluating `sizeof`. – John Bode Nov 28 '16 at 15:34
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).

Leonora Tindall
  • 1,391
  • 2
  • 12
  • 30