c - 按行访问矩阵元素与按列访问矩阵元素

Question

给出了一个矩阵A[i][j]。如果我们要添加矩阵的元素，哪种方法更好，为什么？

1. 列明智
2. 按行

从我的角度来看，行方式更好，因为在数组中表示元素存储在连续的内存位置，因此访问它们需要更少的时间。但是由于在 RAM 中获取每个位置需要相同的时间，这有关系吗？

Answer 1

利用Spatial Locality

在 C 中，矩阵存储在 r ow-major order 中.因此，如果您访问元素 a[i][j]，则对元素 a[i][j+1] 的访问很可能会命中缓存。不会执行对主存储器的访问。缓存比主内存更快，因此访问模式很重要。

当然，还要考虑更多的因素，比如写权限/读权限，写策略(write through，write back/write allocate，no write allocate)，多级缓存等等。但这对于这个问题来说似乎有些矫枉过正。

享受分析工具带来的乐趣，例如 cachegrind ，并亲眼看看。

例如，考虑一个访问 4MB 矩阵的虚拟程序。查看每种访问模式的未命中率之间的差异。

列访问

$ 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%  )