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

Question

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

1. колонки мудрого
2. ряд мудрого

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

Answer 1

Примите преимущество Spatial Locality

В C, матрицы хранятся в г ow-major order. Поэтому, если вы обращаетесь к элементу 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 обрабатывает массивы, как указатели со смещением, см: The C Programming Language.