嵌套for循环性能计算：交换数组下标为何使性能提升400%？

原始代码 #

void row_order (){
    char A[1024][1024] = {0};
    char B[1024][1024] = {0};
    char C[1024][1024] = {0};
  
    for(int i = 0 ; i<1024;i++){
        for(int j = 0 ; j<1024;j++){
            C[i][j] = A[i][j] * B[i][j];
        }
    }
}

int main() {
    for(int i = 0 ; i< 1000; i++){
        row_order();
    }
}

修改点 #

将赋值语句从：

C[i][j] = A[i][j] * B[i][j];

修改为：

C[j][i] = A[j][i] * B[j][i];

问题 #

修改后代码性能提升了400%，请问该现象的原因是什么？

解答 #

这个性能暴涨的核心原因，要从C语言二维数组的存储规则和CPU缓存的工作逻辑说起：

1. C语言二维数组是行优先存储
   比如A[1024][1024]这种二维数组，在内存里是按行“平铺”的——A[0][0]、A[0][1]…A[0][1023]是连续的内存地址，紧接着是A[1][0]、A[1][1]…以此类推。也就是说，A[i][j]的内存地址可换算为&A[0][0] + i*1024 + j，同一行的元素紧密排列，跨行访问则会直接跳过1024字节的内存空间。

2. CPU缓存靠空间局部性提速
   CPU缓存的速度比主存快几个数量级，它的核心优化逻辑是「空间局部性」：当CPU读取某个内存地址时，会把该地址附近的一整块内存（即缓存行，通常为64字节）加载到缓存中。如果后续访问的是相邻地址，就能直接从缓存读取，无需从速度极慢的主存加载。

回到你的代码场景：

• 若原始代码的实际执行逻辑是按列遍历（比如循环外层为j、内层为i），那么访问A[i][j]时，每次i递增都会跳过1024字节，完全不在同一个缓存行内，会触发大量「缓存未命中（Cache Miss）」，CPU不得不频繁从主存捞数据，性能暴跌。
• 修改为C[j][i] = A[j][i] * B[j][i]的同时，循环顺序同步调整为按行遍历（外层j、内层i），此时j固定时i递增，访问的是同一行的连续元素，缓存命中率大幅提升，CPU能持续从高速缓存读取数据，因此性能直接暴涨400%。

本质上就是：行遍历顺着内存存储顺序访问，能充分利用CPU缓存；列遍历跳着访问内存，缓存完全失效，两者的执行效率天差地别。

内容的提问来源于stack exchange，提问作者hasangkz