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.

Improve this question
6
  • 1
    in the first case you would probably get faster access with int idx = i*col; for(int j=0;j<col;j++) buffer[idx++]=128; Commented Apr 17, 2015 at 3:50
  • 1
    also, indexing should be buffer[i*col+j] Commented Apr 17, 2015 at 3:51
  • right, thanks for your comments, although the general questions about the speed advantage of sequential access remains. Commented Apr 17, 2015 at 4:00
  • Well, that would give me a value but no explanation as to whether my theory about why it is faster is right... Commented Apr 17, 2015 at 4:07
  • 1
    The only way to know which theory is right is to try it on your system. Different conditions may give different results. Commented Apr 17, 2015 at 4:23

2 Answers 2

Reset to default
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).

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

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?"
@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.
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.
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
oh, and static allocation on stack of course also gives you a contiguous memory area in your case
|
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.
Improve this answer

3 Comments

note that the second snippet wouldn't work in real code anyway since row and column must be compile-time constants there
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 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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.