Сравнение времени доступа к двумерному массиву

Вы должны доверять возможностям своего компилятора при оптимизации стандартного кода.

Также вы должны доверять современным процессорам, имеющим быстрые инструкции по умножению чисел.

Не утруждайте себя тем или иным!

Я - несколько десятилетий назад - сильно оптимизировал некоторый код с помощью указателей вместо использования вычисления 2d-array->, но это будет a) полезно только в том случае, если это опция для хранения указателя - например, в цикле и b) имеет низкий уровень так как я предполагаю, что современный cpus должен делать доступ к массиву 2d за один цикл? Стоит измерить! Может быть связано с размером массива.

В любом случае указатели, использующие ptr++ или ptr + = NuM_COLS, наверняка будут немного быстрее, если это применимо!

Рассматриваются два случая: определение времени компиляции и определение размера массива во время выполнения. Существует большая разница в производительности.

Статическое выделение, глобальная или файловая область, массив фиксированного размера:
Компилятор знает размер массива и сообщает компоновщику выделить пространство в разделе данных/памяти. Это самый быстрый метод.

Пример:

#define ROWS 5
#define COLUMNS 6
int array[ROWS][COLUMNS];
int buffer[ROWS * COLUMNS];

Распределение времени выполнения, локальная область действия, массив фиксированного размера:
Компилятор знает размер массива и сообщает, что код выделяет пространство в локальной памяти (aka stack) для массива. В общем случае это означает добавление значения в регистр стека. Обычно одна или две инструкции.

Пример:

void my_function(void)
{
  unsigned short my_array[ROWS][COLUMNS];
  unsigned short buffer[ROWS * COLUMNS];
}

Распределение времени выполнения, динамическая память, массив фиксированного размера:
Опять же, компилятор уже вычислил объем памяти, необходимый для массива, поскольку он был объявлен с фиксированным размером. Компилятор испускает код для вызова функции выделения памяти с требуемой суммой (обычно передаваемой как параметр). Немного медленнее из-за вызова функции и накладных расходов, необходимых для поиска динамической памяти (и, возможно, сбора мусора).

Пример:

void another_function(void)
{
  unsigned char * array = new char [ROWS * COLS];
  //...
  delete[] array;
}

Распределение времени выполнения, динамическая память, переменный размер:
Независимо от размеров массива, компилятор должен испускать код для вычисления объема памяти для распределения. Затем это количество передается в функцию распределения памяти. Немного медленнее, чем выше, из-за кода, необходимого для расчета размера.

Пример:

int * create_board(unsigned int rows, unsigned int columns)
{
  int * board = new int [rows * cols];
  return board;
}

Поскольку ваша цель - обработка изображений, я бы предположил, что ваши изображения слишком велики для статических массивов. Правильный вопрос о динамически распределенных массивах

В C/C++ существует несколько способов выделения динамического 2D-массива. Как работать с динамическими многомерными массивами в C? , Чтобы сделать эту работу как в C/C++, мы можем использовать malloc с литьем (для C++ только вы можете использовать новый)

Способ 1:

int** arr1 = (int**)malloc(NUM_ROWS * sizeof(int*));
for(int i=0; i<NUM_ROWS; i++)
    arr[i] = (int*)malloc(NUM_COLS * sizeof(int));

Способ 2:

int** arr2 = (int**)malloc(NUM_ROWS * sizeof(int*));
int* arrflat = (int*)malloc(NUM_ROWS * NUM_COLS * sizeof(int));
for (int i = 0; i < dimension1_max; i++)
  arr2[i] = arrflat + (i*NUM_COLS);

Метод 2 по существу создает смежный 2D-массив: ie arrflat[NUM_COLS*i+j] и arr2[i][j] должны иметь одинаковую производительность. Тем не менее, не следует ожидать, что arrflat[NUM_COLS*i+j] и arr[i][j] из метода 1 имеют одинаковую производительность, поскольку arr1 не является смежным. Метод 1, однако, по-видимому, является методом, который наиболее часто используется для динамических массивов.

В общем, я использую arrflat[NUM_COLS*i+j] поэтому мне не нужно думать о том, как распределять динамические 2D-массивы.

Первый метод будет почти всегда быстрее. В общем случае (потому что всегда есть угловые случаи) архитектура процессора и памяти, а также компиляторы могут иметь встроенные оптимизаторы для помощи с 2d-массивами или другими подобными структурами данных. Например, графические процессоры оптимизированы для математической матрицы (2d массива).

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

... также я согласен с @Paul R, есть гораздо большие соображения, когда дело доходит до производительности, чем распределение массивов и арифметика адресов.