Is there a performance drawback when declaring 2D arrays using int** compared to int (*)[N] in C?

Question

I have a question about the performance tradeoffs between different ways of storing 2D arrays in memory in C.

I know that if I declare a 2D matrix A with dimensions MxN by the following:

int (*A)[N] = malloc(M*N*sizeof(int));

then A will be a M * N * sizeof(int) bytes long contiguous block of memory.

However if I declare matrix B of the same dimensions MxN, by:

int** B = malloc(M * sizeof(int*));
for (int i = 0; i < M; i++){
    B[i] = malloc(N * sizeof(int));
}

then B will be M separate blocks of length N * sizeof(int) bytes which are contiguous on their own, but all of the M blocks together are not contiguous.

My question is if using int** way of declaring 2D arrays has some performance or any other drawbacks compared to int (*)[].

The reason why I ask this is because it is much easier to return int** from a function than int (*)[N] if the dimension N is not know at compile time, so I prefer using int**.

Answer 1

Generally speaking, using a single malloc will probably more efficient in terms of memory access than multiple calls to malloc given that the latter is not contiguous and involves an extra lookup. However, it ultimately depends on a lot of things such as hardware and your compiler.

The best way to find out is to measure, although I'd be surprised if there is a measurable difference between the two.

Answer 2

My question is if using int** way of declaring 2D arrays has some performance or any other drawbacks compared to int (*)[].

Yes it has. ** is an array of pointers and dereferencing it adds another level of indirection. It is simply less effective than using pointer to array where you have only one level of indirection.

Using pointer to an array also simplifies the allocation.

Side note: I would use objects instead of types in sizeof :

int (*A)[N] = malloc(M*sizeof(*A));