Доступ к элементам матрицы по ряду столбцов и столбцам

Дана matrix A[i][j] . Если мы хотим добавить элементы матрицы, какой метод лучше и почему?

  1. колонка
  2. разумный ряд

С моей точки зрения, разумный ряд лучше, потому что в элементах представления массива хранятся в смежных ячейках памяти, поэтому доступ к ним занимает меньше времени. Но поскольку в оперативной памяти каждый прием занимает одинаковое время, имеет ли это значение?

Воспользуйтесь Пространственной Местностью

В C матрицы хранятся в основном порядке . Поэтому, если вы получите доступ к элементу a[i][j] , доступ к элементу a[i][j+1] , вероятно, ударит по кешу. Не будет доступа к основной памяти. Кэш-память быстрее, чем основная память, поэтому шаблон доступа имеет значение.

Разумеется, необходимо учитывать больше факторов, таких как доступ на чтение / чтение, политика записи (запись, запись назад / запись, отсутствие выделения записи), многоуровневые кэши и т. Д. Но это кажется излишним для этого вопроса.

Поужинайте с помощью инструмента профилирования, такого как cachegrind , и посмотрите его на себя.

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

доступ в столбцы

 $ cat col_major.c #include  int main(){ size_t i,j; const size_t dim = 1024 ; int matrix [dim][dim]; for (i=0;i< dim; i++){ for (j=0;j  

доступ к строке

 $ cat row_major.c #include  int main(){ size_t i,j; const size_t dim = 1024 ; int matrix [dim][dim]; for (i=0;i< dim; i++) for (j=0;j  

Если массивы небольшие, это не важно. Если они большие, тогда время чтения может быть затронуто. Большая проблема – это кеш. Если вы не можете ожидать, что ваша полная matrix будет загружена в кеш сразу, то вы хотите свести к минимуму количество промахов в кеше, с которыми вы сталкиваетесь, поскольку работа с промахом кэш-памяти занимает относительно много времени.

Если массивы действительно большие, то вы можете получить еще больший выигрыш в производительности, вызвав больше замены страниц, чем необходимо.

Для C наилучшим способом обработки многомерных массивов является:

 int a[MAX_I][MAX_J]; for (i = 0; i < MAX_I; ++i) { for (j = 0; j < MAX_J; ++j) { /* process a[i][j] */ } } 

Причина этого заключается в том, что язык C обрабатывает массивы как указатели со смещениями, см. Язык программирования C.