CODEWITHSUNDEEP
carraysmemoryoptimization
Christian Panhuber
Christian Panhuber

Reputation: 173

In C: Is it faster to access a char* = malloc() used like a 2D array than an array[][]?

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.

Upvotes: 1

Views: 201

Answers (2)

VAndrei
VAndrei

Reputation: 5570

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.

Upvotes: 1

mfro
mfro

Reputation: 3335

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

Upvotes: 5

Related Questions