overhead in addressing 2d array in linear memory space

Question

Does addressing addressing values in a multidimensional array in a linear fashion as in

values[row_num*row_width + column_num]

incur extra computation for the multiplication/addition when compared to values[row][col]? Or does the compiler convert the latter to the former anyway?

Answer 1

does the compiler convert the latter to the former anyway?

Yes. If you index consecutive memory locations, the caching will work in your favor, big-time.

Answer 2

Assuming you're comparing indexing into e.g. int values[M*N] and int values[M][N] respectively, then these will create equivalent code in practice.

However, if you're using values[row][col] to index into e.g. int (*values)[N], then it's a different matter...

Answer 3

It depends. If you declare an array like this:

int values[m][n];

then the compiler optimizes the accesses, i.e. using a linear piece of memory and computing the right offsets (like in your pseudo code).

But if you declare an array like this:

int **values;
values = new int*[m];
for (size_t i = 0; i < m; ++i) values[i] = new int[n];

Then the compiler can't optimize an array access like

values[row][col]
// same as
*(*(values+row) + col)

I.e. such code yields one extra memory access. And since on current architectures, a memory access is several orders of magnitudes more expensive then computing the offset, this style of more-dimensional arrays is less efficient than using a linear block of memory and computing (or let the compiler compute where possible) the offsets.