GEMM代码循环顺序为何大幅影响执行效率？核心原因探究

先看你给出的两段GEMM代码：

// 第一版
void gemm_cpu_naive(
    int* __restrict__ C, 
    const int* __restrict__ A, 
    const int* __restrict__ B, 
    const int n, 
    const int m, 
    const int k){
    for(int l=0; l<k; ++l)
        for(int i=0; i<n; ++i)
            for(int j=0; j<m; ++j){
                C[i*m+j] += A[i*k+l] * B[l*m+j];
            }
}

// 第二版
void gemm_cpu_naive(
    int* __restrict__ C, 
    const int* __restrict__ A, 
    const int* __restrict__ B, 
    const int n, 
    const int m, 
    const int k){
    for(int i=0; i<n; ++i)
        for(int j=0; j<m; ++j)
            for(int l=0; l<k; ++l){
                C[i*m+j] += A[i*k+l] * B[l*m+j];
            }
}

当n=m=k=64时两版性能差异悬殊，核心原因是数组的内存访问模式完全不同，你的初始判断有误，具体分析如下：

1. 最关键因素：B数组的访问模式 #

CPU缓存的性能收益核心依赖空间局部性——连续的内存地址会被一次性加载到缓存行中，后续访问无需再从内存读取。

• 第一版：l是外层循环，固定l后遍历j，B[l*m+j]是访问B的第l行，地址连续（每次j+1对应地址+4字节）。64个int的行刚好占256字节，对应4个64字节缓存行，整行可一次性加载，缓存命中率接近100%，几乎没有内存等待延迟。
• 第二版：l是内层循环，固定j后遍历l，B[l*m+j]是访问B的第j列，地址间隔为m=64（对应256字节），远超过单缓存行的大小。每次访问B的元素都无法命中缓存，必须从内存读取——内存访问速度比缓存慢几个数量级，这是性能差距的主要来源。

2. C数组的写入行为与指令并行度 #

• 第一版：i固定后遍历j，C[i*m+j]是连续写入不同内存位置，同样利用空间局部性，缓存行可被连续写入，且每个j对应的操作相互独立，CPU可以利用指令级并行同时执行多个循环体的计算，进一步提升效率。
• 第二版：固定i,j后遍历l，每次都对同一个C[i*m+j]进行累加操作。虽然这个位置的缓存命中率是100%，但每次累加都依赖上一次的结果，指令间存在数据依赖，CPU无法并行执行，只能串行计算，这也会拖慢整体速度。

3. A数组的访问模式影响（次要） #

• 第一版：固定l后遍历i，A[i*k+l]是访问A的第l列，地址间隔k=64，缓存命中率低；但因为B的访问效率极高，这个损失被抵消了。
• 第二版：固定i后遍历l，A[i*k+l]是访问A的第i行，地址连续，缓存命中率高；但B的访问效率太差，这个收益完全无法弥补。

综上，两版性能差异的核心原因是B数组的访问模式——第一版的行访问充分利用了缓存的空间局部性，而第二版的列访问完全破坏了缓存效率，再加上指令并行度的差异，最终导致了近一倍的性能差距。

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