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

Question

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

1. по столбцам
2. по строкам

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

Answer 1

Воспользуйтесь преимуществом Пространственная местность

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

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

Получите удовольствие от использования инструмента профилирования, такого как cachegrind , и убедитесь сами.

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

доступ к столбцу

$ cat col_major.c 
#include <stdio.h>

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 <dim;j++){
            matrix[j][i]= i*j;
        }
    }
    return 0;
}

$ valgrind --tool=cachegrind ./col_major 

==3228== D   refs:      10,548,665  (9,482,149 rd   + 1,066,516 wr)
==3228== D1  misses:     1,049,704  (      968 rd   + 1,048,736 wr)
==3228== L2d misses:     1,049,623  (      893 rd   + 1,048,730 wr)
==3228== D1  miss rate:        9.9% (      0.0%     +      98.3%  )
==3228== L2d miss rate:        9.9% (      0.0%     +      98.3%  )

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

$ cat row_major.c 
#include <stdio.h>

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 <dim;j++)
            matrix[i][j]= i*j;

    return 0;
}

$ valgrind --tool=cachegrind ./row_major 

==3524== D   refs:      10,548,665  (9,482,149 rd   + 1,066,516 wr)
==3524== D1  misses:        66,664  (      968 rd   +    65,696 wr)
==3524== L2d misses:        66,583  (      893 rd   +    65,690 wr)
==3524== D1  miss rate:        0.6% (      0.0%     +       6.1%  )
==3524== L2d miss rate:        0.6% (      0.0%     +       6.1%  )

Answer 2

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

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

Answer 3

Для 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 .