накладные расходы при адресации 2d массива в линейном пространстве памяти

Question

Выполняет ли адресацию значений в многомерном массиве линейным способом, как в

values[row_num*row_width + column_num]

нести дополнительные вычисления для умножения / сложения по сравнению со значениями [row] [col]? Или компилятор все равно конвертирует последний в первый?

Answer 1

Если вы сравниваете индексирование, например, с int values[M*N] и int values[M][N] соответственно, тогда они на практике создадут эквивалентный код.

Однако, если вы используете values[row][col] для индексации, например, int (*values)[N], тогда другое дело ...

Answer 2

Это зависит.Если вы объявляете массив следующим образом:

int values[m][n];

, то компилятор оптимизирует доступ, то есть использует линейный фрагмент памяти и вычисляет правильные смещения (как в вашем псевдокоде).

Но если вы объявите массив следующим образом:

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

, то компилятор не сможет оптимизировать доступ к массиву, как

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

Т.е. такой код дает один дополнительный доступ к памяти.А поскольку в современных архитектурах доступ к памяти на несколько порядков дороже, чем вычисление смещения, этот тип многомерных массивов менее эффективен, чем использование линейного блока памяти и вычислений (или, если возможно, компилятор вычисляет)смещения.

Answer 3

конвертирует ли компилятор последний к прежнему?

Да. Если вы индексируете последовательные области памяти, кэширование будет работать в вашу пользу, большое время.