1

Just stumbled accross this recent question:

How can I have a dynamically allocated 2D array in C?

I just wondered: When I create a 2D array with a simple malloc and manage the 2D-like access myself like so:

int row=100;
int col=100;
char* buffer = malloc(sizeof(char)*row*col);
for(int i=0;i<row;i++){
    for(int j=0;j<col;j++){
        buffer[i*col+j]=128;
     }
}

would this be (significantly) faster then when creating a 'conventional' 2D Array because in the former I achieve buffer optimization through sequential access? Or am I thinking wrong?

int row=100;
int col=100;
char buffer[row][col];
for(int i=0;i<row;i++){
    for(int j=0;j<col;j++){
        buffer[i][j]=128;
     }
}

Thanks for your explanation.

Community
  • 1
  • 1
Christian Panhuber
  • 153
  • 8

2 Answers2

5

Leaving the (small) overhead for dynamic memory allocation away, there is no difference if you access a particular element in a memory area by [row][column] or * (row * rowsize + column). It's basically just a difference in notation.

So your question is more like "is it better to have arrays defined "row first" than "column first?".

And the answer is: only you will know since you are the one to define the access pattern to the memory area depending on your application's needs.

I wouldn't think too much about this unless you deal with very large arrays (where one dimension is larger than what fits into your caches).

mfro
  • 3,286
  • 1
  • 19
  • 28
  • Thanks! I wouldn't have expected much of a difference for accessing particular elements, but I wondered wether there would be a (generally explainable) difference when accessing all elements in sequence like I did in the nested loops. The question was meant more like "is it better to have arrays defined in row and columns or rather in one all-in-one row?" – Christian Panhuber Apr 17 '15 at 07:12
  • @mfro I don't think this is a good recommendation. It's almost always better to use 1D due to the reasons I mentioned in my post. You agree that 1D makes use of better caching but there are also more advantages of using 1D. – VAndrei Apr 17 '15 at 08:24
  • the "row first rather than column first question" boils down to: is my machine faster to add `sizeof(element)` to a register than to add `sizeof(element) + number of columns` (note that this addition reduces to a constant at compile time). E.g. with a 100x100 character array, it would be "is `* (x + 100)` faster than `*(x + 1)`?". For most cases (unless you have really many rows/columns, you can always construct an example that contradicts), I guess there is not much difference. – mfro Apr 17 '15 at 08:33
  • I think the point I was missing is: When I create a static 2D array on the stack as in example 2, will it still occupy a continuous area in the memory? If so then I understand why you state that the difference will be hard to measure – Christian Panhuber Apr 17 '15 at 09:48
  • `malloc()` always allocates an (at least virtually, in most cases also physically, but that should not bother you) contiguous area in heap. This is a must. Otherwise a lot of C programs would not work. – mfro Apr 17 '15 at 10:27
  • 1
    oh, and static allocation on stack of course also gives you a contiguous memory area in your case – mfro Apr 17 '15 at 10:36
  • now I get it... so in a char array[2][2]; the [1][0] byte follows the [0][1] byte which in turn would be the same as writing array[2]? Then my question doesn't really make sense any more, which is at least some learn effect, thanks! – Christian Panhuber Apr 17 '15 at 15:07
1

Note 1:

In the first code snippet, the array is allocated on the process's heap, while on the second snippet you allocate the buffer on the stack. If you want to use larger sized arrays, you might get a ... stackoverflow :)

Note 2:

My explain is focusing on the case where you want to allocate dynamically a 2D array, using Type** (int** in your case).

When you deal with a 2D array, it's faster to allocate it as a 1D array and use smart indexing to access it as a 2D array. This is because:

  • 1D array fills a contiguous space in memory (lower fragmentation). This enables better caching of the array, decreasing the access latencies.
  • When you allocate a 2D array, you have another level of indirection, meaning that you need to get the address of the row first and then access the element. When you use a 1D array, you access directly the element.
  • When the array is allocated in 1D fashion, it's easily to align it to the cache line size. This will make it easier for the compiler to optimize transactions and avoid having to make 2 reads for an element that falls on a cache line boundary.
  • Dealing with 1D array, should help the compiler generate better vectorized code.
VAndrei
  • 5,420
  • 18
  • 43
  • note that the second snippet wouldn't work in real code anyway since `row ` and `column` must be compile-time constants there – mfro Apr 17 '15 at 10:33
  • regarding your statements: a 1D array does fill contiguous space. Just as a 2D array (as defined by the OP) does. There is no difference. "Fragmentation" is not an issue here. 1.) Fragmentation in my book means to waste memory in the heap if you `free()` arbitrary sized areas that can't be efficiently reused/merged by the memory manager. A stack can't fragment, that's right but one single dynamic allocation can't as well. 2.) there is no difference in indirection if you declare a 2D array then to "simulate" a 2D array by a 1D one it always boils down to `base address + offset`. – mfro Apr 17 '15 at 10:43
  • @mfro My answer was more refering to allocating dynamically a 2D array, using Type** .In the case presented by OP you are right. The 2D array is allocated on the stack so fragmentation is not a problem. – VAndrei Apr 17 '15 at 14:38