逐行访问矩阵元素与列方式

Question

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

1. 列明智
2. 划明

从我的观点来看,行方式更好,因为在数组表示元素存储在连续的内存位置,因此访问它们花费的时间更少.但是因为在RAM中获取每个位置需要相同的时间,这是否重要？

Answer 1

利用空间位置

在C中,矩阵以r ow-major顺序存储.因此,如果您访问元素a[i][j],则对元素的访问a[i][j+1]可能会触及缓存.不会访问主内存.缓存比主内存快,因此访问模式很重要.

当然,必须考虑更多因素,例如写访问/读访问,写策略(直写,回写/写分配,无写分配),多级缓存等.但这对于这个问题来说似乎有些过分.

使用分析工具(如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%  )