哪个有更好的内存访问？(C++)

Question

哪个版本效率更高,为什么？似乎两者都进行相同的计算.我唯一能想到的是编译器是否认识到(a)j中没有改变值而不必一遍又一遍地计算它.任何输入都会很棒!

#define M /* some mildly large number */
double a[M*M], x[M], c[M];
int i, j;

(a) First version
for (j = 0; j < M; j++)
    for (i = 0; i < M; i++)
        c[j] += a[i+j*M]*x[i];

(b) Second version
for (i = 0; i < M; i++)
    for (j = 0; j < M; j++)
        c[j] += a[i+j*M]*x[i];

Answer 1

这是关于内存访问模式而不是计算效率.通常(a)更快,因为它以单位步幅访问存储器,这比(b)具有更高的缓存效率,其具有步幅M.在(a)每个高速缓存行被充分利用的情况下,而对于(b),可能在每个高速缓存行被驱逐之前仅使用一个数组元素,

话虽如此,一些编译器可以执行循环重新排序优化,因此在实践中,如果发生这种情况,您可能看不到任何差异.与往常一样,您应该对代码进行基准测试/分析,而不仅仅是猜测.